A* эффективность против Greedy Best First

Question

Учитывая следующий лабиринт:

|||||||||||||||||||||||||||||||||||||
|       | | |           |   |     | |
| ||||||| | ||| | ||| ||| ||||||| | |
|       |       | |     |     | |   |
||||| ||||| ||| | | | ||| ||||| | |||
|   | | | |   | | | |   | |   | |   |
| ||| | | | ||| ||||| ||| | ||| ||| |
|       |     |   |   |     | | |   |
||| ||||||||| ||||||| ||| ||| | | | |
|             |       | |   |     | |
| | ||||| | ||| | | ||| | ||| ||| | |
| | |     | | | | |     |   | | | | |
| | | ||||||| | ||||||||| ||| | ||| |
| | | |     |   |     |     |   |   |
||| ||| | ||||| ||||| ||| ||| ||||| |
|     | | |     | |     | |   | | | |
| | | | | ||| ||| ||| ||| | | | | | |
| | | | |                 | | |     |
||| ||||||| | | ||||| ||| | ||| |||||
|       | | | |     |   |     | |   |
||||| | | ||||||||| ||||||||||| | |||
|   | |           | |     |   | |   |
| ||| ||||| ||||||||| ||||| | | ||| |
| |   |      |        |     |       |
| | | ||||| ||| | | | | |||||||||||||
| | |   |     | | | |       |   | | |
| | ||| ||| | | | ||||||||| ||| | | |
| |   | |   | | |   | |   | | |     |
| ||| ||| ||||| ||| | | ||||| | |||||
|       |   |     | |     |   | |   |
||| | ||||| ||||| ||| ||| | ||| | |||
| | | | | | | |     | |   | |   | | |
| | ||| | | | | ||||||||| | | | | | |
|   |   |   |                 |     |
| | | | ||| ||| ||||||| ||| ||| ||| |
|+| | |       |   |       |   | |  P|
|||||||||||||||||||||||||||||||||||||

У меня есть два результата от двух разных алгоритмов (которые, я надеюсь, являются правильными реализациями A* и Greedy First):

                                    #nodes searched; hops to goal
large maze - a* -                   expanded: 1120 (cost: 209)
large maze - greedy -               expanded: 916 (cost: 209)

Это нормальное поведение? Является ли A* не всегда оптимальным и более эффективным, чем другие алгоритмы, учитывая один путь? Я знаю, что это зависит от установки проблемы, но это было воспроизведено с гораздо большим тестом:

mega maze - a* -                    expanded: 8964 (837)
mega maze - greedy (mh heur) -      expanded: 5455 (837)

Я ошибаюсь, думая, что A* должен был превзойти Greedy First здесь? Ниже моя эвристика... может быть, я неправильно устанавливаю свои эвристические значения?:

#greedy
self.heuristic = abs(goalNodeXY[0] - self.xy[0]) + abs(goalNodeXY[1] - self.xy[1])

#A* --- costFromStart == path length from starting point
self.heuristic = math.hypot(self.xy[1]-goalNodeXY[1],self.xy[0]-goalNodeXY[0]) + costFromStart

Answer 1

Является ли A* не всегда оптимальным и более эффективным, чем другие алгоритмы, учитывая один путь?

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

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

Answer 2

Хорошей эвристикой для A* является та, которая наилучшим образом приближается к оставшемуся расстоянию (а также никогда не превышает его, если вам нужен A*, чтобы всегда находить лучший путь). Поскольку расстояние в вашем лабиринте определяется как число пройденных ячеек, ваша жадная эвристика приближается, если значительно лучше, чем расстояние Евклида (гипотета), потому что оно предсказывает его идеально для случая, когда на оставшейся части пути нет препятствий, и всегда ближе к реальному расстоянию, если есть препятствия.

Поэтому абсолютно ожидаемо, что ваш первый подход превосходит ваш второй подход.