Weg des Handlungsreisenden mit Laster und diversen Guetern

[Zweipunktnull]

Es ist noch immer sehr mühselig, sich in den Thread hineinzudenken, da immer noch sehr schwamming und händewedelnd diskutiert wird. Ich versuche mal (für mich) etwas Klarheit in die Sache zu bringen.

Gegeben ist also oBdA ein vollständiger (!) Graph G=(V,E), wobei jeder Knoten eine Stadt repräsentiert und jede Kante einen kürzesten Weg zwischen ihren beiden Endpunkten (bzgl. der Metrik Reisezeit). Sind zwei Städte nicht erreichbar, so besitzt die entsprechende Kante einfach Reisezeit unendlich. Zusätzlich ist jede Kante mit "ihrem Profit" gelabelt. Jede Kante e=(u,v) unterliegt also eine 2-dim. Bewertung c : e -> (t, p), wobei t die Länge eines kürzesten Weges (in sec.) zwischen u und v ist und p die Differenz (Verkaufspreis in v - Einkaufspreis in u)*LKW-Größe bzgl. des optimalen Guts auf e ist. OBdA ist das Ganze deshalb, weil wir uns einen solchen vollständigen Graphen inkl. der Bewertungsfunktion berechnen können, sollten wir nur ein normales Straßennetz gegeben haben.

Gesucht ist nun ein (nicht notwendigerweise zyklenfreier) Pfad, so dass (a) die Summe der c(e).t aller Kanten e auf dem Pfad kleiner-gleich 3h ist und (b) die Summe der c(e).p maximiert wird. Der Pfad muss dabei nicht notwendigerweise geschlossen sein.

Legt man dieses Verständnis zugrunde, sehe ich im Moment nicht, inwiefern deine Lösung (daemon) das Problem löst (kann auch an mir legen ). So wie ich das Verstehe, entspricht deine Funktion Profit(u, v) = c((u,v)).p, oder? Mir ergeben sich nun mehrere Fragen. Zum einen wird der Zeitconstraint bei dir irgendwie nicht (direkt) berücksichtigt. Weiterhin ist zu bedenken, dass eine Kante e mit hohem c(e).p nicht unbedingt "gut" sein muss. Man muss dies ja immer auch in Relation zur Reisezeit c(e).t setzen. Daneben ist zu bedenken, dass selbst eine Kante e*=(u,v), die maximalen Profit pro Zeit verspricht (d.h. c(e*).p / c(e*).t ist am höchsten unter allen Kanten e in E), nicht unbedingt in der Lösung sein muss. Denn möglicherweise geht es nach v nur noch mit kaum Profit weiter, sodass ein Pfad ohne e* ingesamt (eben auf die <= 3h gesehen) besser ist.

Mich würde interessieren, was du dazu sagst. Hab ich dich irgendwo falsch verstanden?

Edit: Btw:

Wenn man natürlich einen optimalen Kreis sucht wird das Ganze wieder aufwendiger (wenn auch nicht NP-vollständig).

Was wäre denn dein Algorithmus dafür? Ich frag nur, weil du dann die P-NP-Frage beantwortet hättest. LONGEST CYCLE ist mindestens so schwer (EDIT: ok, es ist leicht einzusehen, dass es exakt genauso schwer ist) wie HAMILTONIAN CYCLE, was wiederum eines der klassischen 21 NP-vollständigen Probleme ist.

 

[Ochse]

@Zweipunktnull
Genau genommen hängt die Bewertung c : e -> (t, p) auch noch von der Richtung ab, behaupte ich jedenfalls.

@daemon777
Ich sehe auch nicht was du meinst. Das ist alles etwas zu wage für mich, um es zu verstehen.

 

[Zweipunktnull]

Üblicherweise modelliert man Straßennetze als gerichtete Graphen. Und die Kante (u,v) kann natürlich eine andere Bewertung haben als die Kante (v,u).

 

[Ochse]

Joo das ist mir schon klar.

Ich glaube nicht, dass uns der Formalismus hier beim Lösen des Problems weiterhilft, außer vielleicht beim Erkennen, dass die Aufgabe schwer zu bewältigen ist .
Aber das war den Meisten sicher auch schon vorher klar.

Vermutlich wird sich niemand die Mühe machen einen Lösungsalgorithmus zu finden und der Thread wird ergebnisoffen bleiben.

 

[Zweipunktnull]

Dann wärs aber kein vollständiger Graph bzw. man würde ihn nicht so nennen.

Vollständigkeit ist auch für gerichtete Graphen definiert. Siehe einschlägige Literatur.

Etwas Formalismus hilft auf jeden Fall, um überhaupt mal die Ausgangsfrage zu verstehen. Wie gesagt, bisher versteht hier offensichtlich jeder etwas anderes darunter. Und das die Schwierigkeit des Problems den meisten schon klar ist, dass bezweifel ich ebenfalls. Sonst wären ja nicht schon ein paar Algorithmen gepostet worden.

 

[Ochse]

Ich kann mich nicht erinnern diesen Satz je geschrieben zu haben .
Hast natürlich Recht. Mit der Zeit schwand ein bisschen graphentheoretisches Wissen aus meinem Gedächnis.

 

[daemon777]

@Zweipunktnull
Ich werde mir deinen Post nochmal nüchtern durchlesen müssen, deshalb hier nur eine kurze Antwort. Am Anfang hatte ich es so verstanden, dass er nur den nächsten Schritt bei einer gegebenen Stadt berechnen will, was aber natürlich Unsinn wäre. Deshalb habe ich dann mit der Annahme, dass wir nur einen Pfad (keinen Kreis) suchen den Algo aufgeschrieben habe. Bei den Edits habe ich ja darauf hingewiesen, dass dies das Problem nicht wirklich löst. Den Profit habe ich einfach berechnet als Erlös(Lasterinhalt) - Kosten(Lasterinhalt) - Wegkosten(Pfad). Das lässt sich so einfach rechnen, weil ich ja immer nur ein Gut von A nach B transportiere. Weitere Überlegungen hierzu auszuführen macht aber denke ich keinen Sinn, denn das Problem ist ja hier, wie gesagt, damit nicht gelöst. Pfad <> Kreis. Leider

Es wäre jetzt einfach eine gute Lösung zu berechnen. Allerdings ist hier die Fragestellung ja: "optimale Lösung". Das wird dann tatsächlich langsam etwas schwieriger. Weiterhin habe ich das Problem so verstanden, dass ich einen Kreis finden will, den ich immer wieder abfahren kann. Also müsste es schon ein geschlossener Pfad sein. Somit brauche ich auch keinen Hamillton Kreis. Das Problem mit dem Kreis maximaler Länge ist auch nicht identisch mit dem Problem, das ich hier lösen will. Schließlich brauche ich keinen Kreis, der maximal viele Knoten durchläuft, sondern einen Kreis, der mir die Profit-Funktion auf seinen Kanten maximiert. Dennoch ist das Problem verdächtig ähnlich zu den NP-vollständigen.

Ich werde mir hierzu nochmal weiter Gedanken machen, ob mich meine bisherigen Überlegungen irgendwo hinführen (sind jedoch jetzt vollständig Andere als hier vorher beschrieben, da Kreis <> Pfad ).

Falls das allgemeine Problem jedoch tatsächlich NP-vollständig sein sollte ist das jedoch noch kein Untergang, da man hier ein paar weitere Annahmen treffen kann. Bei einer großen Menge an Städten (und 100-200 ist groß) sollte die Anzahl an Kanten vergleichsweise gering sein. Da der Graph vermutlich auch gegeben ist (davon gehe ich mal aus) und wir das Problem nicht allgemein lösen müssen haben wir einen Graphen von beschränktem Grad. Wenn ich mich recht erinnere war es der Satz von Sese, der besagt, dass es dann einen Polynomialzeitalgorithmus gibt, um das Problem zu lösen. Aber das hängt eben dann davon ab, ob der Graph gegeben ist oder nicht. Die Annahme, dass wir einen beschränkten Grad haben halte ich jedoch für sinnig.
Weiterhin gibt es vielleicht Knoten und Kanten, die man schnell ausschließen kann (Knoten mit Grad 1 und keinen preiswerten Gütern als einfaches Beispiel). Eventuell haben wir ja sogar richtig Glück und Teile des Graphen entsprechen einer Baumstruktur oder die Baumähnlichkeit ist hoch? Das sind jetzt aber zugegebenermaßen eher Fragestellungen, wo ich nicht so große Hoffnung habe

Zur P = NP Frage: die lässt sich nicht ganz so leicht beantworten

 

[Ochse]

Glaube nicht der der Threadersteller einen konkreten Graphen/Städteverbund im Sinn hatte. So ist jedenfalls mein Eindruck nachdem ich mir, aus lauter Langeweile, alles nochmal durchgelesen habe. Es ist also von irgendeinem allgemeinen Graphen auszugehen.

Die Annahme, dass wir einen beschränkten Grad haben halte ich jedoch für sinnig.

Weiß nicht, Zweipunktnull (was für ein Name ) ist ja von kürzesten Wegen ausgangen d.h. vollst. Graphen (man muss u.U. durch Stadt B um von Stadt A nach zu C gelangen), was mir in meinem jetzigen Zustand sinnvoll erscheint.

Da ich ein bisschen Zweifel, dass ich der Threadersteller nochmal blicken lässt, hier mal ein ganz einfacher Vorschlag für einen Graphen:

Eine ringförmige Anordnung von Städten/Knoten die sich in beide Richtungen befahren lässt.

 

[Zweipunktnull]

Das Problem mit dem Kreis maximaler Länge ist auch nicht identisch mit dem Problem, das ich hier lösen will. Schließlich brauche ich keinen Kreis, der maximal viele Knoten durchläuft, sondern einen Kreis, der mir die Profit-Funktion auf seinen Kanten maximiert.

Wie du schon vermutet hast, sind diese ganzen hier erwähnten Probleme mit den Kreisen sehr ähnlich und insbesondere alle NP-vollständig. Die Beweise sind jeweils extrem simpel und so kurz, dass ich sie grad runtertippen kann.

Sei A ein Algorithmus, der in einem Graphen G einen Kreis C findet, sodass die Summe der Bewertungen der Kanten e in C maximal wird (das ist quasi das, was du machen wolltest, wenn ich das richtig sehe). Nennen wir das Problem mal LONGEST WEIGHTED CYCLE. Um nun zu zeigen, dass LONGEST WEIGHTED CYCLE mindestens so schwer wie LONGEST CYCLE (= Kreis mit max. vielen Knoten) ist, müssen wir also jede Instanz von LONGEST CYCLE unter Zuhilfenahme des Algorithmus A effizient lösen können. Das ist nicht schwer:

Gegeben sei ein Graph G, indem wir den Kreis mit den meisten Knoten finden sollen. Dann setzen wir einfach alle Kantengewichte in Linearzeit auf 1 und führen Algorithmus A auf diesem modifizieren Graphen aus. Der längeste gewichtete Kreis ist nun per Konstruktion automatisch auch der mit den meisten Knoten. Also gilt, dass LONGEST WEIGHTED CYCLE gerade NP-schwer ist. Darüber hinaus ist es NP-vollständig, da für die Entscheidungsvariante des Problems kurze Zeugen angegeben werden können.

Noch simpler ist die Reduktion von HAMILTONIAN CYCLE auf LONGEST CYCLE: Wenn der Kreis, den uns unser Algorithmus für LONGEST CYCLE zurück liefert gerade genauso viele Knoten enthält, wie im Graph vorhanden sind, dann gibts einen Hamiltonkreis. Wenn nicht, nicht.

Die restlichen Reduktionen bis hin zu SAT glauben wir mal Herrn Karp.

Zur P = NP Frage: die lässt sich nicht ganz so leicht beantworten

Wie meinst du das? Wenn du tatsächlich einen effizienten Algorithmus zum Finden optimaler Kreise im Graphen gefunden hättest (wie behauptet ), dann wäre die Frage gelöst gewesen.

Zum Knotengrad hat Ochse ja schon was gesagt: Da wir zwischen allen Städte-Paaren optimale Strecken berechnen, erhalten wir einen vollständigen Graphen, indem der Knotengrad bekanntlich linear wächst.

Um aber mal was für meine Bildung zu tun: Was ist der Satz von Sese? Google scheint ihn auch nicht zu kennen...

EDIT: Btw:

Da der Graph vermutlich auch gegeben ist (davon gehe ich mal aus) und wir das Problem nicht allgemein lösen müssen

Algorithmen für einzelne Probleminstanzen zu entwickeln, ist ja voll die Schummelei. Dann fällt ja auch die gesamte Komplexitätstheorie in sich zusammen. Soll nur eine Instanz gelöst werden, so berechnen wir uns die Lösungen mit beliebig viel Zeit in einem Preprocessing und kodieren sie dann hart in den "Algorithmus". Somit wird jedes Problem effizient lösbar. Eigentlich mehr noch, selbst unlösbare Probleme werden lösbar, wenn man sich auf endlich viele Instanzen beschränkt. So kann man z.B. ein Programm entwickeln, dass das Halteproblem auf den "ersten" 1000 Instanzen löst (bzgl. irgendeiner naheliegenden Ordnung), ihm man einfach diese 1000 Lösungen ins Programm hart kodiert. Insofern ist die Lösung einzelner Instanzen irgendwie ziemlich unlustig. Kurzum: Der Graph ist natürlich gegeben, aber es ist eben ein beliebiger Graph gegeben.

 

[voon]

Es wird langsam schwierig fuer mich, euch noch zu folgen Aber ich glaub zu "gegebenem Graphen" kann ich was sagen. Typische Spacesim Karten sehen so ca so aus (hier eine Babylon 5 Karte):



Die Verbindungen stellen dabei die vorhandenen Sprungtore fuer Hyperjumps dar - dh man kann nicht von ueberall irgendwohin fliegen, sondern muss diesen Kanten folgen.

 

[daemon777]

Wie meinst du das? Wenn du tatsächlich einen effizienten Algorithmus zum Finden optimaler Kreise im Graphen gefunden hättest (wie behauptet ), dann wäre die Frage gelöst gewesen.

Wenn wir einen polynomialzeit Algorithmus für ein NP-vollständiges Problem finden ist die Aussage korrekt. Da ich aber davon ausgehe, dass wir hier keinen beliebigen Graphen haben zweifel ich noch daran, dass das hier der Fall ist. Ich kann mir zB nicht vorstellen, dass es eine Stadt gibt, die direkt mit 100 anderen verbunden ist.

Zur Knotengradfrage: Es kann nicht wirklich zielführend sein aus einer dünnbesetzen Adjazenzmatrix erstmal einen vollständigen Graphen zu berechnen.

Um aber mal was für meine Bildung zu tun: Was ist der Satz von Sese? Google scheint ihn auch nicht zu kennen...

Algorithmen für einzelne Probleminstanzen zu entwickeln, ist ja voll die Schummelei. Dann fällt ja auch die gesamte Komplexitätstheorie in sich zusammen. Soll nur eine Instanz gelöst werden, so berechnen wir uns die Lösungen mit beliebig viel Zeit in einem Preprocessing und kodieren sie dann hart in den "Algorithmus". Somit wird jedes Problem effizient lösbar. Eigentlich mehr noch, selbst unlösbare Probleme werden lösbar, wenn man sich auf endlich viele Instanzen beschränkt. So kann man z.B. ein Programm entwickeln, dass das Halteproblem auf den "ersten" 1000 Instanzen löst (bzgl. irgendeiner naheliegenden Ordnung), ihm man einfach diese 1000 Lösungen ins Programm hart kodiert. Insofern ist die Lösung einzelner Instanzen irgendwie ziemlich unlustig. Kurzum: Der Graph ist natürlich gegeben, aber es ist eben ein beliebiger Graph gegeben.

Naja das kommt ganz darauf an. Wir können zB einen Algorithmus für eine Subklasse von Graphen entwickeln. UGraphs ist ja zB auch eine Unterklasse von Graphs. Wenn wir jetzt annehmen können, dass wir zB ein Grid gegeben haben statt einem allgemeinen Graphen verändert das doch die Problemstellung. Ich gehe weiterhin davon aus, dass wir einen beschränkten Grad im Ausgangsproblem haben. Auch wenn die Anzahl der Städte wächst, so ist es unwahrscheinlich, dass die Anzahl an Straßen für eine beliebige Stadt unendlich wachsen kann.

Zu Sese: ja auf google habe ich ihn auch gerade nicht gefunden. Da werde ich mal in meinen Skripten nachschauen, ob ich den wiederfinde (oder falls ich mich im Namen geirrt habe den richtigen Namen).

Noch kurz zum Beweis: wenn ich einfach Katengewichte auf 1 setze ist die Ausgabe für die beiden Probleme nicht mehr unbedingt identisch. Dann wäre ein Kreis der Länge 4 immer größer als ein Kreis der Länge 3 und zwar unabhängig von den Gewichten der Kante. Allerdings lässt sich das zugegebenermaßen leicht beheben:
Sei g das Gewicht einer Kante (x,y). Dann ersetzen wir die gewichtete Kante im Ursprungsgraph durch einen Pfad der Länge g, indem wir g Knoten einfügen und jeweils mit dem Vorgänger verbinden. Am Ende wird noch die Kante (zg, y) eingefügt, um den Pfad komplett zu machen.

EDIT: Hier ist mir noch was aufgefallen. Die Reduktion fällt hier doch nicht so leicht, da unsere Kanten durchaus eine negative Ausgabe für die Gewichtsfunktion bekommen können. Da wir aber keinen negativen Pfad erhalten können funktioniert die Reduktion so direkt leider nicht.
Würden wir dennoch versuchen auf ein MAX-CIRCLE-Problem zu reduzieren, so ist die Ausgabe eventuell falsch und somit unsere Reduktion nicht geglückt. Der NPC-Beweis steht also leider doch noch aus.

EDIT2: Verdammt! Ich habe mal wieder bei der Reduktion falschrum gedacht
Dann stimmt der Beweis natürlich doch *schäm*

Allerdings habe ich ja schon zugegeben, dass mein anfänglich hier geposteter Algo nicht für Kreise sondern nur für Wege gedacht war. Für Kreise müssen wir uns wohl oder übel etwas anderes überlegen oder die reale Laufzeit durch irgendwelche Tricks drücken. Wenn alles nichts hilft müssen wir halt eine gute Lösung statt einer Optimalen ausgeben.


EDIT: Der Kerl heißt Seese. Aber den richtigen Satz habe ich noch nicht gefunden. Es gibt noch einen anderen Satz von Seese, aber der spricht über MSO und nicht über Graphentheorie. Da muss ich wohl nochmal das (handgeschriebene -.-) Skript durchblättern.

Abgesehen davon wird uns das aber wohl leider doch nicht großartig weiterhelfen, wenn ich mir hier die Beispielskarte mal anschaue o.O Da habe ich wirklich in eine etwas andere Richtung gedacht.

Ergänzung (15. Juni 2014)

Jetzt habe ich den Satz gefunden, den ich gesucht habe, aber die Erinnerung war leider doch nicht ganz so gut, wie gedacht. Und zwar besagt der Satz, dass es für jeden FO-Satz auf relationalen Strukturen mit beschränktem Grad einen polynomialzeit-Algorithmus zum Lösen des Problems gibt. Jetzt lässt sich leicht ein Satz angeben, dass es einen Kreis der Länge 3,4,5 oder anderer Konstanten gibt, aber eben nicht für beliebig lange Kreise.
Wir könnten also hier in dem Fall nur ein lokales Problem lösen und damit wäre das Problem sowieso in P.

Das ist jetzt schon ein schwerer Rückschlag finde ich, da der Graph auch noch wesentlich zufälliger ist, als ich vermutet habe.

Ich fürchte einen effizienten Algorithmus zu finden, der garantiert die optimale Lösung ausgibt ist somit unmöglich geworden.

Achja was ich gesucht habe war das hier: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.9462

 

[Zweipunktnull]

Ich kann mir zB nicht vorstellen, dass es eine Stadt gibt, die direkt mit 100 anderen verbunden ist.

Die Anzahl der Kanten dürfte so auf den ersten Blick ohnehin nicht übermäßig relevant sein. In einem Graphen mit beschränktem Knotengrad wächst die Anzahl Kanten linear, in einem vollständigen Graphen wächst sie ja allerdings auch nur quadratisch und damit insbesondere polynomiell. Wenn wir also einen polynomiellen Algorithmus für ersteren Fall haben, läuft der i.d.R. auch auf vollständigen Graphen in Polynomialzeit. Das gilt zumindest für alle klassischen Graphen-Algorithmen, die einem so spontan einfallen: Dijkstra, Jarnik-Prim, Bellman, Kruskal, Floyd-Warshall etc. Natürlich, wenn man aus irgendeinem Grund an jedem einzelnen Knoten einen Aufwand hat, der exponentiell im jeweiligen Knotengrad ist, dann gilt das nicht mehr unbedingt. Aber da wär mir jetzt ehrlichgesagt gar keine Algorithmus bekannt.

Gut, ansonsten ging's mir nur darum aufzuzeigen, dass das Ganze nicht so einfach ist, wie teilweise angenommen wurde. Die Muße und Zeit, da jetzt ernsthaft einen Polynomialzeit-Algorithmus für zu finden oder - alternativ - ein NP-vollständiges Problem darauf zu reduzieren, habe ich ehrlich gesagt nicht.

Wenn man es exakt lösen will, dann sollte das gefühlt mit Integer Linear Programming möglich sein. Für eine heuristische Lösung sind gefühlt evolutionäre Algorithmen gut geeignet (die funktionieren zumindest beim TSP ziemlich gut und eine gewisse Ähnlichkeit gibt's ja schon zwischen beiden Problem).