Im Tankstellenproblem erhalten wir Städte und Straßen zwischen ihnen. Jede Straße hat eine Länge und jede Stadt definiert den Preis des Kraftstoffs. Eine Straßeneinheit kostet eine Kraftstoffeinheit. Unser Ziel ist es, auf möglichst günstige Weise von einer Quelle zu einem Ziel zu gelangen. Unser Tank ist durch einen gewissen Wert begrenzt.
Ich versuche, den Algorithmus zu verstehen , also habe ich die Schritte zur Berechnung der Lösung manuell aufgeschrieben. Leider blieb ich stecken - irgendwann gibt es keine Kanten mehr zu berücksichtigen, ich weiß nicht warum, vielleicht fehlt mir etwas.
Beispiel:
Straße:
0 ----------- 1 ------------ 2 -------------- 3
(nicht) muss so einfach sein, es könnte jeder Graph sein, dh es könnte Straßen zwischen 0-> 2, 0-> 3, 1-> 3 usw. geben)
Quelle: 0, Ziel: 3, Tank: 10 Einheiten
Kraftstoffpreise: 0 : 10 Einheiten, 1 : 10 Einheiten, 2 : 20 Einheiten, 3 : 12 Einheiten
Längen: 0-> 1 : 9 Einheiten, 1-> 2 : 1 Einheit, 2-> 3 : 7 Einheiten
Optimale Lösung: 9 Einheiten zu 0 und 8 Einheiten zu 1 füllen. Die Gesamtkosten betragen dann 170 Einheiten (9 * 10 + 8 * 10).
Also habe ich versucht, es wie hier gezeigt zu berechnen (Absatz 2.2)
GV[u] is defined as:
GV[u] = { TankCapacity - length[w][u] | w in Cities and fuelPrice[w] < fuelPrice[v] and length[w][u] <= TankCapacity } U {0}
so in my case:
GV[0] = {0}
GV[1] = {0}
GV[2] = {0, 3, 9}
GV[3] = {0}
D(u,g) - minimum cost to get from u to t starting with g units of fuel in tank:
D(t,0) = 0, otherwise:
D(u,g) = min (foreach length[u][v] <= TankCapacity)
{
D(v,0) + (length[u][v] - g) * fuelPrice[u] : if fuelPrice[v] <= fuelPrice[u] and g <= length[u][v]
D(v, TankCapacity - length[u][v]) + (TankCapacity - g) * fuelPrice[u] : if fuelPrice[v] > fuelPrice[u]
}
so in my case:
D(0,0) = min { D(1,0) + 9*10 } - D(0,0) should contain minimum cost from 0->3
D(1,0) = min { D(2,9) + 10*10 } - in OPT we should tank here only 8 units :(
D(2,9) = min { ??? - no edges which follows the condition from the reccurence
Nevertheless D(0,0) = 90 + 100 + smth, so it's already too much.
To achieve the optimal solution algorithm should calculate D(2,7) because the optimal route is:
(0,0) -> (1,0) -> (2, 7) -> (3, 0) [(v, g): v - city, g - fuel in tank].
If we look at G[2] there is no "7", so algorithm doesn't even assume to calculate D(2,7),
so how can it return optimal solutions?
Die Wiederholung aus dem Dokument scheint nicht zu funktionieren oder was wahrscheinlicher ist, dass ich etwas falsch mache.
Könnte mir jemand dabei helfen?
quelle
Mit der @ j_random_hacker-Lösung müssen wir unseren Graphen in einen vollständigen Graphen umwandeln und die Bedingung von Gleichung (4) in Folgendes ändern:
Das vollständige Diagramm sollte folgendermaßen aussehen:
und endgültige Berechnungen:
Pfad durch 0 -> 1 -> 3 [Gesamtkosten 170 $] ist die Lösung. Das haben wir erwartet :-). Wenn wir eine Route benötigen, sollten wir in der Lage sein, diese zusätzlichen Kanten von der Lösung zu Beginn in die angegebenen Kanten umzuwandeln (dies sollte keine große Schwierigkeit sein).
Ich frage mich nur, wie wir bei dieser Wiederholung Deadloops vermeiden sollten. Zum Beispiel kann es einen Deadloop zwischen 0 - 1 geben, weil c (0) <= c (1) und c (1) <= c (0).
quelle
Die Idee ist, den Kraftstoff nach Bedarf zum günstigsten Preis zu erhalten, wo immer Sie ihn haben (Paradigma des gierigen Algorithmus).
Nehmen Sie einige Beispiele. in deinem Beispiel
Quelle: 0, Ziel: 3, Tank: 10 Einheiten Kraftstoffpreise: 0: 10 Einheiten, 1: 10 Einheiten, 2: 20 Einheiten, 3: 12 Einheiten Längen: 0-> 1: 9 Einheiten, 1-> 2: 1 Einheit, 2-> 3: 7 Einheiten
Ich muss zuerst 9 Einheiten fahren, also muss ich meinen Tank bei 0 mit> = 9 Einheiten füllen (Kapazität> = 9). Jetzt kann ich bei 1,2,3 sehen, dass die Kraftstoffmenge> = Kraftstoffmenge bei 0 ist. Da ich meinen benötigten Kraftstoff zum günstigsten Preis kaufen möchte, werde ich versuchen, 9 + 1 + 7 = 17 Einheiten bei zu tanken Stadt 0 nur. Aber die Kapazität des Tanks könnte <17 sein, sagen wir 10. Also werde ich bis 10 tanken. Dann habe ich bei 1 1 Einheit Kraftstoff übrig und ich muss 8 Einheiten mehr durchqueren, also fülle ich bei 1 7 Einheiten mehr. Ich kann nicht bei 2 tanken, weil die Rate höher wäre. Meine Gesamtkosten = 10 * 10 + 7 * 10 = 170.
i) voll = 0
quelle