A-star (A *) с «правильной» функцией heuristi c и без отрицательных граней

Question

В A * heuristi c есть шаг, который обновляет значение узла, если был найден лучший маршрут к этому узлу . Но что, если бы у нас было без отрицательных граней и правильная функция heuristi c ( целенаправленная, безопасная и последовательная ). Правда ли, что обновление больше не нужно, потому что мы всегда сначала добираемся до этого состояния по кратчайшему пути?

Учитывая евклидово расстояние heuristi c, мне кажется, что оно работает, но я Я не могу обобщить это в своих мыслях, как и почему. Если нет, может ли кто-нибудь предоставить мне контрпример или в другом случае подтвердить мой первоначальный вариант?

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

Answer 1

Итак, я проверил свою гипотезу в различных случаях, и кажется, что даже если heuristi c (целеустремленный, безопасный и непротиворечивый) и «граф» не имеет отрицательных граней, первый вход в состояние может не быть на кратчайшем пути. (Некоторые экземпляры, по-видимому, дают правильный результат, только если поддерживается пересмотр и обновление состояний, а также отправка их обратно в openSet, содержащийся в A *.)

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