418
правок
Изменения
Нет описания правки
Аналогично множество <tex>Pred(s) \in V</tex> как множество вершин, входящих в вершину <tex>s</tex>.
Функция <tex>0 \lessgtr leqslant с(s, s') \lessgtr leqslant +\infty</tex> будет возвращать стоимость перехода из вершины <tex>s</tex> в вершину <tex>s'</tex>. При этом <tex>s' \in Succ(s)</tex>.
Функция <tex>g(s)</tex> будет возвращать последнее известное (и самое минимальное) значение расстояния от вершины <tex>s_{start}</tex> до <tex>s</tex>.
:<tex dpi="120">rhs(s) = 0</tex>
Иначе
:<tex dpi="120">rhs(s) = min_{s' \in predPred(s)}(g(s') + c(s', s)</tex>
Вершина <tex>s</tex> может быть 3-х видов:
Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь между вершинами <tex>s_{start}</tex> и <tex>s_{goal}</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n^2 \dot log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite.
'''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку О(n*\dot log(n)).
== Алгоритм D* ==
Пока что был описан только алгоритм LPA*. Он способен неоднократно определять кратчайшее расстояние между начальной и конечной вершинами при любом изменении данного графа. Его первоначальный поиск полностью совпадает с алгоритмом A*, но последующие итерации способны использовать информацию из предыдущих поисков.
=== Постановка задачи ===
Теперь на основе LPA* опишем алгоритм D*, который способен определять расстояние между текущей вершиной <tex>s_{start}</tex>, в которой, допустим, находится курсор/робот, и конечной вершиной <tex>s_{goal}</tex> при каждом изменении графа в то время, как наш робот движется вдоль найденного пути.
=== Описание ===
Опишем первую версию алгоритма D*. Очевидно, что большинство вершин в процессе движения робота остаются неизменными, поэтому мы можем применить алгоритм LPA*.
'''Примечание''': Большинство функций переходят в данный алгоритм без изменений, поэтому опишем только измененные части.
Для начала мы поменяем направление поиска в графе.
Теперь функция g(s) хранит минимальное известное расстояние от <tex>s_{goal}</tex> до <tex>s</tex>. Свойства остаются прежними.
Эвристическая функция h(s,s') теперь должна быть неотрицательная и обратно-устойчивая, т.е.
<tex>h(s_{start},s_{start}) = 0</tex> и <tex>h(s_{start}, s) <= 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 S</tex>.
Дополнительное условие выхода также меняется, т.е. при <tex>g(s_{start}) = +\infty</tex> путь не найден на данной итерации. Иначе путь найден и робот может проследовать по нему.
=== Псевдокод (Первая версия) ===
При такой постановке задачи псевдокод не сильно меняется. Но функция '''Main''' все-таки претерпевает значительные изменения.
'''CalcKey'''(s):
return [<tex>\min(g(s);rhs(s)) + h(s_{start};s)</tex>;<tex>\min(g(s); rhs(s))</tex>];
'''UpdateVertex'''(u):
if (<tex>u != \ne s_{goal}</tex>)
rhs(u) = min_{s' \in Succ(u)}(c(u,s')+g(s'));
if (<tex>u \in U</tex>)
U.Remove(u);
if (<tex>g(u) != \ne rhs(u)</tex>)
U.Insert(u; CalcKey(u));
<tex>s_{start}</tex> = такая вершина s', что <tex>min_{s' \in Succ(s_{start})}(c(s_{start}, s') + g(s'))</tex>
Передвинулись вдоль найденного пути и изменили вершину <tex>s_{start}</tex>;
if (если граф изменился)
for всех ориентированных ребер <tex>(u; v)</tex> с измененными весами:
