В алгоритме поиска A * что вы проверяете, когда просматриваете открытый список?

Question

Я немного запутался в следующем шаге, что делать после сохранения первого узла. На странице в Википедии об A * говорится, что нужно игнорировать соседа, который уже находится в закрытом наборе, но если его нет, добавьте его в открытый набор, если его там нет, и проверьте оценку g.

Однако на этой странице https://brilliant.org/wiki/a-star-search/, говорится, чтобы проверить, «имеет ли сосед значение g ниже, чем текущее, и находится ли он в закрытом списке», а затем заменить значение g соседа, если «текущее значение g ниже, и это сосед находится в открытом списке "", затем замените соседа новым, более низким значением g "

Так что я как бы запутался в том, что проверять. Проигнорировать ли узел, если он уже находится в закрытом наборе, или мне нужно также проверить его значение g и заменить соседним с ним?

Что мне делать после того, как у меня есть первый узел в A *?

Answer 1

Если мы находим соседа в закрытом наборе, это означает, что мы уже посетили его ранее. Это означает одну из двух вещей:

1. Его оценка g уже минимальная , так что дополнительное условие на Brilliant никогда не будет выполнено.

2. Эвристическая функция h является недопустимой , то есть она переоценивает фактическую минимальную стоимость достижения цели. В этом случае код на Brilliant может найти несколько более короткие пути, но ни один из них не гарантирует нахождение самых коротких. Чтобы найти кратчайший путь, используя недопустимую эвристику, вам необходимо «открыть» такие узлы. Это заставит алгоритм пересматривать целые подграфы несколько раз, что серьезно повредит сложности, а это не то, что делает код Brilliant.

Подводя итог: разница между версиями Brilliant и Wikipedia заключается в обработке небольшого углового случая, который никогда не произойдет, если A * дана "правильная" (допустимая) эвристическая функция.

Так что я как бы смущен тем, что проверять. Проигнорировать ли узел, если он уже находится в закрытом наборе, или мне нужно также проверить его значение g и заменить соседним с ним?

Я бы следовал коду Википедии и полностью игнорировал узлы в закрытом наборе.