418
правок
Изменения
Нет описания правки
* ненасыщена, если <tex>g(s) < rhs(s)</tex>
Очевидно, что если все вершины насыщены, то мы можем найти расстояние от стартовой вершины до любой. Такой граф будем называть устойчивым (насыщенным).
Функция <tex>key(s)</tex>, где <tex>s</tex> - вершина, возвращает вектор из 2-ух значений <tex>k_1(s)</tex>, <tex>k_2(s)</tex>.
* <tex>k_1(s) = min(g(s), rhs(s)) + h(s, s_goals_{goal})</tex>.
* <tex>k_2(s) = min(g(s), rhs(s))</tex>.
Дополнительное условие выхода также меняется, т.е. при <tex>g(s_{start}) = +\infty</tex> путь не найден на данной итерации. Иначе путь найден и робот может проследовать по нему.
'''Примечание''': Так же следует отметить, что функция '''Initialize''' не обязана инициализировать абсолютно все вершины перед стартом алгоритма. Это важно, так как в на практике число вершин может быть огромным и только немногие будут пройдены робот в процессе движения. Так же это дает возможность добавления/удаления ребер без потери устойчивости всех подграфов данного графа.
=== Псевдокод (Первая версия) ===
'''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);
