Последовательная эвристика

При изучении задач поиска пути в искусственном интеллекте эвристическая функция называется последовательной или монотонной , если ее оценка всегда меньше или равна предполагаемому расстоянию от любой соседней вершины до цели плюс стоимость достижения тот сосед.

Формально, для каждого узла N и каждого преемника P из N предполагаемая стоимость достижения цели из N не превышает стоимость шага достижения P плюс расчетная стоимость достижения цели из P . То есть:

$h(N)\leq c(N,P)+h(P)$ и

$h(G)=0.\,$

где

• h — непротиворечивая эвристическая функция
• N — любой узел графа
• P — любой потомок N
• G — любой целевой узел
• c(N,P) — стоимость достижения узла P из N

Неформально, каждый узел i даст оценку, которая с учетом стоимости достижения следующего узла всегда меньше или равна оценке в узле i+1 .

Последовательная эвристика также допустима , т. е. она никогда не переоценивает стоимость достижения цели (обратное , однако, не всегда верно). Предполагая, что ребра неотрицательны, это легко доказать по индукции .

Позволять $h(N_{0})=0$ быть ориентировочной стоимостью целевого узла. Это означает, что базовое условие тривиально истинно при 0 ≤ 0. Поскольку эвристика непротиворечива, $h(N_{i+1})\leq c(N_{i+1},N_{i})+h(N_{i})\leq c(N_{i+1},N_{i})+c(N_{i},N_{i-1})+...+c(N_{1},N_{0})+h(N_{0})$ путем расширения каждого члена. Указанные сроки равны реальной стоимости, $\sum _{i=1}^{n}c(N_{i},N_{i-1})$, поэтому любая непротиворечивая эвристика также допустима, поскольку она ограничена истинной стоимостью.

Обратное утверждение явно неверно, поскольку мы всегда можем построить эвристику, которая всегда будет ниже истинной стоимости, но, тем не менее, несовместима, например, увеличивая эвристическую оценку от самого дальнего узла по мере приближения и, когда оценка $h(N_{i})$ становится максимум истинной стоимостью $h^{*}(N_{i})$, мы делаем $h(N_{i-1})=h(N_{i})-c(N_{i},N_{i-1})$.

Последствия монотонности

Сравнение допустимой, но противоречивой и непротиворечивой эвристической функции оценки.

Непротиворечивые эвристики называются монотонными, потому что предполагаемая конечная стоимость частичного решения $f(N_{j})=g(N_{j})+h(N_{j})$ монотонно не убывает по любому пути, где $g(N_{j})=\sum _{i=2}^{j}c(N_{i-1},N_{i})$ стоимость лучшего пути от начального узла $N_{1}$ к $N_{j}$. эвристике необходимо и достаточно подчиняться неравенству треугольника . Чтобы быть непротиворечивой,

В алгоритме поиска A* использование последовательной эвристики означает, что после расширения узла стоимость его достижения является минимально возможной при тех же условиях, которые требует алгоритм Дейкстры при решении задачи о кратчайшем пути (отсутствие ребер с отрицательной стоимостью). ). Фактически, если графу поиска задана стоимость $c'(N,P)=c(N,P)+h(P)-h(N)$ для последовательного $h$, то A* эквивалентно поиску по принципу «сначала лучшее» на этом графе с использованием алгоритма Дейкстры. В необычном случае, когда допустимая эвристика не является последовательной, узлу потребуется повторное расширение каждый раз, когда для него будет достигнута новая лучшая (на данный момент) стоимость.

Если данная эвристика $h$ допустимо, но несовместимо, можно искусственно заставить эвристические значения на пути быть монотонно неубывающимииспользуя

$h'(P)\gets \max(h(P),h'(N)-c(N,P))$

как эвристическое значение для $P$ вместо $h(P)$, где $N$ это узел, непосредственно предшествующий $P$ на пути и $h'(start)=h(start)$. Эта идея принадлежит Ласло Меро. и теперь известен как pathmax.Вопреки распространенному мнению, pathmax не превращает допустимую эвристику в непротиворечивую эвристику. Например, если A* использует pathmax и эвристику, которая является допустимой, но несогласованной, не гарантируется наличие оптимального пути к узлу при его первом расширении.

См. также

• Допустимая эвристика