Изменения

Перейти к: навигация, поиск

Алгоритм D*

332 байта добавлено, 16:32, 10 января 2014
м
Нет описания правки
|about=О монотонности изменения ключей
|statement=В течение выполнения функции '''ComputeShortestPath''' вершины, взятые из очереди, монотонно не убывают.
|proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf]
}}
|about=О необратимой насыщенности
|statement=Если в функции '''ComputeShortestPath''' была взята переполненная вершина, то на следующей итерации она станет насыщенной.
|proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf]
}}
{{Теорема
|statement=После выполнения функции '''ComputeShortestPath''' можно проследить путь из <tex>f</tex> в <tex>t</tex>. Для этого, начиная с вершины <tex>t</tex>, нужно постоянно передвигаться к такой вершине <tex>s'</tex>, входящей в <tex>t</tex>, чтобы <tex>g(s') + c(s',s)</tex> было минимальным, до тех пора, пока не будет достигнута вершина <tex>f</tex>.
|proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf]
}}
|about=Об устойчивой насыщенности вершин
|statement=Функция '''ComputeShortestPath''' в данной версии алгоритма ''расширяет'' вершину максимум 2 раза, а именно 1 раз, если вершина ненасыщена, и максимум 1 раз, если она переполнена.
|proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf]
}}
418
правок

Навигация