Сравнение вариаций A*

Question

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

Я ищу онлайн -статьи, которые провели аналогичные эксперименты, сравнивая вариации A* по отношению к расширенным узлам, но не сталкивались с чем -либо конкретным.

Answer 1

Ну, есть много библиографии о том, лучше ли один алгоритм, чем другой. В частности, главное понимание: "При наличии дубликатов (например, сетки), $^*$ должен быть предпочтительным, тогда как в других случаях Ida $^*$ в целом предпочтительнее«Например, эвристические планировщики обычно предпочитают лучшие первые стратегии поиска, такие как $^*$ вместо Ida $^*$ (только потому, что дубликаты встречаются во многих областях). Например, для решения $ n $ -puzzle, $ n $ -pancake, или Topspin, Ida $^*$, является текущим алгоритмом выбора. Для других случаев, таких как куб Рубика или башни Ханой, Ида $^*$ все еще является алгоритмом выбора, но будьте осторожны и попытаться реализовать хорошую стратегию для обработки симметрий. В случае сетей $^*$ - правильный выбор.

Есть замечательная статья о том, как реализовать $^*$, и делает много соображений, которые, я думаю, соответствуют вашему вопросу: Этан Эндрю Бернс, Мэтью Хэтем, Майкл Дж. Лейтон, Уилер Румл. Реализация быстрого эвристического кода поиска

Дайте мне знать, пожалуйста, поможет ли это или нет,