Итеративное углубление A*
| Сорт | Алгоритм поиска |
|---|---|
| Структура данных | Дерево , График |
| Наихудшая пространственная сложность |
Итеративное углубление A* ( IDA* ) — это алгоритм обхода графа и поиска пути , который может найти кратчайший путь между назначенным начальным узлом и любым членом набора целевых узлов во взвешенном графе. Это вариант итеративного поиска в глубину с углублением , который заимствует идею использования эвристической функции для консервативной оценки оставшейся стоимости достижения цели из алгоритма поиска A* . Поскольку это алгоритм поиска в глубину, его использование памяти ниже, чем в A*, но в отличие от обычного итеративного поиска с углублением он концентрируется на исследовании наиболее перспективных узлов и, таким образом, не достигает одинаковой глубины повсюду в дереве поиска. В отличие от A*, IDA* не использует динамическое программирование и поэтому часто исследует одни и те же узлы много раз.
В то время как стандартный итеративный поиск в глубину с углублением использует глубину поиска в качестве порогового значения для каждой итерации, IDA* использует более информативный поиск. , где стоимость перемещения от корня к узлу и — это эвристическая оценка стоимости поездки из конкретной задачи к цели.
Алгоритм был впервые описан Ричардом Корфом в 1985 году. [1]
Описание
[ редактировать ]Iterative-deepening-A* работает следующим образом: на каждой итерации выполняет поиск в глубину , отсекая ветвь, когда ее полная стоимость превышает заданный порог . Этот порог начинается с оценки стоимости в начальном состоянии и увеличивается с каждой итерацией алгоритма. На каждой итерации порог, используемый для следующей итерации, представляет собой минимальную стоимость всех значений, которые превысили текущий порог. [1]
Как и в случае A*, эвристика должна обладать определенными свойствами, чтобы гарантировать оптимальность (кратчайшие пути). См. Свойства ниже.
Псевдокод
[ редактировать ]путь текущий путь поиска (действует как стек) узел текущий узел (последний узел в текущем пути) g стоимость достижения текущего узла f предполагаемая стоимость самого дешевого пути (корень..узел..цель) h ( узел ) предполагаемая стоимость самый дешевый путь (узел..цель) стоимость ( узел , succ ) функция стоимости шага is_goal ( узел ) проверки цели преемники ( узел ) функция расширения узла, расширение узлов в порядке g + h(узел) ida_star ( корень ) возвращает либо NOT_FOUND, либо пара с лучшим путем и процедура ее стоимости ida_star ( root ) связанный := h ( корень ) путь := [ корень ] цикл t := поиск ( путь , 0, граница ) если t = FOUND, то вернуть (путь, граница), если t = ∞ , то вернуть NOT_FOUND граница := t конец цикла конец процедуры функции поиск ( путь , g , граница ) узел := путь .последний ж := г + ч ( узел ) если f > bound , то вернуть f, если is_goal ( узел ) , то вернуть FOUND мин := ∞ для успеха в преемниках ( узел ) сделать , если успех не в пути , то путь .push( succ ) t := поиск ( путь , g + стоимость ( узел , успех ), граница ) если t = НАЙДЕНО , то верните НАЙДЕНО если t < min , то min := t path .pop() end if end for return min end функция
Характеристики
[ редактировать ]ведущий от заданного начального узла к любому целевому узлу графа задачи, если эвристическая функция h допустима Как и A*, IDA* гарантированно найдет кратчайший путь , , [1] то есть
для всех узлов n , где h * — истинная стоимость кратчайшего пути от n до ближайшей цели («идеальная эвристика»). [2]
IDA* полезен, когда проблема связана с нехваткой памяти. Поиск A* сохраняет большую очередь неисследованных узлов, которые могут быстро заполнить память. Напротив, поскольку IDA* не запоминает ни одного узла, кроме тех, которые находятся на текущем пути , ему требуется объем памяти , линейный только по длине решения, которое он создает. Его временная сложность анализируется Корфом и др. в предположении, что эвристическая оценка стоимости h непротиворечива что , а это означает,
для всех узлов n и всех соседей n' из n ; они приходят к выводу, что по сравнению с поиском по дереву методом грубой силы для решения задачи экспоненциального размера, IDA* обеспечивает меньшую глубину поиска (в постоянном коэффициенте), но не меньший коэффициент ветвления. [3]
Рекурсивный поиск по принципу «сначала лучшее» — это еще одна версия поиска A* с ограничениями по памяти, которая на практике может быть быстрее, чем IDA*, поскольку требует меньшего повторного создания узлов. [2] : 282–289
Приложения
[ редактировать ]Приложения IDA* встречаются в таких задачах, как планирование . [4] Решение кубика Рубика — это пример задачи планирования, которую можно решить с помощью IDA*. [5]
Ссылки
[ редактировать ]- ^ Jump up to: а б с Корф, Ричард Э. (1985). «Итеративное углубление в глубину: поиск в оптимальном допустимом дереве» (PDF) . Искусственный интеллект . 27 : 97–109. дои : 10.1016/0004-3702(85)90084-0 . S2CID 10956233 .
- ^ Jump up to: а б Братко, Иван (2001). Программирование на Прологе для искусственного интеллекта . Пирсон Образование.
- ^ Корф, Ричард Э.; Рид, Майкл; Эделькамп, Стефан (2001). «Временная сложность итеративного углубления-A∗» . Искусственный интеллект . 129 (1–2): 199–218. дои : 10.1016/S0004-3702(01)00094-7 .
- ^ Боне, Блай; Геффнер, Гектор К. (2001). «Планирование как эвристический поиск». Искусственный интеллект . 129 (1–2): 5–33. дои : 10.1016/S0004-3702(01)00108-4 . hdl : 10230/36325 .
- ^ Ричард Корф (1997). «Поиск оптимальных решений кубика Рубика с использованием баз данных шаблонов» (PDF) .