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

Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Ноябрь 2009 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

Класс	Алгоритм поиска
Структура данных	Дерево , График
Сложность пространства в наихудшем случае	${\ displaystyle O (d)}$

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

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

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

Описание [ править ]

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

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

Псевдокод [ править ]

путь  текущий путь поиска (действует как стек) узел  текущий узел  (последний узел в текущем пути) g  стоимость достижения текущего узла f  оценочная стоимость самого дешевого пути (корень.. узел..цель) h ( узел ) оценочная стоимость самый дешевый путь (узел..цель) стоимость ( узел , succ ) функция стоимости шага is_goal ( узел ) цель тест преемники ( узел ) функция расширения узла, развернуть узлы в порядке g + h (узел) ida_star ( корень ) вернуть либо NOT_FOUND, либо пару с лучшим путем и его стоимостью процедура  ida_star ( root ) bound  : = h ( root ) path  : = [ root ] loop  t  : = search ( path , 0, bound ), если  t = FOUND, то return  (path, bound),  если  t = ∞, то возврат NOT_FOUND, привязанный  : = t  конец процедура завершения циклафункция  search ( path , g , bound ) node  : = path .last f  : = g + h ( node ), если  f > bound,  затем вернуть  f,  если  is_goal ( node ), затем вернуть FOUND min  : = ∞ для  succ  в  преемниках ( node ) делать,  если  succ  не  в  пути,  тогда path .push ( succ ) t  : = search ( path , g + cost ( node , succ ), bound ), если  t = FOUND, затем вернуть FOUND, если  t < min,  то  min  : = t  path .pop () end  if  end для  return  мин. конечная функция

Свойства [ править ]

Как А *, * МАР гарантировано , чтобы найти кратчайший путь , ведущий от заданного начального узла к любому узлу цели в задаче графа, если эвристический функция ч является допустимым , ^[2] , который

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

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

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

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

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

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

Приложения [ править ]

Приложения IDA * находятся в таких задачах, как планирование . ^[5]

Ссылки [ править ]