Итеративное углубление A*

Эвристический алгоритм поиска пути

Итеративное углубление A* ( IDA* ) — это алгоритм обхода графа и поиска пути , который может найти кратчайший путь между назначенным начальным узлом и любым членом набора целевых узлов во взвешенном графе. Это вариант итеративного углубленного поиска в глубину , который заимствует идею использования эвристической функции для консервативной оценки оставшейся стоимости достижения цели из алгоритма поиска A* . Поскольку это алгоритм поиска в глубину, его использование памяти ниже, чем в A*, но в отличие от обычного итеративного углубленного поиска, он концентрируется на исследовании наиболее перспективных узлов и, таким образом, не переходит на одну и ту же глубину везде в дереве поиска. В отличие от A*, IDA* не использует динамическое программирование и поэтому часто заканчивает исследованием одних и тех же узлов много раз.

В то время как стандартный итеративный поиск в глубину использует глубину поиска в качестве границы для каждой итерации, IDA* использует более информативный , где — стоимость перемещения от корня до узла , а — специфичная для проблемы эвристическая оценка стоимости перемещения от до цели. ${\displaystyle f(n)=g(n)+h(n)}$ ${\displaystyle g(n)}$ ${\displaystyle n}$ ${\displaystyle h(n)}$ ${\displaystyle n}$

Алгоритм был впервые описан Ричардом Корфом в 1985 году. ^[1]

Описание

Итеративное углубление-A* работает следующим образом: на каждой итерации выполняется поиск в глубину , отсекая ветвь, когда ее общая стоимость превышает заданный порог . Этот порог начинается с оценки стоимости в начальном состоянии и увеличивается для каждой итерации алгоритма. На каждой итерации порог, используемый для следующей итерации, является минимальной стоимостью всех значений, которые превысили текущий порог. ^[1] ${\displaystyle f(n)=g(n)+h(n)}$

Как и в A*, эвристика должна иметь определенные свойства, чтобы гарантировать оптимальность (кратчайшие пути). См. свойства ниже.

Псевдокод

path  текущий путь поиска (действует как стек) node  текущий узел  (последний узел в текущем пути) g  стоимость достижения текущего узла f  предполагаемая стоимость самого дешевого пути (корень..узел..цель) h ( узел ) предполагаемая стоимость самого дешевого пути (узел..цель) cost ( узел , succ ) функция стоимости шага is_goal ( узел ) проверка цели successors ( узел ) функция расширения узла, расширяет узлы, упорядоченные по g + h(узел) ida_star ( корень ) возвращает либо NOT_FOUND, либо пару с наилучшим путем и его стоимостью процедура  ida_star ( корень ) граница  := h ( корень ) путь  := [ корень ] цикл  t  := поиск ( путь , 0, граница ) если  t = НАЙДЕНО, то вернуть  (путь, граница)  если  t = ∞ , то вернуть НЕ_НАЙДЕНО граница  := t  конец цикла конец процедурыфункция  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                

Характеристики

Как и A*, IDA* гарантированно найдет кратчайший путь, ведущий от заданного начального узла к любому целевому узлу в графе задачи, если эвристическая функция h допустима, [ 1 ] ^то есть

${\displaystyle h(n)\leq h^{*}(n)}$

для всех узлов n , где h * — истинная стоимость кратчайшего пути от n до ближайшей цели («идеальная эвристика»). ^[2]

IDA* полезен, когда проблема ограничена памятью. Поиск* сохраняет большую очередь неисследованных узлов, которые могут быстро заполнить память. Напротив, поскольку IDA* не запоминает ни одного узла, кроме тех, что находятся на текущем пути , ему требуется объем памяти , который линеен только по длине решения, которое он строит. Его временная сложность анализируется Корфом и др. в предположении, что эвристическая оценка стоимости h является последовательной , что означает, что

${\displaystyle h(n)\leq \mathrm {cost} (n,n')+h(n')}$

для всех узлов n и всех соседей n' узла n ; они приходят к выводу, что по сравнению с поиском методом грубой силы по дереву для задачи экспоненциального размера, IDA* достигает меньшей глубины поиска (на постоянный множитель), но не меньшего фактора ветвления. ^[3]

Рекурсивный поиск по лучшему первому совпадению — это еще одна версия поиска A* с ограничениями по памяти, которая на практике может быть быстрее, чем IDA*, поскольку требует меньшего количества повторных генераций узлов. ^{[2] : 282–289}

Приложения

Применение IDA* можно найти в таких задачах, как планирование . ^[4] Решение кубика Рубика — пример задачи планирования, которую можно решить с помощью IDA*. ^[5]

Ссылки

1. Корф, Ричард Э. (1985). "Итеративное углубление в глубину: оптимальный допустимый поиск по дереву" (PDF) . Искусственный интеллект . 27 : 97–109. doi :10.1016/0004-3702(85)90084-0. S2CID  10956233.
2. Братко, Иван (2001). Программирование на Прологе для искусственного интеллекта . Pearson Education.
3. Корф, Ричард Э.; Рид, Майкл; Эделькамп, Стефан (2001). «Временная сложность итеративного углубления-A∗». Искусственный интеллект . 129 (1–2): 199–218. doi : 10.1016/S0004-3702(01)00094-7 .
4. Бонет, Блай; Геффнер, Гектор К. (2001). «Планирование как эвристический поиск». Искусственный интеллект . 129 (1–2): 5–33. doi :10.1016/S0004-3702(01)00108-4. hdl : 10230/36325 .
5. Ричард Корф (1997). "Поиск оптимальных решений для кубика Рубика с использованием баз данных шаблонов" (PDF) . Архивировано из оригинала (PDF) 2019-08-19 . Получено 2023-09-11 .