Приемлемость не гарантирует оптимальность для A*?

Question

Я готовлюсь к предстоящему экзамену и наткнулся на этот вопрос на листе:

Объясните, почему для эвристики недостаточно допустимости, чтобы гарантировать обнаружение оптимального пути при выполнении поиска в графе с использованием A*.

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

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

       S
      / \
     n   G2
    /
   G

Для меня это доказательство основывается исключительно на допустимости, а последовательность действительно не влияет на него. Хотя доказательство опирается на то, что f (G) больше, чем f(n), что обеспечивается согласованностью, допустимость также обеспечивает это при этом обстоятельстве? Как нет способа, чтобы f (n) мог быть больше, чем f (G), если эвристика не переоценивает расстояние?

Answer 1

Они ошибаются. Допустимость является необходимой и достаточной для A*, чтобы найти оптимальный путь.

Автор, вероятно, запутался, потому что оптимальность времени выполнения (то есть алгоритм, работающий быстро) требует последовательной эвристики.