418
правок
Изменения
Нет описания правки
Функция <tex>key(s)</tex>, где <tex>s</tex> - вершина, возвращает вектор из 2-ух значений <tex>k_1(s)</tex>, <tex>k_2(s)</tex>.
* <tex>k_1(s) = \min(g(s), rhs(s)) + h(s, s_{goal})</tex>. * <tex>k_2(s) = \min(g(s), rhs(s))</tex>.
Если в конце поиска пути <tex>g(s_{goal}) = +\infty</tex>, то мы не смогли найти путь от <tex>s_{start}</tex> до <tex>s_{goal}</tex> на текущей итерации. Но после следующего изменения графа путь вполне может найтись.
Теперь опишем составные элементы подробнее
Функция инициализации исходного графа устанавливает для всех вершин кроме стартовой (<tex>s_{start}</tex>) значения <tex>g(s)</tex> и <tex>rhs(s)</tex> равными бесконечности. Для стартовой <tex>g(s_{start})=0</tex>. Очевидно, что минимальное расстояние от стартовой вершины до самой себя должно быть равным 0, но <tex>rhs(s_{start})=+\infty</tex>. Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь.
'''Initialize'''():
{
U.Insert(<tex>s_{start}</tex>; CalcKey(<tex>s_{start}</tex>));
}
//Функция <tex>key(s)</tex>. Возвращаемые значения сортируются в лексографическом порядке, т.е. сначала <tex>k_1(s)</tex>, потом <tex>k_2(s)</tex>
}
// Функция неоднократно перерасчитывает значение <tex>g(s)</tex> у ненасыщенных вершинв неубывающем порядке их ключей. Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины.
'''ComputeShortestPath'''():
{
