Расширяет ли поиск A* один и тот же узел более одного раза?

Question

Поиск A*, кажется, пересчитывает значение f для Arad, Sibiu и других повторяющихся состояний, чего не следует делать, поскольку эти узлы уже развернуты и находятся в закрытом состоянии. Так чего мне здесь не хватает? (Изображение от Рассела и Норвига - Искусственный интеллект.

Образ:

В этом случае эти узлы не расширяются, поскольку их f-значения больше оптимального пути, что, если это не так? то есть что, если ближайшее f-значение должно было вернуться к предшествующему узлу? А * сделает это?

Answer 1

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