Zrozumienie algorytmu problemu ze stacją benzynową

W przypadku problemu ze stacją benzynową podajemy miast i drogi między nimi. Każda droga ma długość, a każde miasto określa cenę paliwa. Jedna jednostka drogi kosztuje jedną jednostkę paliwa. Naszym celem jest przejście ze źródła do miejsca docelowego w najtańszy możliwy sposób. Nasz czołg jest ograniczony pewną wartością.{ 0 , … , n - 1 $n$$\{ 0, \ldots, n-1 \}$

Próbuję zrozumieć algorytm , więc ręcznie zapisałem kroki, aby obliczyć rozwiązanie. Niestety utknąłem - w pewnym momencie nie ma żadnych krawędzi do rozważenia, nie wiem dlaczego, może coś mi brakuje.

Przykład:
droga:
0 ----------- 1 ------------ 2 -------------- 3
(nie ma muszą być tak proste, może to być dowolny wykres, tzn. mogą istnieć drogi między 0-> 2, 0-> 3, 1-> 3 itd.)

Źródło: 0, Miejsce docelowe: 3, Zbiornik: 10 jednostek
Ceny paliw: 0 : 10 jednostek, 1 : 10 jednostek, 2 : 20 jednostek, 3 : 12 jednostek
Długości: 0-> 1 : 9 jednostek, 1-> 2 : 1 jednostka, 2-> 3 : 7 jednostek
Optymalne rozwiązanie: napełnij 9 jednostek przy 0 i 8 jednostek przy 1. Całkowity koszt to wtedy 170 jednostek (9 * 10 + 8 * 10).

Próbowałem więc obliczyć, jak pokazano tutaj (akapit 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?

Wydaje się, że powtarzanie się dokumentu nie działa lub, co bardziej prawdopodobne, robię coś złego.

Czy ktoś mógłby mi w tym pomóc?

Problem polega na tym, że pierwszy argument min()podany w równaniu (4) na str. 7. Jest obecnie

c(v) <= c(u) and g < d[u][v]

ale powinno być

(c(v) <= c(u) or v = t) and g < d[u][v]

aby wymusić przybycie do t, aby nie pozostało gazu. (Tak jak w przypadku mojego wyjaśnienia poniżej dotyczącego błędu w Fill-Row (u, q), nigdy nie jesteśmy zainteresowani kosztem gazu w t. I tak jak w tym przypadku, innym sposobem rozwiązania problemu byłoby zastąpienie c (t ) z 0 na początku algorytmu).

Naprawienie tego błędu (w opublikowanym algorytmie) w połączeniu z dodaniem brakujących krawędzi, jak opiszę poniżej (twój błąd :-P), powinno wystarczyć, aby wszystko działało.

Jedną z rzeczy, których brakuje, jest to, że wykres G musi być kompletny (pierwsze zdanie w sekcji 2, s. 4) - a jeśli nie jest kompletny, należy dodać wszelkie brakujące krawędzie, a ciężary można znaleźć, przyjmując minimalną długość ścieżki w wykres. Tak więc np. Na twoim przykładowym wykresie powinna istnieć (między innymi) krawędź od 1 do 3 o wadze 8 (odpowiadającej ścieżce przez 2), tak że w rzeczywistości GV [3] = {0, 2}.

Nie jestem pewien, czy to całkowicie rozwiąże problem, ale powinno to pomóc.

Osobno myślę, że jest błąd w algorytmie Fill-Row (u, q) na p. 6: ten algorytm powinien specjalnie traktować przypadek q = 1, ale tak nie jest. Wierzę, że można to naprawić, zmieniając

if c(v) <= c(u)

na linii 3 do

if c(v) <= c(u) or q = 1

aby zmusić ostatnią nogę do dotarcia do miejsca docelowego pustą. (Intuicyjnie powinniśmy zawsze lekceważyć cenę gazu w miejscu docelowym, t.) Innym sposobem byłoby zastąpienie c (t) wartością 0 na początku.

Korzystając z rozwiązania @j_random_hacker, musimy przekształcić nasz wykres w pełny wykres i zmienić warunek z równania (4) na:

(c(v) <= c(u) or v = t) and g < d[u][v]     

Pełny wykres powinien wyglądać następująco:

i końcowe obliczenia:

GV[0] = {0}, GV[1] = {0}, GV[2] = {0, 3, 9}, GV[3] = {0, 2}

D(0,0) = min { D(1,0) + 9 * 10 }
D(1,0) = min { D(2,9) + 10 * 10, D(3,0) + 8*10 }
D(3,0) = 0
... etc

so D(0,0) = 170

Ścieżka przez 0 -> 1 -> 3 [całkowity koszt 170 $] jest rozwiązaniem. Tego się spodziewaliśmy :-). Jeśli potrzebujemy trasy, powinniśmy być w stanie przekształcić te dodatkowe krawędzie z rozwiązania na dane krawędzie na początku (nie powinno to być bardzo trudne).

Zastanawiam się tylko, jak powinniśmy unikać martwych pętli w tym nawrocie. Na przykład może wystąpić martwy punkt między 0 <-> 1, ponieważ c (0) <= c (1) ic (1) <= c (0).

Chodzi o to, aby uzyskać paliwo zgodnie z wymaganiami w najtańszej stawce, gdziekolwiek się znajdziesz (chciwy paradygmat algorytmu)

Weź kilka przykładów. w twoim przykładzie

Źródło: 0, Miejsce docelowe: 3, Zbiornik: 10 jednostek Ceny paliw: 0: 10 jednostek, 1: 10 jednostek, 2: 20 jednostek, 3: 12 jednostek Długości: 0-> 1: 9 jednostek, 1-> 2: 1 jednostka, 2-> 3: 7 jednostek

Najpierw muszę podróżować 9 jednostek, więc muszę napełnić mój zbiornik przy 0> = 9 jednostek (pojemność> = 9). Teraz widzę, że przy 1,2,3 stawka paliwa wynosi> = stawka paliwa przy 0. Ponieważ chcę kupić potrzebne paliwo po najtańszej cenie, postaram się uzupełnić 9 + 1 + 7 = 17 jednostek przy tylko miasto 0. Ale pojemność zbiornika może wynosić <17, powiedzmy 10. Więc napełnię się do 10. Wtedy przy 1 mam 1 jednostek paliwa i muszę przejść 8 jednostek więcej, więc przy 1 uzupełnię 7 jednostki więcej. Nie mogę wypełnić 2, ponieważ stawka byłaby wyższa. Mój całkowity koszt = 10 * 10 + 7 * 10 = 170.

$C_i$$d_{ij}$$i$$j$

i) pełny = 0

$i=0$$n-1$$l$$i$$C_i > C_l$$l$$l=n-1$$d_l$$l$$\sum_{k=i+1}^l d_{k,k+1}$$\min$$d_l -$$i$$\min$$d_l -$$i=l$