DFID (Dept-First итеративное углубление) против IDA * (итеративное углубление A *)

Question

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

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

Я думаю, что IDA * будет лучше, но ..? Есть еще идеи?

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

Спасибо! (

РЕДАКТИРОВАТЬ: Хорошая статья о IDA * и хорошее объяснение алгоритма?

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

Answer 1

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

Напомним:

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

TotalCost = PathCost + Heuristic.

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

h (n) = эвристика, оценка стоимости от текущего состояния до конечного состояния. Чтобы быть допустимым эвристиком (и, таким образом, обеспечить оптимальность A *), вы ни в коем случае не можете переоценить стоимость. См. Этот вопрос для получения дополнительной информации о влиянии переоценки / недооценки эвристики на A *.

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

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

Answer 2

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

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

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

Answer 3

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