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

Question

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

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

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

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

Answer 1

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

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

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

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

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