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

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

8 голосов
/ 08 декабря 2010

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

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

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

Примеры - лучший способ понять алгоритмы ... но я не могу найти.Даже в TopCoder я ничего не нашел в IDA *.

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

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

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

1 Ответ

4 голосов
/ 08 декабря 2010

Начнем с итеративного углубления поиска в глубину.

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

Для реализации необходимо изменить поиск в глубину, чтобы он углублялся на N узлов (т. Е. Не генерировал новые узлы, если у вас N на глубину), и вызывал его с увеличением N. Вы не храните ничего, кроме значения N и того, что вы делаете для DFS.

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

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

...