Введение
Алгоритм, используемый для поиска пути и обхода графа.
A* (произносится "А звезда") — это алгоритм обхода графа и поиска пути, который широко применяется во многих областях информатики благодаря своей полноте, оптимальности и эффективности. Для заданного взвешенного графа, начальной и конечной вершин алгоритм находит кратчайший путь (с учетом заданных весов) от начальной до конечной вершины. Основным практическим недостатком является его пространственная сложность, зависящая от глубины решения (кратчайшего пути) d и фактора ветвления b (среднего количества преемников в состоянии), поскольку он хранит все сгенерированные узлы в памяти. Поэтому в практических системах маршрутизации он часто уступает алгоритмам, способным предварительно обрабатывать граф для повышения производительности, а также алгоритмам с ограниченным объемом памяти. Однако, A* по-прежнему остается наилучшим решением во многих случаях. Питер Харт, Нильс Нильссон и Бертрам Рафаэль из Стэнфордского исследовательского института (ныне SRI International) впервые опубликовали этот алгоритм в 1968 году. Его можно рассматривать как расширение алгоритма Дейкстры. A* достигает более высокой производительности за счет использования эвристик для направления поиска. В отличие от алгоритма Дейкстры, A* находит только кратчайший путь от заданной начальной до заданной конечной вершины, а не дерево кратчайших путей от заданной начальной вершины ко всем возможным конечным вершинам. Это необходимый компромисс для использования целевой эвристики. В алгоритме Дейкстры, поскольку генерируется полное дерево кратчайших путей, каждая вершина является конечной, и не может быть использована специфическая эвристика, ориентированная на конкретную цель.
История
A* был создан в рамках проекта Shakey, целью которого было создание мобильного робота, способного планировать свои собственные действия. Нильс Нильссон первоначально предложил использовать алгоритм Graph Traverser для планирования пути робота Shakey. Graph Traverser ориентируется на эвристическую функцию h(n), оценивающую расстояние от узла n до целевого узла: он полностью игнорирует g(n), расстояние от начального узла до n. Бертрам Рафаэль предложил использовать сумму g(n) + h(n). Питер Харт сформулировал понятия, которые мы сейчас называем допустимостью и согласованностью эвристических функций. A* изначально был разработан для поиска путей с минимальной стоимостью, когда стоимость пути равна сумме его составляющих затрат, но было показано, что A* можно использовать для поиска оптимальных путей для любой задачи, удовлетворяющей условиям алгебры стоимостей. В оригинальной статье 1968 года утверждалось, что согласованность не требуется, однако это было опровергнуто в 1985 году в фундаментальном исследовании Дехтера и Перла об оптимальности A* (в настоящее время называемой оптимальной эффективностью), в котором был приведен пример A* с эвристикой, которая была допустимой, но не согласованной, и расширяла произвольно больше узлов, чем альтернативный алгоритм, подобный A*. Общий поиск в глубину можно реализовать с помощью A*, рассматривая наличие глобального счетчика C, инициализированного очень большим значением. Каждый раз, когда мы обрабатываем узел, мы присваиваем значение C всем его вновь обнаруженным соседям. После каждого присваивания мы уменьшаем счетчик C на единицу. Таким образом, чем раньше обнаружен узел, тем выше его значение h(x). Как алгоритм Дейкстры, так и поиск в глубину могут быть реализованы более эффективно без включения значения h(x) в каждый узел.
Прекращение и полнота
На конечных графах с неотрицательными весами ребер алгоритм A* гарантированно завершается и является полным, то есть он всегда находит решение (путь от начальной до целевой вершины), если оно существует. На бесконечных графах с конечным коэффициентом ветвления и стоимостью ребер, ограниченной снизу отличным от нуля значением (для некоторого фиксированного значения), алгоритм A* гарантированно завершается только в том случае, если решение существует. Авторы рассматривали различные определения Alts и P в сочетании со случаями, когда эвристика A* является лишь допустимой или одновременно допустимой и согласованной. Наиболее значимым положительным результатом, который они доказали, является то, что A* с согласованной эвристикой оптимально эффективен по отношению ко всем алгоритмам поиска, подобным A*, использующим допустимую эвристику, для всех "непатологических" задач поиска. Если говорить упрощенно, их понятие непатологической задачи соответствует современному пониманию "до разрешения связей". Этот результат не верен, если эвристика A* допустима, но не согласована. В этом случае Дехтер и Перл показали, что существуют алгоритмы, подобные A*, использующие допустимую эвристику, которые могут развернуть произвольно меньшее количество узлов, чем A*, для некоторых непатологических задач. Оптимальная эффективность относится к множеству развернутых узлов, а не к числу развертываний узлов (количеству итераций основного цикла A*). Когда используемая эвристика допустима, но не согласована, один и тот же узел может быть развернут алгоритмом A* многократно, в худшем случае – экспоненциальное количество раз. В таких ситуациях алгоритм Дейкстры может значительно превзойти A*. Однако более поздние исследования показали, что этот патологический случай возникает только в определенных искусственно созданных ситуациях, когда вес ребра графа поиска экспоненциально зависит от размера графа, и что некоторые несогласованные (но допустимые) эвристики могут привести к уменьшению числа развертываний узлов при поиске с помощью A*.