418
правок
Изменения
→Описание (2 версия)
Теперь эвристическая функция должна поддерживать неравенство треугольника для всех вершин <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> не должны быть обязательно смежными. Такие свойства не противоречат свойствами из первой версии, а лишь усиливают их.
=== Псевдокод (Вторая версия) ===
'''UpdateVertex'''(u);
ComputeShortestPath();
=== Пример работы ===
{| class="wikitable"
|-
| style="width:50%;text-align:center;" | [[Файл:Схема_движения_робота_Dstarv2_1.png|350px]] || style="width:50%;text-align:center;" | [[Файл:Схема_движения_робота_Dstarv2_2.png|350px]]
|-
| style="width:50%;text-align:center;" | Итерации в функции '''ComputeShortestPath''' на исходном графе. || style="width:50%;text-align:center;" | Итерации в функции '''ComputeShortestPath''' после изменения графа. (Второй вызов функции)
|}
==Ссылки==
