Алгоритм поиска A * - A* search algorithm

Класс	Алгоритм поиска
Структура данных	График
Наихудшая производительность	${\ Displaystyle O (| E |) = O (b ^ {d})}$
Сложность пространства в наихудшем случае	${\ Displaystyle O (| V |) = O (b ^ {d})}$

A * (произносится как «А-звезда») - это алгоритм обхода графа и поиска пути , который часто используется во многих областях информатики из-за его полноты, оптимальности и оптимальной эффективности. Одним из основных практических недостатков является сложность пространства, так как все сгенерированные узлы хранятся в памяти. Таким образом, в практических системах маршрутизации путешествий он обычно уступает алгоритмам, которые могут предварительно обрабатывать граф для достижения лучшей производительности, а также подходам с ограничением памяти; тем не менее, A * по-прежнему остается лучшим решением во многих случаях. ${\ Displaystyle О (Ь ^ {d})}$

Питер Харт , Нильс Нильссон и Бертрам Рафаэль из Стэнфордского исследовательского института (ныне SRI International ) впервые опубликовали алгоритм в 1968 году. Его можно рассматривать как расширение алгоритма Дейкстры . A * обеспечивает лучшую производительность за счет использования эвристики для управления поиском.

История

A * был изобретен исследователями, работающими над планированием пути робота Шейки.

A * был создан в рамках проекта Shakey , целью которого было создание мобильного робота, который мог бы планировать свои собственные действия. Нильс Нильссон первоначально предложил использовать алгоритм Graph Traverser для планирования пути Шейки. Graph Traverser руководствуется эвристической функцией h ( n ) , расчетным расстоянием от узла n до целевого узла: он полностью игнорирует g ( n ) , расстояние от начального узла до n . Бертрам Рафаэль предложил использовать сумму g ( n ) + h ( n ) . Питер Харт изобрел концепции, которые мы теперь называем допустимостью и согласованностью эвристических функций. Первоначально A * был разработан для поиска путей с наименьшей стоимостью, когда стоимость пути является суммой его затрат, но было показано, что A * можно использовать для поиска оптимальных путей для любой задачи, удовлетворяющей условиям алгебры затрат.

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

Описание

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

На каждой итерации основного цикла A * необходимо определить, какой из его путей нужно продолжить. Это делается на основе стоимости пути и оценки затрат, необходимых для продления пути до цели. В частности, A * выбирает путь, который минимизирует

${\ Displaystyle е (п) = г (п) + час (п)}$

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

Типичные реализации A * используют очередь приоритетов для выполнения повторного выбора узлов с минимальной (оценочной) стоимостью для расширения. Эта приоритетная очередь известна как открытый набор или бахрома . На каждом шаге алгоритма узел с наименьшим значением f ( x ) удаляется из очереди, значения f и g его соседей обновляются соответственно, и эти соседи добавляются в очередь. Алгоритм продолжается до тех пор, пока удаленный узел (таким образом, узел с наименьшим значением f из всех периферийных узлов) не станет целевым узлом. Тогда значение f этой цели также является стоимостью кратчайшего пути, поскольку h в цели равно нулю в допустимой эвристике.

Описанный алгоритм дает нам только длину кратчайшего пути. Чтобы найти фактическую последовательность шагов, алгоритм можно легко изменить, чтобы каждый узел на пути следил за своим предшественником. После запуска этого алгоритма конечный узел будет указывать на своего предшественника и так далее, пока предшественник какого-либо узла не станет начальным узлом.

Например, при поиске кратчайшего маршрута на карте h ( x ) может представлять расстояние по прямой до цели, поскольку это физически наименьшее возможное расстояние между любыми двумя точками. Для карты сетки из видеоигры использование манхэттенского расстояния или октильного расстояния становится лучше в зависимости от набора доступных движений (4-стороннее или 8-стороннее).

Алгоритм поиска пути *, перемещающийся по случайно сгенерированному лабиринту

Воспроизвести медиа

Иллюстрация поиска A * для поиска пути между двумя точками на графике.

Если эвристика h удовлетворяет дополнительному условию h ( x ) ≤ d ( x , y ) + h ( y ) для каждого ребра ( x , y ) графа (где d обозначает длину этого ребра), то h называется монотонный или последовательный . При последовательной эвристике A * гарантированно найдет оптимальный путь без обработки какого-либо узла более одного раза, а A * эквивалентно запуску алгоритма Дейкстры с уменьшенной стоимостью d ' ( x , y ) = d ( x , y ) + h ( у ) - h ( х ) .

Псевдокод

Следующий псевдокод описывает алгоритм:

function reconstruct_path(cameFrom, current)
    total_path := {current}
    while current in cameFrom.Keys:
        current := cameFrom[current]
        total_path.prepend(current)
    return total_path

// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h)
    // The set of discovered nodes that may need to be (re-)expanded.
    // Initially, only the start node is known.
    // This is usually implemented as a min-heap or priority queue rather than a hash-set.
    openSet := {start}

    // For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from start
    // to n currently known.
    cameFrom := an empty map

    // For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
    gScore := map with default value of Infinity
    gScore[start] := 0

    // For node n, fScore[n] := gScore[n] + h(n). fScore[n] represents our current best guess as to
    // how short a path from start to finish can be if it goes through n.
    fScore := map with default value of Infinity
    fScore[start] := h(start)

    while openSet is not empty
        // This operation can occur in O(1) time if openSet is a min-heap or a priority queue
        current := the node in openSet having the lowest fScore[] value
        if current = goal
            return reconstruct_path(cameFrom, current)

        openSet.Remove(current)
        for each neighbor of current
            // d(current,neighbor) is the weight of the edge from current to neighbor
            // tentative_gScore is the distance from start to the neighbor through current
            tentative_gScore := gScore[current] + d(current, neighbor)
            if tentative_gScore < gScore[neighbor]
                // This path to neighbor is better than any previous one. Record it!
                cameFrom[neighbor] := current
                gScore[neighbor] := tentative_gScore
                fScore[neighbor] := gScore[neighbor] + h(neighbor)
                if neighbor not in openSet
                    openSet.add(neighbor)

    // Open set is empty but goal was never reached
    return failure

Примечание: в этом псевдокоде, если узел достигнут одним путем, удален из openSet и впоследствии достигнут более дешевым путем, он будет снова добавлен в openSet. Это важно для гарантии того, что возвращаемый путь является оптимальным, если эвристическая функция допустима, но не согласована . Если эвристика согласована, когда узел удаляется из openSet, путь к нему гарантированно будет оптимальным, поэтому тест «tentative_gScore <gScore [сосед]» всегда будет терпеть неудачу, если узел будет достигнут снова.

Иллюстрация поиска A * для поиска пути от начального узла к целевому узлу в задаче планирования движения робота . Пустые кружки представляют собой узлы в открытом наборе , т. Е. Те, которые еще предстоит изучить, а закрашенные - в закрытом наборе. Цвет на каждом замкнутом узле указывает расстояние от цели: чем зеленее, тем ближе. Сначала можно увидеть, как A * движется по прямой в направлении цели, затем при столкновении с препятствием он исследует альтернативные маршруты через узлы из открытого набора.

Смотрите также: алгоритм Дейкстры

Пример

Пример алгоритма A * в действии, где узлами являются города, соединенные дорогами, а h (x) - расстояние по прямой до целевой точки:

Клавиша: зеленый: старт; синий: цель; оранжевый: посетил

Алгоритм A * также имеет реальные приложения. В этом примере ребра - это железные дороги, а h (x) - это расстояние по дуге (кратчайшее возможное расстояние на сфере) до цели. Алгоритм ищет путь между Вашингтоном, округ Колумбия, и Лос-Анджелесом.

Детали реализации

Существует ряд простых оптимизаций или деталей реализации, которые могут существенно повлиять на производительность реализации A *. Первая деталь, которую следует отметить, заключается в том, что способ обработки связей приоритетной очередью может в некоторых ситуациях существенно повлиять на производительность. Если связи разорваны, и очередь ведет себя в стиле LIFO , A * будет вести себя как поиск в глубину среди путей с равной стоимостью (избегая исследования более чем одного одинаково оптимального решения).

Когда в конце поиска требуется путь, обычно для каждого узла сохраняется ссылка на его родителя. В конце поиска эти ссылки можно использовать для восстановления оптимального пути. Если эти ссылки сохраняются, может быть важно, чтобы один и тот же узел не появлялся в очереди приоритетов более одного раза (каждая запись соответствует разному пути к узлу и каждая с разной стоимостью). Стандартный подход здесь - проверить, появляется ли уже добавляемый узел в очереди приоритетов. Если это так, то приоритетный и родительский указатели изменяются, чтобы соответствовать пути с более низкой стоимостью. Стандартная очередь приоритетов на основе двоичной кучи не поддерживает напрямую операцию поиска одного из своих элементов, но ее можно дополнить хеш-таблицей, которая сопоставляет элементы с их положением в куче, позволяя выполнять эту операцию с понижением приоритета в логарифмическое время. В качестве альтернативы куча Фибоначчи может выполнять те же операции с пониженным приоритетом за постоянное амортизированное время .

Особые случаи

Алгоритм Дейкстры , как еще один пример алгоритма поиска с единообразной стоимостью, можно рассматривать как частный случай A *, где для всех x . Общий поиск в глубину может быть реализован с использованием A *, учитывая, что существует глобальный счетчик C, инициализированный очень большим значением. Каждый раз, когда мы обрабатываем узел, мы назначаем C всем его вновь обнаруженным соседям. После каждого отдельного присваивания мы уменьшаем счетчик C на единицу. Таким образом, чем раньше обнаружен узел, тем выше его значение. И алгоритм Дейкстры, и поиск в глубину могут быть реализованы более эффективно без включения значения в каждый узел. ${\ Displaystyle ч (х) = 0}$${\ Displaystyle ч (х)}$${\ Displaystyle ч (х)}$

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

Прекращение и завершенность

На конечных графах с неотрицательными весами ребер A * гарантированно завершается и является полным , т.е. он всегда найдет решение (путь от начала до цели), если оно существует. На бесконечных графах с конечным фактором ветвления и стоимостью ребер, которые отделены от нуля ( при некотором фиксированном ), A * гарантированно завершит работу, только если существует решение. ${\ textstyle d (x, y)> \ varepsilon> 0}$${\ Displaystyle \ varepsilon}$

Допустимость

Алгоритм поиска считается допустимым, если он гарантированно возвращает оптимальное решение. Если эвристическая функция, используемая A *, допустима , то A * допустима. Интуитивно понятное «доказательство» этого заключается в следующем:

Когда A * завершает свой поиск, он нашел путь от начала до цели, фактическая стоимость которого ниже, чем оценочная стоимость любого пути от начала до цели через любой открытый узел (значение узла ). Когда эвристика допустима, эти оценки оптимистичны (не совсем - см. Следующий абзац), поэтому A * может безопасно игнорировать эти узлы, потому что они не могут привести к более дешевому решению, чем то, которое у него уже есть. Другими словами, A * никогда не упускает из виду возможность более дешевого пути от начала до цели и поэтому будет продолжать поиск до тех пор, пока таких возможностей не будет. ${\ displaystyle f}$

Фактическое доказательство немного сложнее, потому что не гарантируется, что значения открытых узлов будут оптимистичными, даже если эвристика допустима. Это связано с тем, что не гарантируется оптимальность значений открытых узлов, поэтому не гарантируется , что сумма будет оптимистичной. ${\ displaystyle f}$${\ displaystyle g}$${\ displaystyle g + h}$

Оптимальная эффективность

Алгоритм A оптимально эффективен по отношению к набору альтернативных алгоритмов Alts для набора задач P, если для каждой задачи P в P и каждого алгоритма A ′ в Alts набор узлов, расширенный A при решении P, является подмножеством (возможно, равно) множества узлов, расширенных на A ′ при решении P. Окончательное исследование оптимальной эффективности A * было проведено Риной Дехтер и Джудеой Перл. Они считали, что различные определения Alts и P в сочетании с эвристикой A * просто допустимы или являются одновременно непротиворечивыми и допустимыми. Наиболее интересный положительный результат, который они доказали, заключается в том, что A * с последовательной эвристикой оптимально эффективен по отношению ко всем допустимым алгоритмам A * -подобного поиска по всем «непатологическим» поисковым задачам. Грубо говоря, их представление о непатологической проблеме - это то, что мы сейчас подразумеваем под «до разрешения проблем». Этот результат неверен, если эвристика A * допустима, но несовместима. В этом случае Дехтер и Перл показали, что существуют допустимые A * -подобные алгоритмы, которые могут расширять сколь угодно меньшее количество узлов, чем A *, для некоторых непатологических проблем.

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

Ограниченная релаксация

* Поиск, который использует эвристику, которая в 5,0 (= ε) раз превышает согласованную эвристику , и получает неоптимальный путь.

Хотя критерий допустимости гарантирует оптимальный путь решения, это также означает, что A * должен исследовать все равнозначные пути, чтобы найти оптимальный путь. Чтобы вычислить приблизительные кратчайшие пути, можно ускорить поиск за счет оптимальности, ослабив критерий допустимости. Часто мы хотим ограничить эту релаксацию, чтобы гарантировать, что путь решения не хуже, чем (1 + ε ) умноженный на оптимальный путь решения. Эта новая гарантия называется ε -допустимой.

Существует ряд ε- допустимых алгоритмов:

• Взвешенный A * / Статическое взвешивание. Если h _a ( n ) - допустимая эвристическая функция, в взвешенной версии поиска A * в качестве эвристической функции используется h _w ( n ) = ε h _a ( n ) , ε > 1 , и выполняется поиск A * как обычно (что в конечном итоге происходит быстрее, чем при использовании h _a, поскольку расширяется меньшее количество узлов). Таким образом, путь, найденный алгоритмом поиска, может иметь стоимость не более чем в ε раз больше, чем путь с наименьшей стоимостью в графе.
• Динамическое взвешивание использует функцию стоимости , где и где - глубина поиска, а N - ожидаемая длина пути решения.${\ Displaystyle е (п) = г (п) + (1+ \ varepsilon w (п)) ч (п)}$${\ displaystyle w (n) = {\ begin {case} 1 - {\ frac {d (n)} {N}} & d (n) \ leq N \\ 0 & {\ text {else}} \ end {case }}}$${\ Displaystyle d (п)}$
• Выборочное динамическое взвешивание использует выборку узлов для лучшей оценки и устранения эвристической ошибки.
• ${\ Displaystyle А _ {\ varepsilon} ^ {*}}$. использует две эвристические функции. Первый - это список FOCAL, который используется для выбора узлов-кандидатов, а второй h _F используется для выбора наиболее многообещающего узла из списка FOCAL.
• A _ε выбирает узлы с функцией , где A и B - константы. Если никакие узлы не могут быть выбраны, алгоритм вернется к функции , где C и D - константы.${\ displaystyle Af (n) + Bh_ {F} (n)}$${\ Displaystyle Cf (n) + Dh_ {F} (n)}$
• AlphA * пытается продвигать эксплуатацию в глубину, предпочитая недавно расширенные узлы. AlphA * использует функцию стоимости , где , где λ и Λ - константы с , π ( n ) - родительский элемент n , а ñ - последний развернутый узел.${\ Displaystyle е _ {\ альфа} (п) = (1 + ш _ {\ альфа} (п)) е (п)}$${\ displaystyle w _ {\ alpha} (n) = {\ begin {case} \ lambda & g (\ pi (n)) \ leq g ({\ tilde {n}}) \\\ Lambda & {\ text {иначе }} \ end {case}}}$${\ displaystyle \ lambda \ leq \ Lambda}$

Сложность

Время сложность А * зависит от эвристики. В худшем случае неограниченного пространства поиска количество расширенных узлов экспоненциально зависит от глубины решения (кратчайший путь) d : O ( b ^d ) , где b - коэффициент ветвления (среднее количество последователей на состояние ). Это предполагает, что целевое состояние вообще существует и достижимо из начального состояния; если это не так и пространство состояний бесконечно, алгоритм не завершится.

Эвристическая функция имеет большое влияние на практическую эффективность поиска A *, поскольку хорошая эвристика позволяет A * отсекать многие из узлов b ^d, которые могут быть расширены при неинформированном поиске. Его качество может быть выражено в терминах эффективного коэффициента ветвления b * , который может быть определен эмпирически для экземпляра задачи путем измерения количества узлов, созданных расширением, N , и глубины решения, а затем решения

${\ displaystyle N + 1 = 1 + b ^ {*} + (b ^ {*}) ^ {2} + \ dots + (b ^ {*}) ^ {d}.}$

Хорошие эвристики - это эвристики с низким эффективным фактором ветвления (оптимальным является b * = 1 ).

Временная сложность является полиномиальной, когда пространство поиска представляет собой дерево, имеется одно целевое состояние и эвристическая функция h удовлетворяет следующему условию:

${\ Displaystyle | час (x) -h ^ {*} (x) | = O (\ log h ^ {*} (x))}$

где h ^* - оптимальная эвристика, точная стоимость перехода от x к цели. Другими словами, ошибка h не будет расти быстрее, чем логарифм «идеальной эвристики» h ^*, которая возвращает истинное расстояние от x до цели.

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

Приложения

A * часто используется для решения общей проблемы поиска пути в таких приложениях, как видеоигры, но изначально был разработан как общий алгоритм обхода графа. Он находит применения в различных задачах, включая проблему синтаксического анализа с использованием стохастических грамматик в НЛП . Другие случаи включают информационный поиск с онлайн-обучением.

Отношения к другим алгоритмам

Что отличает A * от жадного алгоритма поиска лучшего первого, так это то, что он учитывает стоимость / пройденное расстояние, g ( n ) .

Некоторые распространенные варианты алгоритма Дейкстры можно рассматривать как частный случай A *, где эвристика для всех узлов; в свою очередь, и Дейкстра, и A * являются частными случаями динамического программирования . Сама A * является частным случаем обобщения ветвей и границ . ${\ Displaystyle ч (п) = 0}$

Варианты

• В любое время A *
• Блок А *
• D *
• Поле D *
• Бахрома
• Сохранение бахромы A * (FSA *)
• Обобщенный адаптивный A * (GAA *)
• Инкрементальный эвристический поиск
• Уменьшенный A *
• Итеративное углубление A * (IDA *)
• Поиск точки перехода
• Планирование на протяжении всей жизни A * (LPA *)
• Новый двунаправленный A * (NBA *)
• Упрощенная память с ограничением A * (SMA *)
• Тета *

A * также можно адаптировать к алгоритму двунаправленного поиска . Особое внимание следует уделять критерию остановки.

Смотрите также

• Поиск в ширину
• Поиск в глубину
• Планирование пути под любым углом , поиск путей, которые не ограничиваются движением по краям графа, а могут принимать любой угол

Примечания

использованная литература

дальнейшее чтение

• Нильссон, штат Нью-Джерси (1980). Принципы искусственного интеллекта . Пало-Альто, Калифорния: Издательство Tioga. ISBN 978-0-935382-01-3.

внешние ссылки

• Четкое визуальное объяснение A * с советами и мыслями о поиске пути
• Вариант A *, называемый иерархическим поиском пути A * (HPA *)
• Брайан Гринстед. «Алгоритм поиска A * в JavaScript (обновленный)» . Архивировано 15 февраля 2020 года . Проверено 8 февраля 2021 года .