Понимание алгоритма для проблемы АЗС

В задаче о заправке нам даны городов и дороги между ними. Каждая дорога имеет длину, и каждый город определяет цену на топливо. Одна единица дороги стоит одну единицу топлива. Наша цель - добраться от источника до места назначения самым дешевым способом. Наш танк ограничен какой-то ценностью.{ 0 , … , n - 1 $n$$\{ 0, \ldots, n-1 \}$

Я пытаюсь понять алгоритм , поэтому я вручную записал шаги для расчета решения. К сожалению, я застрял - в какой-то момент нет никаких краев для рассмотрения, я не знаю почему, может быть, я что-то упустил.

Пример:
дорога:
0 ----------- 1 ------------ 2 -------------- 3
(это не так должно быть так просто, это может быть любой график, т.е. могут быть дороги между 0-> 2, 0-> 3, 1-> 3 и т. д.)

Источник: 0, Назначение: 3, Бак: 10 единиц
Цены на топливо: 0 : 10 единиц, 1 : 10 единиц, 2 : 20 единиц, 3 : 12 единиц
Длина: 0-> 1 : 9 единиц, 1-> 2 : 1 единица, 2-> 3 : 7 единиц
Оптимальное решение: заполните 9 единиц по 0 и 8 единиц по 1. Общая стоимость тогда составляет 170 единиц (9 * 10 + 8 * 10).

Поэтому я попытался рассчитать его, как показано здесь (пункт 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?

Повторение из документа, кажется, не работает или, что более вероятно, я делаю что-то не так.

Может кто-нибудь помочь мне с этим?

Проблема заключается в том состоянии , для первого аргумента min()в уравнении (4) на стр. 7. Это в настоящее время

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

но это должно быть

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

к силе прибытию в т не имеет никакого газа остался. (Так же , как с моим объяснением ниже для ошибки в заполняющей Row (и, д), мы никогда и не заинтересованы в стоимости газа в т. И , как и там, еще один способ решить эту проблему будет перезапись с (т ) с 0 в начале алгоритма.)

Исправления этой ошибки (в опубликованном алгоритме) в сочетании с добавлением пропущенных ребер, как я опишу ниже (ваша ошибка :-P), должно быть достаточно, чтобы все заработало.

Одна вещь, которую вы упускаете, это то, что граф G должен быть полным (первое предложение в разделе 2, стр. 4) - и, если он не завершен, должны быть добавлены все пропущенные ребра с весами, найденными путем взятия минимальной длины пути в график. Так, например, в вашем примере графа должно быть (среди прочего) ребро от 1 до 3 с весом 8 (соответствует пути через 2), так что на самом деле GV [3] = {0, 2}.

Я не уверен, что это полностью решит проблему для вас, но это должно помочь.

Отдельно я думаю, что есть ошибка в алгоритме Fill-Row (u, q) на p. 6: этот алгоритм должен обрабатывать случай q = 1 специально, но это не так. Я считаю, что это можно исправить, изменив

if c(v) <= c(u)

на линии 3 до

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

заставить любой последний этап прибыть в пункт назначения пустым. (Интуитивно понятно, что мы всегда должны игнорировать цену газа в конечном пункте назначения, т.

Используя решение @j_random_hacker, нам нужно преобразовать наш граф в полный граф и изменить условие с уравнения (4) на:

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

Полный график должен выглядеть так:

и окончательные расчеты:

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

Путь через 0 -> 1 -> 3 [общая стоимость 170 $] является решением. Это то, что мы ожидали :-). Если нам нужен маршрут, то мы должны быть в состоянии преобразовать эти дополнительные ребра из решения в заданные ребра в начале (это не должно быть очень трудным).

Мне только интересно, как мы должны избегать тупиковых ситуаций в этом повторении. Например, может быть тупик между 0 <-> 1, потому что c (0) <= c (1) и c (1) <= c (0).

Идея состоит в том, чтобы получить топливо в соответствии с требованиями по самой низкой цене, где бы вы ни находились (парадигма жадного алгоритма)

Возьмите несколько примеров. в вашем примере

Источник: 0, Назначение: 3, Бак: 10 единиц Цены на топливо: 0: 10 единиц, 1: 10 единиц, 2: 20 единиц, 3: 12 единиц Длина: 0-> 1: 9 единиц, 1-> 2: 1 единица, 2-> 3: 7 единиц

Сначала мне нужно проехать 9 единиц, поэтому я должен заполнить свой танк до 0, набрав> = 9 единиц (вместимость> = 9). Теперь на 1,2,3 я вижу расход топлива> = расход топлива на 0. Как, я хочу купить необходимое топливо по самой низкой цене, я постараюсь заполнить 9 + 1 + 7 = 17 единиц в только город 0 Но вместимость бака может быть <17, скажем, 10. Итак, я буду заполнять до 10. Тогда на 1 у меня останется 1 единица топлива, и мне придется пересечь еще 8 единиц, поэтому на 1 я буду заполнять 7 единиц больше. Я не могу заполнить в 2, потому что ставка будет выше. Моя общая стоимость = 10 * 10 + 7 * 10 = 170.

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

я) полный = 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$