лучше эвристический, чем A *

Question

Эй, ребята, я зарегистрирован на ai-class.com stenford и только что узнал на моей первой неделе лекции об * алгоритме и о том, как его лучше использовать, чем другой поисковый алгоритм.

Я также показываю, как один из моих одноклассников реализует его на головоломке со скользящими блоками 4х4, которую он опубликовал в: http://george.mitsuoka.org/StanfordAI/slidingBlocks/ Хотя я очень ценю и благодарю Джорджа за внедрение A * и публикацию результатов для нашего развлечения.

Мне (и ему тоже) было интересно, есть ли способ сделать процесс более оптимизированным или есть лучшая эвристическая A *, например, лучшая эвристическая функция, чем максимальное из «числа блоков вне места» или « сумма расстояний до целей ", что ускорит процесс? А также, если есть лучший алгоритм, чем A * для таких проблем, я хотел бы также знать о них.

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

Answer 1

Это зависит от вашей эвристической функции .например, если у вас идеальная эвристика [h*], тогда алгоритм жадный (*) даст лучший результат, чем A *, и все равно будет оптимальным [поскольку ваша эвристика идеальна!],Он будет разрабатывать только узлы, необходимые для решения.К сожалению, редко бывает идеальная эвристика.
(*) жадный алгоритм: всегда разрабатывайте узел с наименьшим значением h.

Однако, если ваша эвристика очень плохая: h=0, то A * на самом деле BFS!И A * в этом случае будет развивать O(B^d) узлов, где B - коэффициент ветвления, а d - количество шагов, необходимых для решения.
В этом случае, поскольку у вас есть одна целевая функция, двунаправленный поиск (*) будет более эффективным, так как для него нужно развить только O(2*B^(d/2))=O(B^(d/2)) узлов, что намного меньше, чемчто A * будет развиваться.
двунаправленный поиск: (*) запуск BFS от цели и от начальных узлов, каждая итерация - один шаг с каждой стороны, алгоритм заканчивается, когда в обоих фронтах есть общая вершина.

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

Возможная оптимизация для среднего случая : Вы также можетезапустить двунаправленный поиск с помощью A *: со стартовой стороны вы можете запустить A * со своей эвристикой и обычным BFS со стороны цели.Будет ли решение быстрее?Понятия не имею, вы должны, вероятно, сравнить две возможности и найти, что лучше.Однако решение, найденное с помощью этого алгоритма, также будет оптимальным, как BFS и A *.

Answer 2

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