A * ефективність проти Greedy Best First - пітон, штучний інтелект, пошук шляху, евристика

Дано наступний лабіринт:

|||||||||||||||||||||||||||||||||||||
|       | | |           |   |     | |
| ||||||| | ||| | ||| ||| ||||||| | |
|       |       | |     |     | |   |
||||| ||||| ||| | | | ||| ||||| | |||
|   | | | |   | | | |   | |   | |   |
| ||| | | | ||| ||||| ||| | ||| ||| |
|       |     |   |   |     | | |   |
||| ||||||||| ||||||| ||| ||| | | | |
|             |       | |   |     | |
| | ||||| | ||| | | ||| | ||| ||| | |
| | |     | | | | |     |   | | | | |
| | | ||||||| | ||||||||| ||| | ||| |
| | | |     |   |     |     |   |   |
||| ||| | ||||| ||||| ||| ||| ||||| |
|     | | |     | |     | |   | | | |
| | | | | ||| ||| ||| ||| | | | | | |
| | | | |                 | | |     |
||| ||||||| | | ||||| ||| | ||| |||||
|       | | | |     |   |     | |   |
||||| | | ||||||||| ||||||||||| | |||
|   | |           | |     |   | |   |
| ||| ||||| ||||||||| ||||| | | ||| |
| |   |      |        |     |       |
| | | ||||| ||| | | | | |||||||||||||
| | |   |     | | | |       |   | | |
| | ||| ||| | | | ||||||||| ||| | | |
| |   | |   | | |   | |   | | |     |
| ||| ||| ||||| ||| | | ||||| | |||||
|       |   |     | |     |   | |   |
||| | ||||| ||||| ||| ||| | ||| | |||
| | | | | | | |     | |   | |   | | |
| | ||| | | | | ||||||||| | | | | | |
|   |   |   |                 |     |
| | | | ||| ||| ||||||| ||| ||| ||| |
|+| | |       |   |       |   | |  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
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

Відповіді:

Є A * не завжди оптимальним і Чим ефективніше, ніж інші алгоритми, дається один шлях?

A * завжди знаходить оптимальний шлях, але він не завжди робить це швидше, ніж інші алгоритми. Це абсолютно нормально для жадібного пошуку іноді краще.

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

Хороша евристика для A * - та, щонаближається до останньої кращої відстані (а також ніколи не перевищує її, якщо вам потрібен ваш A *, щоб завжди знаходити найкращий шлях). Оскільки відстань у вашому лабіринті визначається як кількість пройдених клітин, ваші жадібні евристики наближаються, якщо значно краще, ніж відстань Евкліда (гіпот), тому що він передбачає його ідеально для випадку, коли на іншій частині шляху немає перешкод, і завжди ближче до реальної відстані, якщо є перешкоди.

Тому абсолютно очікується, що ваш перший підхід перевершить ваш другий підхід.