Почему допустимые эвристики гарантируют оптимальность?

У нас есть список кандидатов, верно?

И у каждого из них есть ETC (ожидаемая общая стоимость) для достижения цели от начального узла (т. е. стоимость достижения этого узла + ожидаемая оставшаяся стоимость достижения цели (эвристика)).

Теперь, если ожидаемая стоимость идентична фактической стоимости, мы просто выберем узлы на кратчайшем пути (ну, на любом из кратчайших путей) и ничего больше. Поскольку мы выбираем самый низкий ETC, должно быть совершенно очевидно, почему мы выбираем узлы только с кратчайшего пути — все, что не находится на кратчайшем пути, будет иметь более высокий ETC.

Что делать, если ETC меньше фактической стоимости? Мы всегда выбираем самый низкий ETC, поэтому мы можем в конечном итоге выбрать узлы не на кратчайшем пути. Но мы никогда не сможем достичь цели по пути, который не является кратчайшим, потому что:

• Фактическая стоимость кратчайшего пути ниже, чем у любого некратчайшего пути.
• ETC у цели такой же, как стоимость достижения цели по этому пути (поскольку мы уже у цели, ожидаемая оставшаяся стоимость равна 0)
• ETC всегда меньше или равно фактической общей стоимости на любом пути.
• Таким образом, ЭТС на кратчайшем пути строго меньше, чем ЭТС на цели, которая была достигнута некратчайшим путем.

As an example, let's say we have costs as follows: (the cost above / below a node is the expected remaining cost, the cost at an edge is the actual cost)

  0    10  0  100   0
START ---- O ------ GOAL
0 |                 | 100
  O ------ O ------ O
 100  1   100  1   100

Очевидно, что мы начнем с посещения верхнего среднего узла, поскольку ETC равен 10 (10+0).

Тогда целью будет кандидат с ETC 110 (10+100+0).

Тогда мы явно выбираем нижние узлы один за другим, а затем обновляемую цель, поскольку все они имеют ETC ниже, чем ETC текущей цели, то есть их ETC: 100, 101, 102, 102.

Таким образом, несмотря на то, что цель была кандидатом, мы не могли выбрать ее, потому что там все еще был лучший путь.

Согласно этой статье Википедии:

С недопустимой эвристикой алгоритм A* может пропустить оптимальное решение задачи поиска...

Хороший пример приведен в статье: Задача на 15 головоломок.

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

Возьмите это как текущий узел:

Целевой узел:

15 и 14 плитки меняются местами.

Для узла, представленного на рисунке выше, он вернет 2 (две плитки неуместны: 15 и 14). Эта эвристическая функция допустима, поскольку она не игнорирует наиболее оптимальное решение (сортировка головоломки за 2 хода — перемещение 15 и 14 на нужные места).

Следовательно, эвристика гарантирует оптимальность.