418
правок
Изменения
м
Теперь опишем {{Определение|definition=Будем называть '''rhs-значением''' (''right-hand side value'') такую функцию <tex>rhs(s)</tex>. Эта функция будет использовать минимальные расстояние из минимальных расстояний от <tex>s_{start}</tex> до вершин, входящих в данную вершины <tex>s</tex>. Потенциально это и которая будет нам давать информацию о возвращать потенциальное минимальное расстояние от <tex>s_{start}</tex> до <tex>s</tex>.по следующим правилам:
Функция {{Определение|definition=Будем называть '''ключом''' вершины такую функцию <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>s</tex> - вершина из множества <tex>V</tex>}}
→Описание
=== Описание ===
Функция <tex>g(s)</tex> будет возвращать последнее известное (и самое минимальное) значение расстояния от вершины <tex>s_{start}</tex> до <tex>s</tex>. Её значение будет почти аналогичным значению в [[Алгоритм A* | алгоритме A*]], за исключением того, что в данном алгоритме нам наc интересуют только <tex>g(s)</tex> -значения известных вершин на данной итерации.
Будем поддерживать для каждой вершины два вида смежных с ней вершин:
Функция <tex>0 \leqslant c(s, s') \leqslant +\infty</tex> будет возвращать стоимость перехода из вершины <tex>s</tex> в вершину <tex>s'</tex>. При этом <tex>s' \in Succ(s)</tex>.
<tex>rhs(s) =
\begin{cases}
\end{cases}
</tex>
Так как rhs-значение использует минимальное значение из минимальных расстояний от <tex>s_{start}</tex> до вершин, входящих в данную вершину <tex>s</tex>, это будет нам давать информацию об оценочном расстоянии от <tex>s_{start}</tex> до <tex>s</tex>.
}}
{{Определение|definition=Вершина <tex>s</tex> может быть 3-х видов:* насыщенаназывается '''насыщенной''' (''locally consistent''), если <tex>g(s) = rhs(s)</tex>* переполнена}} {{Определение|definition=Вершина <tex>s</tex> называется '''переполненной''' (''locally overconsistent''), если <tex>g(s) > rhs(s)</tex>* ненасыщена}} {{Определение|definition=Вершина <tex>s</tex> называется '''ненасыщенной''' (''locally underconsistent''), если <tex>g(s) < rhs(s)</tex>}}
Очевидно, что если все вершины насыщены, то мы можем найти расстояние от стартовой вершины до любой. Такой граф будем называть устойчивым (насыщенным).
<tex>h(s_{goal},s_{goal}) = 0</tex> и <tex>h(s, s_{goal}) \leqslant c(s,s') + h(s',s_{goal})</tex> для всех <tex>s \in V</tex> и <tex>s' \in Succ(s)</tex>
Если в конце поиска пути <tex>g(s_{goal}) = +\infty</tex>, то мы не смогли найти путь от <tex>s_{start}</tex> до <tex>s_{goal}</tex> на текущей итерации. Но после следующего изменения графа путь вполне может найтись.
