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

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

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

Алгоритмы поиска по графам и деревьям
α – β А * B * Возврат Луч Беллман – Форд Лучший первый Двунаправленный Борувка Ветвь и граница BFS британский музей D * DFS Dijkstra Эдмондс Флойд – Уоршалл Поиск бахромы скалолазание ИДА* Итеративное углубление Джонсон Точка прыжка Крускал Лексикографическая BFS LPA * Prim SMA *
Списки
Алгоритмы графа Алгоритмы поиска Список алгоритмов графа
похожие темы
Динамическое программирование Обход графа Обход дерева Искать игры Раскраска графика
v т е

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

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

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

Описание

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

Как и в случае 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

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

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

${\ Displaystyle ч (п) \ Leq ч ^ {*} (п)}$

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

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

${\ Displaystyle ч (п) \ Leq \ mathrm {стоимость} (п, п ') + ч (п')}$

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

Рекурсивный поиск лучшего первого - это еще одна версия поиска A * с ограничением памяти, которая на практике может быть быстрее, чем IDA *, поскольку требует меньшего количества регенерации узлов.

Приложения

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

Рекомендации