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

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

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

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

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

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

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

EDIT: здесь несколько хороших статей, но они слишком теоретические . Никаких примеров, никаких конкретных вещей. Но все равно очень полезно. Я бы порекомендовал их (=


search artificial-intelligence algorithm belongs-to
person Kiril Kirov    schedule 07.12.2010    source источник
comment
к какой проблеме вы пытаетесь подойти? вопросы, которые вы задали, заняли у моего университетского курса искусственного интеллекта около 5 недель, чтобы ответить, так что это слишком много, чтобы ответить.   -  person Alex Lo    schedule 08.12.2010
comment
Этот вопрос как бы связан с ЭТИМ < /a>, но совсем немного. Сначала мне нужно глубоко понять эти алгоритмы. Любые лекции или статьи будут полезны. Спасибо (:   -  person Kiril Kirov    schedule 08.12.2010
comment
Это было бы лучше задать как более чем один вопрос. Я объяснил IDDFS ниже, и вам действительно нужно понять это, прежде чем пытаться использовать IDA*. Как дела на А*? Вам должно быть удобно работать как с A*, так и с IDDFS, прежде чем пытаться изучить IDA*.   -  person David Thornley    schedule 08.12.2010
comment
@ Дэвид - я прекрасно понимаю А *. Или, по крайней мере, я так думаю.   -  person Kiril Kirov    schedule 08.12.2010
comment
Нужно взять себе книгу, сесть, почитать. Russel & Norvig AI - Современный подход может быть уместным.   -  person ziggystar    schedule 08.12.2010
comment
AI Stack Exchange все еще находится в стадии бета-тестирования, поэтому мы не можем переносить туда вопросы. Ничего страшного, если вы хотите оставить это здесь и повторить на ИИ. Если да, предоставьте ссылки между двумя вопросами, чтобы люди могли видеть ответы, которые вы получили от обоих сообществ.   -  person Bill the Lizard    schedule 18.12.2010

Ответы (1)


arrow_upward
4
arrow_downward

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

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

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

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

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

person David Thornley    schedule 07.12.2010
comment
Да, вы правы, я не могу понять, чем IDDFS отличается от BFS, так как идея выглядит точно так же :? - person Kiril Kirov; 08.12.2010
comment
@Kiril: Вы попали в те же узлы, что и BFS. Вам не нужно держать очередь и проверять узлы на уникальность. Идея состоит в том, чтобы объединить пространство и большую часть преимуществ DFS в производительности с гарантированным поиском кратчайшего пути BFS. - person David Thornley; 08.12.2010
comment
это не то же самое. космический компромисс является ключевым. вики-страница довольно хорошо объясняет преимущества: en.wikipedia.org/wiki/Iterative_deepening_depth-first_search - person Alex Lo; 08.12.2010