A * алгоритм - начальная точка

Question

Я нахожусь в двумерном сетчатом лабиринте, где вы можете двигаться только горизонтально и вертикально. Стоимость фронта равна 1, и я использую расстояние в Манхэттене для оценки расстояния от узла до цели.

Мой вопрос заключается в том, имеет ли это значение, если вы начинаете в своем текущем узле, находя путь кваша цель или начало на целевом узле и возвращение к текущему узлу?

Answer 1

Нет, это не имеет значения, работаете ли вы вперед или назад. Имейте в виду, что в практических приложениях у вас часто бывает много целевых узлов, но почти всегда один начальный узел. Если вы хотите достичь только одного целевого узла, лучше начать поиск с начального узла.

Также обратите внимание, что A * даст оптимальное решение при использовании допустимой эвристики. Может быть несколько решений, которые одинаково оптимальны, поэтому поиск назад, а не вперед, может привести вас к другому, но столь же хорошему решению.

Answer 2

Это имеет значение для каждого конкретного лабиринта (при условии, что есть некоторые блоки, делающие его лабиринтом) и подробности алгоритма, но ни один не всегда лучше, так как вы всегда можете поменять местами старт и цель.

Показатьчто это имеет значение, рассмотрим простой лабиринт с большим L-образным блоком следующим образом (расширяющийся далее вверх)

  |
  |                        
  |        a
  |  |  |
  |    
  |---------
 b

От a кажется, что вы пройдете весь квадрат влево. От б вы будете идти прямо вправо, затем вверх и на один шаг влево