418
правок
Изменения
Нет описания правки
Очевидно, что если все вершины насыщены, то мы можем найти расстояние от стартовой вершины до любой. Такой граф будем называть устойчивым (насыщенным).
[[Эвристики для поиска кратчайших путей|Эвристическая функция]] <tex>h(s,s')</tex> теперь должна быть неотрицательная и выполнять неравенство треугольника, т.е.
<tex>h(s_{goal},s_{goal}) = 0</tex> и <tex>h(s, s_{goal}) <= c(s,s') + h(s',s_{goal})</tex> для всех <tex>s \in S</tex> и <tex>s' \in Succ(s)</tex>
Функция <tex>key(s)</tex>, где <tex>s</tex> - вершина, возвращает вектор из 2-ух значений <tex>k_1(s)</tex>, <tex>k_2(s)</tex>.
Теперь функция g(s) хранит минимальное известное расстояние от <tex>s_{goal}</tex> до <tex>s</tex>. Свойства остаются прежними.
[[Эвристики для поиска кратчайших путей|Эвристическая функция ]] <tex>h(s,s') </tex> теперь должна быть неотрицательная и обратно-устойчивая, т.е.
<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>.
* [http://en.wikipedia.org/wiki/D* Wikipedia:D*]
* [http://idm-lab.org/project-a.html Sven Koenig` web page]
* [http://www.cs.cmu.edu/~maxim/files/aij04.pdf LPA*]* [http://pub1.willowgarage.com/~konolige/cs225b/dlite_tro05.pdfD* lite]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах ]]
