Zrozumienie algorytmu problemu ze stacją benzynową

11

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,,n1}

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?

Wojciech Kulik
źródło

Odpowiedzi:

7

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.

j_random_hacker
źródło
Oprócz uważności na to, co dzieje się dla , musisz również wypełnić tabelę znaczącymi wartościami, gdy w wewnętrznej pętli zabraknie elementów. Co więcej, jeśli czytam to poprawnie, algorytm wydaje się całkowicie ignorować przypadek (por. To pytanie CS SE ), więc należy coś z tym zrobić. c ( v ) > c ( u )q=1do(v)>do(u)
fuglede
2

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:

wprowadź opis zdjęcia tutaj

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).

Wojciech Kulik
źródło
W celu odniesienia w przyszłości zobacz ten meta post :-)
Juho
1

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.

dojarejajotjajot

i) pełny = 0

ja=0n-1ljadoja>dolll=n-1rellk=ja+1lrek,k+1minrel-jaminrel-ja=l

Sayan Bandyapadhyay
źródło
Dziękuję za Twoją odpowiedź! Niestety nie określiłem się wystarczająco jasno. Zakładałeś, że wykres będzie tak prosty jak mój przykład, ale może to być dowolny wykres, tzn. Mogą też istnieć drogi 0-> 2, 1-> 3 itd.
Wojciech Kulik
Tak, ponieważ nie wspomniałeś, że wcześniej założyłem, że wszystkie miasta są połączone liniowo (wykres jest prostą ścieżką).
Sayan Bandyapadhyay