Лучший первый поиск: почему снова исследуются узлы с более высокой стоимостью пути?

Question

Я читаю книгу Рассела и Норвига: AIMA и задаюсь вопросом, почему A* (наилучший первый поиск сf=g+h) исследует узел, даже если он уже был исследован с более низким значением .

Следуя примеру Джона Левина , Best-First-Search расширяет следующие пути:

       ['S'],
 ['S', 'A'],
 ['S', 'A', 'B'],
 ['S', 'B'], <- unnecessary since the B before has lower path costs
 ['S', 'D'],
 ['S', 'D', 'C'],
 ['S', 'A', 'B', 'C'], <- unnecessary since the B before has lower path costs
 ['S', 'D', 'E'],
 ['S', 'D', 'C', 'G']

ИМХОnode <- POP(frontier)должно произойти до тех пор, покаnode.PATH-COSTниже, чемPATH-COSTиз всех увиденных случаев этого состояния. Я ошибаюсь?

Answer 1

Это зависит от эвристики.

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

Однако если эвристика допустима , но несовместима , мы не можем дать такую ​​гарантию и, возможно, придется расширить ее несколько раз.

Таким образом, показанный алгоритм не предполагает согласованности. Если вы можете это предположить, вы можете упростить алгоритм.