Правильная формулировка алгоритма А*

Question

Я смотрю определения алгоритма поиска пути A*, и кажется, что в разных местах он определяется несколько по-разному.

Разница заключается в действии, выполняемом при просмотре преемников узла и обнаружении того, что преемник находится в закрытом списке.

• Один подход (предложенный Википедия, и Эта статья) говорит:если преемник находится в закрытом списке, просто игнорируйте его
• Другой подход (предложенный здесь и здесь, например) говорит:если преемник находится в закрытом списке, проверьте его стоимость.Если он выше текущего рассчитанного балла, удалите элемент из закрытого списка для дальнейшего изучения.

Я в замешательстве - какой метод правильный?Интуитивно для меня первое имеет больше смысла, но меня интересует разница в определениях.Одно из определений неверно или они каким-то образом изоморфны?

Answer 1

Первый подход оптимален только в том случае, если оптимальный путь к любому повторяющемуся состоянию всегда является первым, по которому следует идти.Это свойство имеет место, если эвристическая функция обладает свойством последовательность (также называемый монотность).Эвристическая функция непротиворечива, если для каждого узла n и каждый преемник n' из n, предполагаемая стоимость достижения цели от n не превышает стоимости шага, необходимого для достижения n' от n плюс предполагаемая стоимость достижения цели от n.

Второй подход оптимален, если эвристическая функция просто допустима, то есть никогда не переоценивает затраты на достижение цели.

Любая непротиворечивая эвристическая функция также допустима.Хотя непротиворечивость является более строгим требованием, чем допустимость, приходится немало потрудиться, чтобы придумать эвристические функции, которые были бы допустимыми, но не непротиворечивыми.

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

Ссылка:подраздел Поиск:Минимизация общей ориентировочной стоимости решения в разделе 4.1 Информированные (эвристические) стратегии поиска книги Искусственный интеллект:Современный подход.