Изменения
→Алгоритм D* (Вторая версия)
Теперь эвристическая функция должна поддерживать неравенство треугольника для всех вершин <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> не должны быть обязательно смежными. Такие свойства не противоречат свойствами из первой версии, а лишь усиливают их.
Допустим, что после того, как робот продвинется вдоль найденного пути на предыдущих итерациях, из вершины s в s', он обнаружит изменения в графе. Первая компонента ключей <tex>k_1(s')</tex> может уменьшится максимум на <tex>h(s,s')</tex> (по определению ключа). Вторая компонента не зависит от функции h. Аналогично первой версии алгоритма, мы должны уменьшить первую компоненту ключа у всех вершин в очереди U. Очевидно, что <tex>h(s,s')</tex> будет одинаковым для всех вершин из U. Порядок в очереди не изменится, если произвести уменьшение. Следовательно уменьшение можно отложить, тем самым очередь не придется перестраивать на каждой итерации. Так же исходя из нового определения функции h, её значение будет всегда меньше, чем разность первых компонент ключей у соседних по приоритету вершин. Таким образом мы можем добавлять h(s,s') ко всем <tex>k_1(s')</tex> у ключей вершин из U.
Будем называть <tex>K_m</tex> ключевым модификатором. В нем мы и будет хранить сумму h(s,s'), которые нужно добавить ко всем вершинам из U.
=== Псевдокод ===
'''CalcKey'''(s):
return [<tex>\min(g(s);rhs(s)) + h(f;s) + <tex>K_m</tex>;<tex>\min(g(s); rhs(s))</tex>];
'''Initialize'''():
U = <tex>\varnothing</tex>;
<tex>K_m = 0</tex>
for s <tex>s \in S</tex>V <tex>rhs(s) = g(s) = <tex>+\infty</tex> <tex>rhs(t) = 0</tex> U.Insert(<tex>t</tex>; CalcKey(<tex>t</tex>));
'''UpdateVertex'''(u):
if (u <tex>u \ne t</tex>t)
rhs(u) = <tex>\min\limits_{s' \in Succ(u)}(c(u,s')+g(s'));</tex>
if (u <tex>u \in U</tex>U)
U.Remove(u);
if (<tex>g(u) <tex>\ne </tex> rhs(u)</tex>)
U.Insert(u; CalcKey(u));
'''ComputeShortestPath'''():
while (U.TopKey() < CalcKey(<tex>f</tex>) OR <tex>rhs(f) <tex>\ne </tex> g(f)</tex>) <tex>K_{old} </tex> = U.TopKey()</tex>;
u = U.Pop();
if (<tex>K_{old}</tex> < '''CalcKey'''(<tex>u</tex>)) U.Insert(<tex>u</tex>; '''CalcKey'''(<tex>u</tex>));
if (g(u) > rhs(u))
g(u) = rhs(u);
for s <tex>s \in </tex> Pred(u)</tex>
UpdateVertex(s);
else
g(u) = <tex>+\infty</tex>;
for s <tex>s \in </tex> Pred(u) <tex>\cup \{u\}</tex> {u}
'''UpdateVertex'''(s);
'''Initialize'''();
'''ComputeShortestPath'''();
while (f <tex>f \ne t</tex>t) // if (<tex>g(f) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.
<tex>f</tex> = такая вершина s', что <tex>\min\limits_{s' \in Succ(f)}(c(f, s') + g(s'))</tex>
Передвинулись вдоль найденного пути и изменили вершину <tex>f</tex>;
