418
правок
Изменения
→Описание (2 версия)
== Описание (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> не должны быть обязательно смежными. Такие свойства не противоречат свойствами из первой версии, а лишь усиливают их.
[[Файл:Схема_движения_робота_Dstarv2_1.png|350px|thumb|right|Итерации в функции '''ComputeShortestPath''' на исходном графе.]]
[[Файл:Схема_движения_робота_Dstarv2_2.png|350px|thumb|right|Итерации в функции '''ComputeShortestPath''' после изменения графа. (Второй вызов функции)]]
=== Псевдокод (Вторая версия) ===
