Я готовлюсь к предстоящему экзамену и наткнулся на этот вопрос на листе:
Объясните, почему для эвристики недостаточно быть допустимым для
гарантировать обнаружение оптимального пути при ведении графа
поиск с использованием A *.
Я сидел, думая об этом, и пытался объяснить это, но я не могу решить это? Я рассмотрел другие подобные вопросы здесь, но они говорят о том, как допустимость гарантирует оптимальность.
Основное доказательство оптимальности A * основывается на том, что:
Скажем, у нас есть два целевых состояния G и G2, где f (G) = f *, что является оптимальным решением, а G2 является неоптимальным решением.
n является прямым предком G, поэтому его нужно расширить до G.
Из допустимости мы знаем, что независимо от того, что f (n), оно должно быть <= f *. <br>
Однако если мы решили расширить G2 до n, это означает, что f (G2) <= f (n) и, следовательно, f (G2) <= f *. <br>
Это противоречит предыдущему утверждению, что f (G2) является субоптимальным, поэтому f (G2)> f *.
S
/ \
n G2
/
G
Для меня это доказательство основано исключительно на допустимости, а последовательность действительно не влияет на него. Хотя доказательство опирается на то, что f (G) больше, чем f (n), что обеспечивается согласованностью, допустимость также обеспечивает это при этом обстоятельстве? Как нет способа, чтобы f (n) мог быть больше, чем f (G), если эвристика не переоценивает расстояние?