Есть ли у A * попсовый узел в порядке возрастающих затрат (как у Дейкстры) из бахромы для согласованной эвристики?

Question

A heuristi c является допустимым , если оно никогда не переоценивает истинную стоимость достижения узла цели из n.

Если heuristi c является последовательным , тогда значение heuristi c n никогда не превышает стоимость его преемника.

Для допустимого значения heuristi c более поздний извлеченный узел может обновить стоимость целевого узла, хотя он может уже иметь некоторый результат, поэтому нам нужно запустить алгоритм, пока ни один другой узел в бахроме не имеет меньше Значение тогда найденной стоимости. Отличается ли этот случай для последовательного heuristi c?

Answer 1

Последовательная эвристика c также удовлетворяет h (x) ≤ d (x, y) + h (y) для каждого ребра (x, y) графа, где d - расстояние до ребра.

Когда значение heuristi c является постоянным при первом раскрытии узла в A ^*, мы нашли оптимальный путь к этому узлу. Каждый узел будет развернут ровно один раз, в порядке стоимости.