вопрос алгоритма кратчайшего пути a-star

Question

Карта - это изображение (10x10), которое нельзя перемещать по диагонали.

Порядок поиска вверх, вправо, вниз, влево.

тогда, если запустить кратчайший алгоритм типа «звезда», работает как черный путь, не так ли?

, но кратчайший путь - это красный путь.

Я не понимаю-Звездный алгоритм хорошо.Я хочу, чтобы вы мне помогли.

Answer 1

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