418
правок
Изменения
м
→Алгоритм LPA*
=== Постановка задачи ===
Дан [[Основные определения теории графов|взвешенный ориентированный граф]] <tex> G(V, E) </tex>. Даны вершины : стартовая вершина <tex>f</tex> и конечная вершина <tex>t</tex>. Требуется после каждого изменения графа <tex>G</tex> уметь вычислять функцию <tex>g(s)</tex> для каждой известной вершины <tex>s \in V</tex>
=== Описание ===
Функция <tex>g(s)</tex> будет возвращать последнее известное (и самое минимальное) значение расстояния от наименьшую стоимость пути из вершины <tex>f</tex> до в <tex>s</tex>. Её значение для алгоритма будет почти аналогичным значению в [[Алгоритм A* | алгоритме A*]], за исключением того, что в данном алгоритме наc интересуют только <tex>g(s)</tex>-значения известных вершин на данной итерации.
Будем поддерживать для каждой вершины два вида смежных с ней вершин:
return [min(g(s); rhs(s)) + h(s; t); min(g(s); rhs(s))];
// Обновляет данные вершины в соответствие с данными выше определениями. Также поддерживает инвариант того, что в очереди U лежат только ненасыщенные вершины.
'''UpdateVertex'''(u):
if u <tex>\ne</tex> f
