Fischerproblem

Hallo,

wie würdet ihr folgendes Problem lösen?
http://www.spoj.pl/problems/FISHER/

Kurzzusammenfassung:
Typisches Problem der kombinatorischen Optimierung: Wegfindung mit minimalen Kosten. Jedoch steht nur eine gewisse Zeit t für den Weg zur Verfügung und ein kostengünstiger Weg kann t überschreiten.
Im Prinzip werden die Kantengewichte im Graph also als Tupel (Zeit,Kosten) modelliert.

Nun überlege ich, wie man das effizient löst.
Vielleicht ein modifizierter Dijkstra? Jedoch scheint ein Greedy-Algorithmus hier Fehl am Platz, weil doch die optimale Lösung sich später als zeitüberschreitend herausstellen könnte.

Jester

Dijkstra passt im Prinzip, allerdings mußt du für jeden Knoten das Paar aus Weglänge und Kosten speichern und evtl. Mehrere Paare für jeden Knoten vorhalten. Wenn die zeit zu groß ist kannst du abschneiden, und wenn du für einen knoten werte (a,b) und (c,d) hast mit a<=c und b<=d, dann kannst du (c,d) entfernen, weil es nicht zu einer besseren Lösung führt.

Danke.
Mir ist nur nicht klar, wie ich die bis zum Knoten K benötigte Zeit sinnvoll speichere.

Ging es darum, die Zeit zu minimieren, wäre es vielleicht einfacher, aber prinzipiell ist die Zeit ja egal, so lange sie kein vorgegebenes Maximum überschreitet. Beispiel:
Ist die Maximalzeit 9, so ist ein Pfad P mit (Kosten = 12, Zeit = 9) immernoch besser als (Kosten = 11, Zeit = 4).

Also muss ich pro Knoten k die Zeit einsehen können, die man von einem gegeben Pfad, welcher am Startpunkt anfängt, bis zu k gebraucht hat.
Zunächst dachte ich, ich könne ja einfach pro Knoten eine Liste aus Tupel (Vorgänger, Zeit) speichern.
Aber das funktioniert nicht, denn in einem Knoten VOR dem Vorgänge könnte es ja schon beliebig viele Wegeaufspaltungen gegeben haben, sodass ich vielleicht mit einem falschen Zeitwert arbeite.

Letztlich müsste ich also für jeden bisher besuchten Pfad eine Zeit abspeichern.

Irgendwelche Ideen?

Jester

LOLAlter schrieb:

Ging es darum, die Zeit zu minimieren, wäre es vielleicht einfacher, aber prinzipiell ist die Zeit ja egal, so lange sie kein vorgegebenes Maximum überschreitet. Beispiel:
Ist die Maximalzeit 9, so ist ein Pfad P mit (Kosten = 12, Zeit = 9) immernoch besser als (Kosten = 11, Zeit = 4).

Das verstehe ich nicht. Er will doch die Kosten minimieren, da sind Kosten 11 doch besser als Kosten 12. Und da die Zeit auch nich geringer ist dominiert die zweite Lösung die erste -- sie kann also ignoriert werden.

Ja, zu schnell abgeschickt, meinte es natürlich so wie du.

Das Problem, um das es mir geht ist aber, wie man die Zeit für einen Pfad speichert.

Michael E.

Edit: Müll.

Vielleicht noch eine Anmerkung, um mein gedankliches Problem zu verdeutlichen:

Wenn ich einen Knoten besuche, brauche ich die Zeit, die bis dahin verstrichen ist. Ich könnte das jetzt pro Knoten k abspeichern, etwa als Liste: benötigte Zeit t bis k von Vorgänger k' aus.

Wir gehen also vom Hafen nach Staat 1, von Staat 1 zu Staat 2.
In Staat 2 speichere ich, wie lange ich gebraucht habe, um von Staat 1 aus nach Staat 2 zu fahren. Soweit so gut!
Das funktioniert aber nur so lange, wie der Pfad vom Hafen zu Staat 1 eindeutig ist. Wenn ich dazwischen noch einen Umweg fahren kann, ist die Zeit nicht mehr eindeutig und meine weitere Betrachtung wird falsch.

Das ist mein Problem mit dem Dijkstra-Ansatz, weil der Dijkstra keinen Pfad am Stück verfolgt, für den man die Zeit hochrechnen könnte. Viel mehr wird ja ein Teilgraph G' stückchenweise generiert, und es werden immer nacheinandere die aktuellen "Peripherieknoten" (Randknoten des Teilgraphs) betrachtet.

Jester

Du speicherst Dir bei jedem Knoten eine Menge von möglichen Ankünften, jede besteht dabei aus einem Tupel (a,b), wobei a die Zeit bis dahin ist und b die Kosten sind. Wenn Du an einem Knoten zwei Tupel (a,b) und (c,d) hast mit a <=c und b<=d, dann ist der erste Weg offensichtlich in allen Belangen besser und dominiert den zweiten, der muß daher nicht mehr verfolgt werden. Es ist aber durchaus möglich, dass Du einen Knoten mit mehreren Labels hast -- eben anders als beim Disjkstra-Algorithmus, weil dort die Labels ja total geordnet sind und man immer nur das kleinste aufhebt.

Wenn Du jetzt einen Knoten u neu labelst mit (a,b), dann schaust Du alle seine Nachbarkanten. Sei e so eine Kante, die zu v führt und Kosten (c,d) hat. Dann hast Du ein neues Label (a+c,b+d) für v gefunden, das Du von v aus weiter propagieren kannst -- wie im Dijkstra ja auch. Damit das nicht ganz so lange dauert kannst Du eben dominierte Labels wegwerfen und Labels verwerfen, bei denen die Zeit überschritten wird. Danach hast Du an jedem Knoten alle Pareto-optimalen Kostenpaare stehen mit denen dieser Knoten vom Startknoten aus erreicht werden kann.

Versuch evtl. mal zu vergessen, dass der Dijkstra "zufällig" auch einen Suchbaum mit aufbaut. Im Prinzip merkt er sich nur einen Vorgänger und mit welchen Kosten er ankommt. Analog dazu speicherst Du jetzt halt mehrere mögliche Kosten für jeden Knoten und für jeden dieser Werte einen eigenen Vorgänger. Wenn Du dich dann am Schluß entschieden hast kannst Du dann indem Du rückwärts zu den entsprechenden Vorgängern gehst auch den Weg auspacken. Du hältst letzlich aber ein ganzes Netzwerk von möglichen Suchpfaden vor.

Jester schrieb:

Du speicherst Dir bei jedem Knoten eine Menge von möglichen Ankünften, jede besteht dabei aus einem Tupel (a,b), wobei a die Zeit bis dahin ist und b die Kosten sind.

Jester schrieb:

Wenn Du jetzt einen Knoten u neu labelst mit (a,b),

Wie passt das zusammen? Was ist im zweiten Zitat (a,b)?
Wie du selbst schreibst, muss ich eine Liste halten.
Ich gehe von v nach v'.
Für v habe ich bspw. m Tupel ZEIT x KOSTEN x VORGAENGER
(z1, k1, v1)
(z2, k2, v2)
...
(z_m, k_m, v_m).

Um ein Tupel für v' mit Kosten k' und Zeit t' zu erstellen, muss ich nun ein solches Element (^z, ^k, ^v) aus meiner Tupelmenge von v auswählen und
^z + t', ^k + k' bilden.
Ein entsprechendes Tupel kann ich aber nicht wählen, weil mir ^v grad nicht bekannt ist. Der Dijkstra verfolgt ja wie gesagt keinen Pfad sondern "springt" zwischen den möglichen Pfaden hin- und her (im Prinzip führt er ja eine Breitensuche aus).

Hab grad einen ziemlichen Knoten im Kopf und glaube mich sehr dumm anzustellen. Bin im 2. Semester Informatik und mir geht es auf den Geist, dass ich bei Abweichungen der 0815-Fälle aus den Vorlesungen sofort Lösungsschwierigkeiten bekomme. Der Dijkstra an sich bzw. Kruskal f. minimale Spannbäume waren kein Problem. Jetzt kommt noch ein Constraint hinzu und ich bin mit dem Latein am Ende. Deshalb will ich mich unbedingt an solchen Problemen üben.

Jester

Vielleicht ist Dijkstra auch nicht ganz das perfekte Stichwort. Probiers mal mit Bellman-Ford. Jeder Knoten hat ein Label, initial ist das ∞.

Der Prozess wird angestoßen, indem das Labels des Startknotens auf 0 gesetzt wird.
Jedesmal wenn sich das Label eines Knotens ändert, schaut man sich alle Nachbarn des Knotens an und updated deren Labels -- allerdings nur wenn sich dadurch ein besseres Label, also eines mit kürzerer tenativer Distanz ergibt. Um den Pfad auch rekonstruieren zu können, merkt man sich an jedem Knoten für jedes Label über welchen Vorgänger das Label erhalten wurde.

Genau das gleiche machst Du jetzt auch, nur dass Knoten mehrfache Labels haben können, und Labels, die dominiert werden, entfernt werden -- Du hast also wirklich eine Liste von Labels an jedem Knoten. Wenn Du das durchziehst bleiben Dir am Schluß an jedem Knoten die Pareto-optimalen Lösungen übrig -- probier das evtl. einfach mal zuerst aus! Danach kannst Du noch leicht einbauen, dass Suchwege die die Maximalzeit überschreiten abgebrochen werden, das hält die Labelzahl kleiner.

Jester

Jester schrieb:

Wenn Du jetzt einen Knoten u neu labelst mit (a,b),

Wie passt das zusammen? Was ist im zweiten Zitat (a,b)?
Wie du selbst schreibst, muss ich eine Liste halten.
Ich gehe von v nach v'.
Für v habe ich bspw. m Tupel ZEIT x KOSTEN x VORGAENGER
(z1, k1, v1)
(z2, k2, v2)
...
(z_m, k_m, v_m).
[/quote]

Also betrachten wir eine Kante von v nach v', diese benötigt Zeit z und Kosten k.
Die neuen möglichen Label für v' sind (z_1+z,k_1+z,v),...,(z_m+z,k_m+z,v). Das kann man so erstmal hinschreiben. Die kommen jetzt für v' alle neu dazu. Damit der Rechenaufwand nicht ins unermessliche steigt (kann er trotzdem), verwerfen wir Labels, fall wir rausfinden dass v' schon ein Label hat, das in beiden Kategorien besser ist, ansonsten wird das Label hinzugefügt und evtl. werden dadurch noch wieder Nachbarn von v' upgedated.

Yay, der letzte Tipp (dass natürlich alle Verbindungen von v auf den nächsten Knoten v' weitergeführt werden müssen), hat es mir erlaubt, einen Algorithmus zu formulieren,
dessen Laufzeit aber noch nicht gerade der Brenner ist. Aber ich habe zumindest mal eine Basis.

Vielen Dank, Jester.