418
правок
Изменения
Нет описания правки
* Обозначим множество <tex>Pred(s) \subseteq V</tex> как множество вершин, входящих в вершину <tex>s</tex>.
Функция <tex>0 \leqslant c(s, s') \leqslant +\infty</tex> будет возвращать стоимость перехода из вершины ребра (<tex>sss'</tex> в вершину ). При этом <tex>c(s, s') = +\infty</tex>. При этом будет тогда и только тогда, когда ребра (<tex>sss' \in Succ(s)</tex>) не существует.
{{Определение
{{Теорема
|statement=После выполнения функции '''ComputeShortestPath''' можно проследить восстановить путь из <tex>f</tex> в <tex>t</tex>. Для этого, начиная с вершины <tex>t</tex>, нужно постоянно передвигаться к такой вершине <tex>s'</tex>, входящей в <tex>t</tex>, чтобы <tex>g(s') + c(s',s)</tex> было минимальным, до тех пора, пока не будет достигнута вершина <tex>f</tex>.
|proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf]
}}
Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь вычисляет длину кратчайшего пути между вершинами <tex>f</tex> и <tex>t</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n \cdot m \cdot \log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite.
'''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку <tex>O(n \cdot \log(n))</tex>.
== Алгоритм D* (Первая версия) ==
Пока что был описан только алгоритм LPA*. Он способен неоднократно определять находит кратчайшее расстояние между начальной и конечной вершинами при любом изменении данного графа. Его первоначальный поиск полностью совпадает с алгоритмом A*, но последующие итерации способны использовать информацию из предыдущих поисков.
=== Постановка задачи ===
Теперь на основе LPA* опишем алгоритм D*, который способен определять расстояние между текущей вершиной <tex>f</tex>, в которой, допустим, находится способный к сканированию местности "робот", и конечной вершиной <tex>t</tex> при каждом изменении графа в то время, как наш "робот" движется вдоль найденного пути.
[[Файл:Схема_движения_робота_Dstar.png|350px|thumb|right|Схема движения "робота" в процессе работы алгоритма D*. Информация о серых клетках ему неизвестна до определенной итерациитех пор, пока они не попадут в его зону обзора. В данном примере зона обзора составляет 1 клетку в 8-ми направлениях.]]
=== Описание ===
'''UpdateVertex'''(u);
'''ComputeShortestPath'''();
=== Асимптотика ===
С помощью введения ключевого модификатора <tex>K_m</tex> и отложенного обновления ключей вершин получилось убрать из каждой итерации алгоритма <tex>O(n \cdot \log(n))</tex> операций, которые тратились на обновление очереди <tex>U</tex>. Очевидно, что на основе теорем, приведенных выше алгоритм использовал <tex>O(2 \cdot n \cdot \log(n))</tex> операций. Итак, нам удалось уменьшить константу в 2 раза, что дает существенный рост производительности на практических задачах.
=== Пример работы ===
