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

Сегодня в классе мой профессор познакомил нас с допустимыми эвристиками и заявил, что они гарантируют оптимальность для алгоритма A* .

Я попросил его объяснить это на крайнем примере, чтобы сделать это очевидным, но он не смог.

Может кто-нибудь помочь?

1 3
algorithm heuristics artificial-intelligence

1 ответ:

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

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

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

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

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

В качестве примера предположим, что у нас есть затраты следующим образом: (стоимость выше / ниже узла-это ожидаемая остаточная стоимость, стоимость на краю-это фактическая стоимость) 

  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. Таким образом, несмотря на то, что цель была кандидатом, мы не могли выбрать его, потому что все еще был лучший путь.
6