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

Алгоритм, используемый для поиска пути и обхода графа

A* (произносится как «А-стар») — это алгоритм обхода графа и поиска пути , который используется во многих областях компьютерных наук благодаря своей полноте, оптимальности и оптимальной эффективности. ^[1] При наличии взвешенного графа , исходного узла и целевого узла алгоритм находит кратчайший путь (относительно заданных весов) от источника до цели.

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

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

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

История

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

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

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

Описание

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

Иллюстрация поиска A* для нахождения пути между двумя точками на графике. Слева направо все чаще используется эвристика, которая отдает предпочтение точкам, более близким к цели.

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

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

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

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

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

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

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

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

Псевдокод

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

функция restore_path ( cameFrom , current ) total_path := {current} пока current в cameFrom . Ключи : current := cameFrom [ current ] total_path . prepend ( current ) return total_path               // A* находит путь от начала до цели. // h — эвристическая функция. h(n) оценивает стоимость достижения цели от узла n. function A_Star ( start , goal , h ) // Набор обнаруженных узлов, которые, возможно, потребуется (повторно) расширить. // Изначально известен только начальный узел. // Обычно это реализуется как min-heap или приоритетная очередь, а не как хэш-набор. openSet := {start}          // Для узла n cameFrom[n] — это узел, непосредственно предшествующий ему на самом дешевом пути от начала // до n, известном в настоящее время. cameFrom := пустая карта       // Для узла n gScore[n] — это известная на данный момент стоимость самого дешевого пути от начала до n. gScore := map со значением по умолчанию Infinity gScore [ start ] := 0            // Для узла n, fScore[n] := gScore[n] + h(n). fScore[n] представляет наше текущее лучшее предположение о том, // насколько дешевым может быть путь от начала до конца, если он проходит через n. fScore : = map со значением по умолчанию Infinity fScore [ start ] := h ( start )             while openSet is not empty // Эта операция может быть выполнена за время O(Log(N)) если openSet является минимальной кучей или приоритетной очередью current := узел в openSet с наименьшим значением fScore [] if current = goal return reform_path ( cameFrom , current )                        openSet . Remove ( current ) для каждого соседа текущего // d(current,neighbor) - вес ребра от текущего к соседу // tentative_gScore - расстояние от начала до соседа через текущий tentative_gScore := gScore [ current ] + d ( current , neighbor ) if tentative_gScore < gScore [ neighbor ] // Этот путь к соседу лучше любого предыдущего. Запишите его! cameFrom [ neighbor ] : = current gScore [ neighbor ] := tentative_gScore fScore [ neighbor ] := tentative_gScore + h ( neighbor ) if neighbor not in openSet openSet . add ( neighbor )                                    // Открытый набор пуст, но цель так и не была достигнута return failure  

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

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

Пример

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

Обозначения: зеленый: начало; синий: цель; оранжевый: посещение

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

Подробности реализации

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

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

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

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

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

Прекращение и полнота

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

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

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

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

Фактическое доказательство немного сложнее, поскольку ⁠ ⁠ ${\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* много раз, экспоненциальное число раз в худшем случае. ^[14] В таких обстоятельствах алгоритм Дейкстры может превзойти A* с большим отрывом. Однако более поздние исследования показали, что этот патологический случай возникает только в определенных надуманных ситуациях, когда вес ребра поискового графа экспоненциально зависит от размера графа, и что определенные непоследовательные (но допустимые) эвристики могут привести к уменьшению количества расширений узлов в поиске A*. ^{[15] [16]}

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

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

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

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

• Взвешенные A*/статические весовые коэффициенты. ^[17] Если h _a ( n ) является допустимой эвристической функцией, в взвешенной версии поиска A* используется h _w ( n ) = ε h _a ( n ) , ε > 1 в качестве эвристической функции, и выполняется поиск A* как обычно (что в конечном итоге происходит быстрее, чем при использовании h _{a ,} поскольку расширяется меньше узлов). Таким образом, путь, найденный алгоритмом поиска, может иметь стоимость не более чем в ε раз больше, чем у пути с наименьшей стоимостью в графе. ^[18]
• Динамическое взвешивание ^[19] использует функцию стоимости ⁠ ⁠ ${\displaystyle f(n)=g(n)+(1+\varepsilon w(n))h(n)}$ , где , и где ⁠ ⁠ — глубина поиска, а N — ожидаемая длина пути решения. ${\displaystyle w(n)={\begin{cases}1-{\frac {d(n)}{N}}&d(n)\leq N\\0&{\text{otherwise}}\end{cases}}}$ ${\displaystyle d(n)}$
• Выборочное динамическое взвешивание ^[20] использует выборку узлов для лучшей оценки и устранения эвристической ошибки.
• ${\displaystyle A_{\varepsilon }^{*}}$. ^[21] использует две эвристические функции. Первая — это список FOCAL, который используется для выбора узлов-кандидатов, а вторая h _F используется для выбора наиболее перспективного узла из списка FOCAL.
• A _ε ^[22] выбирает узлы с функцией ⁠ ⁠ ${\displaystyle Af(n)+Bh_{F}(n)}$ , где A и B — константы. Если не удается выбрать ни одного узла, алгоритм возвращается к функции ⁠ ⁠ ${\displaystyle Cf(n)+Dh_{F}(n)}$ , где C и D — константы.
• AlphA* ^[23] пытается продвигать эксплуатацию в глубину, отдавая предпочтение недавно расширенным узлам. 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 }$

Сложность

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

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

${\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 до цели. ^{[18] [24]}

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

Приложения

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

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

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

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

A* похож на лучевой поиск, за исключением того, что лучевой поиск сохраняет ограничение на количество путей, которые он должен исследовать. ^[30]

Варианты

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

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

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

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

Примечания

1. «A*-подобный» означает, что алгоритм ищет, расширяя пути, исходящие из начального узла, по одному ребру за раз, как это делает A*. Это исключает, например, алгоритмы, которые ищут в обратном направлении от цели или в обоих направлениях одновременно. Кроме того, алгоритмы, охватываемые этой теоремой, должны быть допустимыми и «не более информированными», чем A*.
2. Целевые узлы могут быть пройдены несколько раз, если остаются другие узлы с более низкими значениями f , поскольку они могут привести к более короткому пути к цели.

Ссылки

1. Рассел, Стюарт Дж .; Норвиг, Питер (2018). Искусственный интеллект: современный подход (4-е изд.). Бостон: Pearson. ISBN 978-0134610993. OCLC  1021874142.
2. Деллинг, Д.; Сандерс, П.; Шультес, Д.; Вагнер, Д. (2009). «Алгоритмы планирования инженерных маршрутов». Алгоритмика больших и сложных сетей: проектирование, анализ и моделирование . Конспект лекций по информатике. Том 5515. Springer. С. 117–139. doi :10.1007/978-3-642-02094-0_7. ISBN 978-3-642-02093-3.
3. Zeng, W.; Church, RL (2009). «Поиск кратчайших путей на реальных дорожных сетях: случай A*». Международный журнал географической информационной науки . 23 (4): 531–543. Bibcode : 2009IJGIS..23..531Z. doi : 10.1080/13658810801949850. S2CID  14833639.
4. Харт, PE ; Нильссон, NJ ; Рафаэль, B. (1968). «Формальная основа для эвристического определения путей с минимальной стоимостью». Труды IEEE по системной науке и кибернетике . 4 (2): 100–7. doi :10.1109/TSSC.1968.300136.
5. Доран, Дж. Э.; Мичи, Д. (1966-09-20). «Эксперименты с программой Graph Traverser». Proc. R. Soc. Lond. A. 294 ( 1437): 235–259. Bibcode : 1966RSPSA.294..235D. doi : 10.1098/rspa.1966.0205. S2CID  21698093.
6. Нильссон, Нильс Дж. (2009-10-30). Поиски искусственного интеллекта (PDF) . Кембридж: Издательство Кембриджского университета. ISBN 9780521122931. Одной из первых проблем, которую мы рассмотрели, было то, как спланировать последовательность «точек маршрута», которые Шейки мог бы использовать для навигации из одного места в другое. […] Навигационная задача Шейки — это задача поиска, похожая на те, о которых я упоминал ранее.
7. Нильссон, Нильс Дж. (2009-10-30). Поиски искусственного интеллекта (PDF) . Кембридж: Издательство Кембриджского университета. ISBN 9780521122931. Бертрам Рафаэль, который в то время руководил работой над Shakey, заметил, что лучшим значением для оценки была бы сумма пройденного расстояния от исходного положения плюс моя эвристическая оценка того, какое расстояние должен был пройти робот.
8. Эделькамп, Стефан; Джаббар, Шахид; Льюч-Лафуэнте, Альберто (2005). "Cost-Algebraic Heuristic Search" (PDF) . Труды Двадцатой национальной конференции по искусственному интеллекту (AAAI) : 1362–7. ISBN 978-1-57735-236-5.
9. Харт, Питер Э.; Нильссон, Нильс Дж .; Рафаэль, Бертрам (1972-12-01). «Исправление к „Формальной основе для эвристического определения путей минимальной стоимости“» (PDF) . Бюллетень ACM SIGART (37): 28–29. doi :10.1145/1056777.1056779. S2CID  6386648.
10. Dechter, Rina; Judea Pearl (1985). «Обобщенные стратегии поиска лучшего первого и оптимальность A*». Журнал ACM . 32 (3): 505–536. doi : 10.1145/3828.3830 . S2CID  2092415.
11. Нанничини, Джакомо; Деллинг, Даниэль; Шультес, Доминик; Либерти, Лео (2012). «Двунаправленный поиск A* в дорожных сетях, зависящих от времени» (PDF) . Сети . 59 (2): 240–251. doi :10.1002/NET.20438.
12. De Smith, Michael John; Goodchild, Michael F.; Longley, Paul (2007), Геопространственный анализ: всеобъемлющее руководство по принципам, методам и программным средствам, Troubadour Publishing Ltd, стр. 344, ISBN 9781905886609.
13. Hetland, Magnus Lie (2010), Алгоритмы Python: Освоение базовых алгоритмов на языке Python, Apress, стр. 214, ISBN 9781430232377.
14. Мартелли, Альберто (1977). «О сложности допустимых алгоритмов поиска». Искусственный интеллект . 8 (1): 1–13. doi :10.1016/0004-3702(77)90002-9.
15. Фелнер, Ариэль; Узи Захави (2011). «Непоследовательные эвристики в теории и практике». Искусственный интеллект . 175 (9–10): 1570–1603. doi : 10.1016/j.artint.2011.02.001 .
16. Чжан, Чжифу; Н. Р. Стертевант (2009). Использование несогласованных эвристик при поиске A*. Двадцать первая международная совместная конференция по искусственному интеллекту. С. 634–639.
17. Pohl, Ira (1970). «Первые результаты по влиянию ошибки на эвристический поиск». Machine Intelligence 5. Edinburgh University Press: 219–236. ISBN 978-0-85224-176-9. OCLC  1067280266.
18. Pearl, Judea (1984). Эвристика: интеллектуальные стратегии поиска для решения компьютерных проблем. Addison-Wesley. ISBN 978-0-201-05594-8.
19. Pohl, Ira (август 1973). «Избегание (относительной) катастрофы, эвристическая компетентность, подлинное динамическое взвешивание и вычислительные проблемы в эвристическом решении проблем» (PDF) . Труды Третьей международной совместной конференции по искусственному интеллекту (IJCAI-73) . Том 3. Калифорния, США. С. 11–17.
20. Кёлль, Андреас; Герман Кайндль (август 1992 г.). «Новый подход к динамическому взвешиванию». Труды Десятой Европейской конференции по искусственному интеллекту (ECAI-92) . Вена, Австрия: Wiley. стр. 16–17. ISBN 978-0-471-93608-4.
21. Pearl, Judea; Jin H. Kim (1982). «Исследования полудопустимых эвристик». IEEE Transactions on Pattern Analysis and Machine Intelligence . 4 (4): 392–399. doi :10.1109/TPAMI.1982.4767270. PMID  21869053. S2CID  3176931.
22. Ghallab, Malik; Dennis Allard (август 1983). "Aε – эффективный почти допустимый эвристический алгоритм поиска" (PDF) . Труды Восьмой международной совместной конференции по искусственному интеллекту (IJCAI-83) . Том 2. Карлсруэ, Германия. С. 789–791. Архивировано из оригинала (PDF) 2014-08-06.
23. Reese, Bjørn (1999). AlphA*: ε-допустимый эвристический алгоритм поиска (Отчет). Институт производственных технологий, Университет Южной Дании. Архивировано из оригинала 2016-01-31 . Получено 2014-11-05 .
24. Рассел, Стюарт ; Норвиг, Питер (2003) [1995]. Искусственный интеллект: современный подход (2-е изд.). Prentice Hall. стр. 97–104. ISBN 978-0137903955.
25. Рассел, Стюарт ; Норвиг, Питер (2009) [1995]. Искусственный интеллект: современный подход (3-е изд.). Prentice Hall. стр. 103. ISBN 978-0-13-604259-4.
26. Кляйн, Дэн; Мэннинг, Кристофер Д. (2003). "A* parsing: fast exact Viterbi parse selection" (PDF) . Труды конференции 2003 Human Language Technology Conference Североамериканского отделения Ассоциации компьютерной лингвистики . стр. 119–126. doi :10.3115/1073445.1073461.
27. Kagan E.; Ben-Gal I. (2014). «Алгоритм группового тестирования с информационным обучением в режиме онлайн» (PDF) . IIE Transactions . 46 (2): 164–184. doi :10.1080/0740817X.2013.803639. S2CID  18588494. Архивировано из оригинала (PDF) 2016-11-05 . Получено 2016-02-12 .
28. Фергюсон, Дэйв; Лихачев, Максим; Стенц, Энтони (2005). "Руководство по эвристическому планированию пути" (PDF) . Труды международного семинара по планированию в условиях неопределенности для автономных систем, международная конференция по автоматизированному планированию и составлению расписаний (ICAPS) . стр. 9–18. Архивировано (PDF) из оригинала 29.06.2016.
29. Nau, Dana S.; Kumar, Vipin; Kanal, Laveen (1984). «Общие ветви и границы и их связь с A∗ и AO∗» (PDF) . Искусственный интеллект . 23 (1): 29–58. doi :10.1016/0004-3702(84)90004-3. Архивировано (PDF) из оригинала 2012-10-04.
30. "Варианты A*". theory.stanford.edu . Получено 2023-06-09 .
31. Хансен, Эрик А.; Чжоу, Ронг (2007). «Эвристический поиск в любое время». Журнал исследований искусственного интеллекта . 28 : 267–297. arXiv : 1110.2737 . doi : 10.1613/jair.2096 . S2CID  9832874.
32. Фарех, Рауф; Базияд, Мохаммед; Рахман, Мохаммад Х.; Раби, Тамер; Беттайеб, Маамар (2019-05-14). «Исследование стратегии планирования сокращенного пути для дифференциального колесного мобильного робота». Robotica . 38 (2): 235–255. doi :10.1017/S0263574719000572. ISSN  0263-5747. S2CID  181849209.
33. Pijls, Wim; Post, Henk. Yet another bidirectional algorithm for shortest paths (PDF) (Технический отчет). Эконометрический институт, Университет Эразма Роттердамского. EI 2009-10. Архивировано (PDF) из оригинала 2014-06-11.
34. Голдберг, Эндрю В.; Харрельсон, Крис; Каплан, Хаим; Вернек, Ренато Ф. «Эффективные алгоритмы кратчайшего пути от точки к точке» (PDF) . Принстонский университет . Архивировано (PDF) из оригинала 18 мая 2022 г.

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

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

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

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