418
правок
Изменения
Нет описания правки
[[Эвристики для поиска кратчайших путей|Эвристическая функция]] <tex>h(s,s')</tex> теперь должна быть неотрицательная и выполнять неравенство треугольника, т.е.
<tex>h(s_{goal},s_{goal}) = 0</tex> и <tex>h(s, s_{goal}) <= \leqslant c(s,s') + h(s',s_{goal})</tex> для всех <tex>s \in SV</tex> и <tex>s' \in Succ(s)</tex>
Функция <tex>key(s)</tex>, где <tex>s</tex> - вершина, возвращает вектор из 2-ух значений <tex>k_1(s)</tex>, <tex>k_2(s)</tex>.
[[Эвристики для поиска кратчайших путей|Эвристическая функция]] <tex>h(s,s')</tex> теперь должна быть неотрицательная и обратно-устойчивая, т.е.
<tex>h(s_{start},s_{start}) = 0</tex> и <tex>h(s_{start}, s) <= \leqslant h(s_{start},s') + c(s',s)</tex> для всех <tex>s \in S</tex> и <tex>s' \in Pred(s)</tex>. Очевидно, что при движении робота <tex>s_{start}</tex> изменяется, поэтому данные свойства должны выполняться для всех <tex>s_{start} \in SV</tex>.
Дополнительное условие выхода также меняется, т.е. при <tex>g(s_{start}) = +\infty</tex> путь не найден на данной итерации. Иначе путь найден и робот может проследовать по нему.
Передвинулись вдоль найденного пути и изменили вершину <tex>s_{start}</tex>;
Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним.
if (если граф изменился)
for всех ориентированных ребер <tex>(u; v)</tex> с измененными весами:
Обновляем результат функции <tex>c(u; v)</tex>;
|statement=Функция '''ComputeShortestPath''' в данной версии алгоритма ''расширяет'' вершину максимум 2 раза, а именно 1 раз, если вершина ненасыщена, и максимум 1 раз, если она переполнена.
}}
== Описание (2 версия) ==
В первой версии алгоритма была серьезная проблема в том, что для каждой вершины в приоритетной очереди нужно было обновлять ключ суммарно за <tex>O(n \cdot log(n))</tex>. Это дорогая операция, так как очередь может содержать огромное число вершин. Воспользуемся оригинальным методом поиска и изменим преобразим основной цикл, чтобы избежать постоянного перестроения очереди <tex>U</tex>.
Теперь эвристическая функция должна поддерживать неравенство треугольника для всех вершин <tex>s,s',s'' \in V</tex>, т.е. <tex>h(s,s'') \leqslant h(s, s') + h(s',s'')</tex>. Так же должно выполняться свойство <tex>h(s,s') \leqslant c^*(s,s')</tex>, где <tex>c^*(s,s')</tex> - стоимость перехода по кратчайшему пути из <tex>s</tex> в <tex>s'</tex>, при этом <tex>s</tex> и <tex>s'</tex> не должны быть обязательно смежными. Такие свойства не противоречат свойствами из первой версии, а лишь усиливают их.
=== Псевдокод (Вторая версия) ===
'''CalcKey'''(s):
return [<tex>\min(g(s);rhs(s)) + h(s_{start};s) + K_m</tex>;<tex>\min(g(s); rhs(s))</tex>];
'''Initialize'''():
U = <tex>\varnothing</tex>;
<tex>K_m = 0</tex>
for <tex>s \in S</tex>
<tex>rhs(s) = g(s) = +\infty</tex>
<tex>rhs(s_{goal}) = 0</tex>
U.Insert(<tex>s_{goal}</tex>; CalcKey(<tex>s_{goal}</tex>));
'''UpdateVertex'''(u):
if (<tex>u \ne s_{goal}</tex>)
rhs(u) = <tex>min_{s' \in Succ(u)}(c(u,s')+g(s'));</tex>
if (<tex>u \in U</tex>)
U.Remove(u);
if (<tex>g(u) \ne rhs(u)</tex>)
U.Insert(u; CalcKey(u));
'''ComputeShortestPath'''():
while (U.TopKey() < CalcKey(<tex>s_{start}</tex>) OR <tex>rhs(s_{start}) \ne g(s_{start})</tex>)
<tex>K_{old} = U.TopKey()</tex>;
u = U.Pop();
if (<tex>K_{old}</tex> < CalcKey(<tex>u</tex>))
U.Insert(<tex>u</tex>;CalcKey(<tex>u</tex>));
if (g(u) > rhs(u))
g(u) = rhs(u);
for <tex>s \in Pred(u)</tex>
UpdateVertex(s);
else
g(u) = <tex>+\infty</tex>;
for <tex>s \in Pred(u) \cup \{u\}</tex>
UpdateVertex(s);
'''Main'''():
<tex>s_{last} = s_{start}</tex>
'''Initialize'''();
'''ComputeShortestPath'''();
while (<tex>s_{start} \ne s_{goal}</tex>)
// if (<tex>g(s_{start}) = \infty</tex>) тогда путь на данной итерации не найден.
<tex>s_{start}</tex> = такая вершина s', что <tex>min_{s' \in Succ(s_{start})}(c(s_{start}, s') + g(s'))</tex>
Передвинулись вдоль найденного пути и изменили вершину <tex>s_{start}</tex>;
Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним.
if (граф изменился)
<tex>K_m = K_m + h(s_{last}, h_{start})</tex>;
<tex>s_{last} = s_{start}</tex>;
for всех ориентированных ребер <tex>(u; v)</tex> с измененными весами:
Обновляем результат функции <tex>c(u; v)</tex>;
'''UpdateVertex'''(u);
ComputeShortestPath();
==Ссылки==
