NP Problem?

Hallo Forum,

die von Euch die Informatik studiert haben werden sich noch an NP Probleme erinnern. Das sind alle Probleme deren Lösung
1. "geraten" werden. Was nichts anderes meint das im schlimmsten Fall der Computer alle möglichen Lösungen durchprobiert und dann die auswählt die passt.
2. Die "geratene" Lösung muß in polynomieller Zeit überprüft werden können.

Beispiel Traveling Salesman Problem: Gibt es einen Weg durch alle Städte so das jede Stadt genau einmal besucht wird. Die Lösung fällt vom Himmel und es ist schnell überprüfbar ob alle Städte genau einmal besucht werden.

Ich stehe nun vor einem Graphen Partitionierungs Problem. Ich habe einen Graphen und möchte ihn partitionieren. Die Partitionen sollen möglichst gleich groß sein. die Verbindungen zwischen den Partitionen soll minimal sein. Gefragt ist nach der besten Lösung. Also ziemlich exakt das Problem wie bei Distributed Computing: Die Processoren sollen gleichmäßig ausgelastet werden, die Kommunikation zwischen den Processoren soll minimal sein.

Sind solche Probleme überhaupt in NP? Wenn nach der besten Lösung für etwas gefragt wird, kann doch die Überprüfung der Lösung nicht in polynomieller Zeit erfolgen? Es muß ja überprüft werden ob die geratene Lösung auch wirklich die beste ist! Gewissenermassen nochmal alles durchrechnen. Und das geht nur in EXP Zeit.

Viele Grüße

Ich

CStoll

NP geht zunächst von Entscheidungsproblemen aus, also in deinem Fall: Gegeben ist ein Graph und ein Wert n_min - gibt es eine Partitionierung des Graphen, bei der die Verbindungen zwischen den Teilen kleiner sind als n_min? Aber afaik kannst du mit polynomiellem Aufwand und einem Programm für das Entscheidungsproblem das zugehörige Optimierungs- (wie lang ist die kürzeste mögliche Verbindung?) bzw. Suchproblem (wie sieht die optimale Partinionierung aus?) lösen.

Bashar

Definiere den Begriff "beste Lösung". Dann bekommst du irgendeine Kostenfunktion. Jetzt iterierst du: Gibt es eine Lösung mit Kosten = 0? Gibt es eine Lösung mit Kosten = 1? etc. Klingt grausam, ergibt aber nur einen zusätzlichen linearen Faktor.

Sag ich mal so als Nicht-Informatiker.

Ist BTW beim TSP auch so.

Vielen Dank für die Hilfe. Dann ist "Suche die beste Lösung" doch in NP. Würde ich reelle Zahlen als Knoten- Kantengewichte verwenden wäre die Sache mathematisch schwieriger. Aber so genau muß ich das nicht nehmen. Die Präsentation über "unser" Problem muß ich vor E-Technikern/Maschbauer/BWLern halten. *g*

Christoph

Wenn du einen Graphen in nur zwei Partitionen zerlegen willst mit minimalen Verbindungskosten, eignet sich der Stör/Wagner-Algorithmus; ich weiß gerade nicht mehr die genaue Komplexität, die dürfte aber irgendwas in der Gegend O(V^2 * E) sein (V=Anzahl der Knoten, E=Anzahl der Kanten). Auf jeden Fall polynomiell, nicht exponentiell.

Wie du die Bedingung "möglichst gleich große Partitionen, aber minimale Verbindungskosten" genau meinst, ist mir allerdings nicht ganz klar. Der Stör/Wagner-Algorithmus minimiert jedenfalls die Verbindungskosten, achtet aber nicht auf die Anzahl der Knoten in einer der Partitionen.

Jester

In manchen Fällen ist es wichtig den Graphen so zu zerlegen, dass die entstehenden Teile in etwa gleich groß sind. In planaren Graphen geht sowas relativ gut. Aber die Teile wirklich gleichgroß zu machen *und* die Kosten des Schnitts zu minimieren, das klingt ziemlich schwer. Ich glaube eher nicht, dass das in allgemeinen Graphen in Polynomialzeit geht.

Für Partitionierungsprobleme gibt es Heuristiken aus Distributed Computing: PMetis, Scotch, Party, Chaco, ...

Christoph schrieb:

Wie du die Bedingung "möglichst gleich große Partitionen, aber minimale Verbindungskosten" genau meinst, ist mir allerdings nicht ganz klar.

Die Praktiker in unserer Firma sind gerade dabei den Knoten-Kanten Faktor herauszubekommen. Beispiel: Wenn in einer Partition 10 Knoten a 100 Kosten sind macht die Partitionsgröße 1000. Hinzukommen die Kanten die hinausführen. Diese Zahl wird mit dem Paxisfaktor von oben multipliziert und zu den 1000 hinzugezählt. Am Ende sollten am besten alle Partitionen exakt die gleiche Größe haben. Als Maß für die Gleichheit könnte man die Standardabweichung nehmen. Mathematisch gesehen sollte es dann mindesten eine optimale Lösung geben für die gilt des es keine optimalere gibt

Unter Stör/Wagner-Algorithmus habe ich jetzt nur den minimalen Schnitt gefunden?
http://wwwhni.uni-paderborn.de/~tamas/NW_WS02/nw09.pdf
http://www.informatik.uni-frankfurt.de/~erps/theoseminar.pdf
http://de.wikipedia.org/wiki/Schnitt_(Graphentheorie)

Der teilt zwar einen Graphen wenn der Schnitt entfernt wird, es wird aber keine Gleichverteilung vorgenommen...

Jester

Für ungewichtete planare Graphen gibt's das planar-separator-Theorem (gibt auch nen algorithmus dazu), der liefert was halbwegs vernünftiges. Inwiefern sich der auch auf Deine Problemstellung anwendne lässt weiß ich nicht.

Ich schaue es mir an. Vielen Dank