418
правок
Изменения
м
Теперь на основе LPA* опишем алгоритм D*Дан [[Основные определения теории графов|взвешенный ориентированный граф]] <tex> G(V, который способен определять расстояние между текущей вершиной E) </tex>. Даны вершины <tex>s_{start}</tex>, в которой, допустим, находится курсор/робот, и конечной вершиной <tex>s_{goal}</tex> при каждом изменении графа . Требуется в то время, как наш робот движется вдоль найденного процессе движения по кратчайшему путив графе <tex>G</tex> обновлять значения функции <tex>g(s)</tex> при поступлении новой информации о графе <tex>G</tex>.
→Алгоритм D* (Первая версия)
=== Постановка задачи ===
Теперь на основе LPA* опишем алгоритм D*, который способен определять расстояние между текущей вершиной <tex>s_{start}</tex>, в которой, допустим, находится способный к сканированию местности "робот", и конечной вершиной <tex>s_{goal}</tex> при каждом изменении графа в то время, как наш "робот" движется вдоль найденного пути. [[Файл:Схема_движения_робота_Dstar.png|350px|thumb|right|Схема движения курсора/"робота " в процессе работы алгоритма D*. Информация о серых клетках ему неизвестна до определенной итерации.]]
=== Описание ===
<tex>h(s_{start},s_{start}) = 0</tex> и <tex>h(s_{start}, s) \leqslant 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 V</tex>.
Дополнительное условие выхода также меняется, т.е. при <tex>g(s_{start}) = +\infty</tex> путь не найден на данной итерации. Иначе путь найден и "робот " может проследовать по нему.
'''Примечание''': Так же следует отметить, что функция '''Initialize''' не обязана инициализировать абсолютно все вершины перед стартом алгоритма. Это важно, так как в на практике число вершин может быть огромным , и только немногие будут пройдены робот роботом в процессе движения. Так же это дает возможность добавления/удаления ребер без потери устойчивости всех подграфов данного графа.
=== Псевдокод ===
При такой постановке задачи псевдокод не сильно меняется. Но , но функция '''Main''' все-таки претерпевает значительные изменения.
'''CalcKey'''(s):
