Нужна помощь для понимания алгоритмов поиска (A*, IDA*, DFS, BFS, IDDFS и т. Д.)

Question

У меня есть некоторые проблемы с пониманием некоторых алгоритмов для поиска, используемых в ИИ (искусственный интеллект).

• В чем точная разница между A* и Ида* (итеративное углубление звезды)? Является ли только эвристическая функция? Если так, я все еще не могу представить, как работает Ида*:/
• Является ИДА* такой же как BFS (поиск по ширине) (Когда глубина расширения составляет всего 1 уровень, я имею в виду - перемещение только одного за один уровень «вниз», есть ли разница между ИДА* и BFS)
• Является IDDFS (итеративная глубина-по поиску) поиск) такой же как ИДА*, кроме эвристической функции (которая эквивалентна 0 в Iddfs)
• Что именно такого Iddfs - Двигается вниз только один Уровень, затем используя DFS (поиск по глубине)? Если это так, то в этом смысле много государств рассчитаны (расширены) гораздо больше, чем те ... или это так - используйте DFS с определенной глубиной, затем храните «листья» (последние расширенные узлы) и переверните через них, чтобы использовать DFS снова (что, на самом деле, BFS?)
• Где "итеративный"Приходит? Как я вижу, Iddfs не итеративно, он все еще рекурсивен, просто микширует BFS и DFS? Или я ошибаюсь? Или это "итеративный"Не имеет ничего общего с противоположностью рекурсии?
• Что "итеративный" за ИДА* ?

Не могли бы вы, пожалуйста, привести несколько примеров? Я прочитал весь день об этих алгоритмах, я знаю их преимущества и недостатки, сложность и т. Д., Но я просто не мог найти никаких хороших примеров (за исключением*; я знаю, что BF и DFS, другие беспокоят меня). Я нашел немного псевдокода для IDA* в разных местах, но все они были совершенно разными.

Примерами были бы лучший способ понять алгоритмы ... но я не могу найти. Даже в Топкодер Я ничего не нашел об Иде*.

Я читал статьи в вики и ищу что -то новое (:

Большое спасибо!

---

РЕДАКТИРОВАТЬ: Вот несколько хороших статей, но они слишком теоретические. Нет примеров, никаких конкретных вещей. Но все еще очень полезен. Я бы порекомендовал их (=

Answer 1

Давайте начнем с итеративного углубленного поиска глубины.

Идея состоит в том, что поиск по глубине является эффективным, но не обязательно достигнет правильного ответа в ближайшее время. Итак, сделайте DFS на глубину 1. Если вы не нашли ответ, сделайте это на глубину 2. Повторите, пока не найдете ответ, или не решите сдаться. Это автоматически дает вам самый короткий путь на дереве поиска, поскольку вы никогда не ищете путь длины n + 1, если есть один из длины N.

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

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

Сначала изучите итеративное углубление DFS, затем примените это к IDA*. Я прочитал раннюю бумагу Korf об этих поисках более пятнадцати лет назад, и не помню, как Ида* работает очень хорошо, но ваша главная проблема заключается в том, что вы не понимаете итеративное углубление в первую очередь.