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 }
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?
źródło
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:
Pełny wykres powinien wyglądać następująco:
i końcowe obliczenia:
Ś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).
źródło
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.
i) pełny = 0
źródło