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

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

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

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

История [ править ]

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

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

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

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

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

${\displaystyle f(n)=g(n)+h(n)}$

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

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

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

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

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

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

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

функция  reconstruct_path ( cameFrom ,  current )  total_path  : =  {current}  пока  текущий  в  cameFrom . Ключи :  current  : =  cameFrom [ current ]  total_path . prepend ( текущий )  возврат  total_path// A * находит путь от начала до цели. // h - эвристическая функция. h (n) оценивает стоимость достижения цели от узла n. function  A_Star ( start ,  goal ,  h )  // Набор обнаруженных узлов, которые, возможно, потребуется (повторно) расширить.  // Изначально известен только начальный узел.  // Обычно это реализуется как min-heap или приоритетная очередь, а не как хеш-набор.  openSet  : =  {начало} // Для узла n cameFrom [n] - это узел, непосредственно предшествующий ему на самом дешевом пути от начала  // до n, известном в настоящее время.  cameFrom  : =  в  пустую  карту // Для узла n gScore [n] - это стоимость самого дешевого пути от начала до n, известного в настоящее время.  gScore  : =  карта  со  значением по умолчанию  Infinity gScore [ start ] : = 0      // Для узла n fScore [n]: = gScore [n] + h (n). fScore [n] представляет наше лучшее предположение относительно  // насколько коротким может быть путь от начала до конца, если он проходит через n.  fScore  : =  карта  со  значением по умолчанию  Infinity fScore [ start ] : = h ( start )      в то время как  Openset  это  не  пустой  // Эта операция может происходить в O (1) раз , если Openset является мин-кучи или очереди приоритетов  тока  : =  узел в Openset , имеющий на самую низкую fScore [] значение , если ток = целью возврата reconstruct_path ( cameFrom , текущий )                openSet . Удалить ( ток )  для  каждого  соседа  из  текущего  // D (ток, сосед) является весом ребра от тока к ближнему  // tentative_gScore это расстояние от начала до соседа через текущий  tentative_gScore  : =  gScore [ ток ]  +  d ( текущий ,  сосед )  if  tentative_gScore  <  gScore [ сосед ]  // Этот путь к соседу лучше, чем любой предыдущий. Запиши это!  пришел от [ сосед]  : =  текущий  gScore [ сосед ]  : =  предварительный_gScore  fScore [ сосед ]  : =  gScore [ сосед ]  +  h ( сосед ),  если  сосед  не  входит в  openSet  openSet . добавить ( сосед ) // Открытый набор пуст , но цель никогда не достигается  обратный  отказ

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

Пример [ править ]

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

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

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

Детали реализации [ править ]

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

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

Особые случаи [ править ]

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

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

Прекращение и завершение [ править ]

На конечных графах с неотрицательными весами ребер 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 * было проведено Риной Дехтер и Джудеой Перл. ^[10] Они рассмотрели множество определений Alts и P в сочетании с тем, что эвристика A * просто допустима или является одновременно последовательной и допустимой. Наиболее интересный положительный результат, который они доказали, заключается в том, что A * с последовательной эвристикой оптимально эффективен по отношению ко всем допустимым алгоритмам A * -подобного поиска во всех «непатологических» задачах поиска. Грубо говоря, их представление о непатологической проблеме - это то, что мы сейчас подразумеваем под «до разрешения проблем». Этот результат неверен, если эвристика A * допустима, но несовместима. В этом случае Дехтер и Перл показали, что существуют допустимые A * -подобные алгоритмы, которые могут расширять сколь угодно меньшее количество узлов, чем A *, для некоторых непатологических проблем.

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

Ограниченная релаксация [ править ]

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

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

• Взвешенный A * / Статическое взвешивание. ^[14] Если h _a ( n ) - допустимая эвристическая функция, в взвешенной версии поиска A * используется h _w ( n ) = ε h _a ( n ) , ε > 1 в качестве эвристической функции, и выполняется Поиск A * как обычно (что в конечном итоге происходит быстрее, чем при использовании h _a, поскольку расширяется меньшее количество узлов). Таким образом, путь, найденный алгоритмом поиска, может иметь стоимость не более чем в ε раз больше, чем путь с наименьшей стоимостью в графе. ^[15]

• Динамическое взвешивание ^[16] использует функцию стоимости , где и где - глубина поиска, а N - ожидаемая длина пути решения.${\displaystyle f(n)=g(n)+(1+\varepsilon w(n))h(n)}$${\displaystyle w(n)={\begin{cases}1-{\frac {d(n)}{N}}&d(n)\leq N\\0&{\text{otherwise}}\end{cases}}}$${\displaystyle d(n)}$

• Выборочное динамическое взвешивание ^[17] использует выборку узлов для лучшей оценки и устранения эвристической ошибки.

• ${\displaystyle A_{\varepsilon }^{*}}$. ^[18] использует две эвристические функции. Первый - это список FOCAL, который используется для выбора узлов-кандидатов, а второй h _F используется для выбора наиболее многообещающего узла из списка FOCAL.

• A _ε ^[19] выбирает узлы с функцией , где A и B - константы. Если никакие узлы не могут быть выбраны, алгоритм вернется к функции , где C и D - константы.${\displaystyle Af(n)+Bh_{F}(n)}$${\displaystyle Cf(n)+Dh_{F}(n)}$

• AlphA * ^[20] пытается продвигать эксплуатацию в глубину, отдавая предпочтение недавно расширенным узлам. AlphA * использует функцию стоимости , где , где λ и Λ - константы с , π ( n ) - родительский элемент n , а ñ - последний развернутый узел.${\displaystyle f_{\alpha }(n)=(1+w_{\alpha }(n))f(n)}$${\displaystyle w_{\alpha }(n)={\begin{cases}\lambda &g(\pi (n))\leq g({\tilde {n}})\\\Lambda &{\text{otherwise}}\end{cases}}}$${\displaystyle \lambda \leq \Lambda }$

Сложность [ править ]

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

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

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

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

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

${\displaystyle |h(x)-h^{*}(x)|=O(\log h^{*}(x))}$

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

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

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

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

Связь с другими алгоритмами [ править ]

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

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

Варианты [ править ]

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

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

См. Также [ править ]

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

Заметки [ править ]

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

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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