DFID (Iterative-Deeping A *)

Question

Интересно, каковы преимущества и недостатки этих двух алгоритмов. Я хочу написать AddEmUp C++, но я не уверен, какой алгоритм (IDA или DFID) следует использовать.

Лучшая статья, которую я нашел, это this one, но она кажется слишком старой - '93. Любое новее?

Я думаю, что IDA * будет лучше, но ..? Любые другие идеи?

Любые идеи и информация были бы полезны.

Спасибо! (:

EDIT: Некоторые хорошая статья о IDA * и хорошее объяснение алгоритма

EDIT2:? Или некоторые хорошие эвристические функции для этой игры я понятия не имею, как думать о некоторых:/

Answer 1

Russel & Книга Norvig - отличная ссылка на эти алгоритмы, и я дам larsmans виртуальную высоту пять, чтобы предложить ее; однако я не согласен с тем, что IDA * имеет куда более сложную программу, чем A *. Я сделал это для проекта, где мне пришлось написать ИИ, чтобы решить головоломку с раздвижными блоками - знакомая проблема наличия сетки N x N пронумерованных плит и использование единого свободного места для скольжения плиток до тех пор, пока они не станут в порядке возрастания.

Напомним:

F(n) = g(n) + h(n). 

TotalCost = PathCost + Heuristic. 

г (п) = стоимость Путь, расстояние от начального до текущего состояния

ч (п) = Эвристический, оценка стоимости от текущего состояния для завершения состояния. Чтобы быть допустимой эвристикой (и таким образом обеспечить оптимальность A *), вы ни в коем случае не можете переоценить стоимость. See this question for more info on the effects of overestimating/underestimating heuristics on A*.

Помните, что итерационный Углубление А * только А * с ограничением на величину F узлов вам разрешено пересекать. Этот FLimit увеличивается с каждой внешней итерацией; с каждой итерацией вы находитесь углубление поиск.

Here's my C++ code, реализующий как A *, так и IDA * для решения вышеупомянутой раздвижной скобки. Вы можете видеть, что я использую std::priority_queue с пользовательским Компаратором для хранения состояний голосовой почты в очереди с приоритетом их значения F. Вы также заметите, что единственная разница между A * и IDA * заключается в добавлении проверки FLimit и внешнего цикла, который увеличивает этот FLimit. Надеюсь, это поможет пролить свет на эту тему.

Answer 2

Заканчивать Russell & Norvig, главы 3 и 4, и понимают, что IDA * трудно правильно запрограммировать. Вы можете попробовать рекурсивный лучший первый поиск (RBFS), также описывается R & N, или старый добрый A * . Последний может быть реализован с использованием std::priority_queue.

IIRC, R & N описал IDA * в первом издании, а затем заменил его RBFS во втором. Я еще не видел третьего издания.

Что касается вашего второго редактирования, я не изучал игру, но хорошей процедурой для получения эвристики является процедура расслабленных задач. Вы снимаете правила игры, пока не получите версию, для которой эвристика легко выражается и реализуется (и дешево для вычисления). Или, следуя принципу «снизу вверх», вы проверяете основные правила, чтобы узнать, какой из них допускает легкую эвристику, затем попробуйте это и добавьте другие правила по мере необходимости.

Answer 3

DFID - это особый случай IDA *, где эвристическая функция является константой 0; другими словами, он не предусматривает введение эвристики. Если проблема не настолько мала, что ее можно решить без использования эвристики, кажется, у вас нет другого выбора, кроме как использовать IDA * (или какой-либо другой член семейства A *). Тем не менее, IDA * действительно не так сложно: implementation, предоставленный авторами AIMA, составляет всего около половины страницы кода Lisp; Я предполагаю, что реализация на C++ не должна занимать больше двух раз.