Я запустил алгоритм A *, но я не понимаю, как он работает в деталях.Алгоритм A-Star детали
, например, у меня есть график, и это:
А -> В = 9 (не 90, как первоначально просили по ошибке)
А -> С = 20
С -> D = 40
Теперь я хочу начать с A и перейти к D, используя указанные пути.
Если я использую эту эвристическую функцию: h (n) = расстояние прямого пути до D Прямое расстояние между B и D равно 2, но между B и D нет пути.
Что я хочу знать, что:
ли алгоритм * первый перейти к B, а затем вернуться к снова (Потому что нет никакого пути между B и D (цель)
или? Моя эвристический функция не является допустимым? (но i'v видели в учебниках, это нормально)
Не уверен, что ваш вопрос здесь, но в этом случае: A * начинается с A со счетом 0. Он находит B и присваивает оценку в 90 очков, затем находит C и присваивает счет 20. Затем он закрывает A . Таким образом, A замкнуто, B и C являются «открытыми». C имеет самый низкий балл открытых узлов, поэтому он идет туда. Теперь он находит D и останавливается, потому что это конечная точка. – Dave
В более интересном примере B будет иметь более низкий балл, чем C, поэтому он перейдет к B. Он не найдет ничего для ссылки (так что не добавьте новых открытых узлов) и закройте B. Теперь открыт только C, поэтому он идет туда. Остальное по-прежнему. – Dave