Итеративное углубление A*
| Сорт | Алгоритм поиска |
|---|---|
| Структура данных | Дерево , График |
| Наихудшая пространственная сложность |
Итеративное углубление A* ( IDA* ) — это алгоритм обхода графа и поиска пути , который может найти кратчайший путь между назначенным начальным узлом и любым членом набора целевых узлов во взвешенном графе. Это вариант итеративного поиска в глубину с углублением , который заимствует идею использования эвристической функции для консервативной оценки оставшейся стоимости достижения цели из алгоритма поиска A* . Поскольку это алгоритм поиска в глубину, его использование памяти ниже, чем в A*, но в отличие от обычного итеративного поиска с углублением он концентрируется на исследовании наиболее перспективных узлов и, таким образом, не достигает одинаковой глубины повсюду в дереве поиска. В отличие от A*, IDA* не использует динамическое программирование и поэтому часто исследует одни и те же узлы много раз.
В то время как стандартный итеративный поиск в глубину с углублением использует глубину поиска в качестве порогового значения для каждой итерации, IDA* использует более информативный поиск. , где стоимость перемещения от корня к узлу и — это эвристическая оценка стоимости поездки из конкретной задачи к цели.
Алгоритм был впервые описан Ричардом Корфом в 1985 году. [1]
Описание
[ редактировать ]Iterative-deepening-A* работает следующим образом: на каждой итерации выполняет поиск в глубину , отсекая ветвь, когда ее полная стоимость превышает заданный порог . Этот порог начинается с оценки стоимости в начальном состоянии и увеличивается с каждой итерацией алгоритма. На каждой итерации порог, используемый для следующей итерации, представляет собой минимальную стоимость всех значений, которые превысили текущий порог. [1]
Как и в случае A*, эвристика должна обладать определенными свойствами, чтобы гарантировать оптимальность (кратчайшие пути). См. Свойства ниже.
Псевдокод
[ редактировать ]path current search path (acts like a stack) node current node (last node in current path) g the cost to reach current node f estimated cost of the cheapest path (root..node..goal) h(node) estimated cost of the cheapest path (node..goal) cost(node, succ) step cost function is_goal(node) goal test successors(node) node expanding function, expand nodes ordered by g + h(node) ida_star(root) return either NOT_FOUND or a pair with the best path and its cost procedure ida_star(root) bound := h(root) path := [root] loop t := search(path, 0, bound) if t = FOUND then return (path, bound) if t = ∞ then return NOT_FOUND bound := t end loop end procedure function search(path, g, bound) node := path.last f := g + h(node) if f > bound then return f if is_goal(node) then return FOUND min := ∞ for succ in successors(node) do if succ not in path then path.push(succ) t := search(path, g + cost(node, succ), bound) if t = FOUND then return FOUND if t < min then min := t path.pop() end if end for return min end function
Характеристики
[ редактировать ]ведущий от заданного начального узла к любому целевому узлу графа задачи, если эвристическая функция 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) .