Web

Поисковый алгоритм A Star: что это и как эффективно его использовать?

Lorem ipsum dolor

Алгоритм «A Star» это один из проверенных опытом алгоритмов, который используют для того, чтобы найти кратчайший путь между 2 вершинами графа, у которых положительный вес ребер. Данный алгоритм был описан еще в 1968 году П. Хартом, Н. Нильсоном и Б. Рафаэлем.

Алгоритм «A Star» всегда находит кратчайший путь, потому что применяет в своих расчетах вспомогательную функцию, которая всегда направляет поиск в нужном направлении, сокращая его длительность. Такая вспомогательная функция называется «эвристика», поэтому алгоритм «A Star» относят к категории «эвристических алгоритмов поиска».

 

Алгоритм «A Star»

Алгоритм «A Star» характеризуется тремя важными свойствами:

  • оптимальностью — это означает, что алгоритм гарантирует получение лучшего из возможных результатов;

  • полнотой — это означает, что алгоритм «A Star» всегда найдет решение, если оно существует;

  • эффективностью — на сегодняшний день нет других алгоритмов, которые смогут найти кратчайший путь быстрее, чем «A Star», применяя эвристическую функцию.

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

F(x) = G(x) + H(x) , где:

  • F(x) — это функция для вершины; чем меньше функция, тем «ближе» вершина стоит в очереди для посещения; данная функция оценивает минимальную стоимость перехода от вершины к вершине;

  • G(x) — это стоимость пути от первоначальной вершины и до любой другой;

  • H(x) — это эвристический показатель стоимости пути от вершины «х» и до конечной вершины.

Вычисляя F(x), за «х» берется соседняя вершина с уже посещенной. Поэтому получается, что алгоритм вычисляет стоимость всего пути у всех соседних вершин и останавливает выбор на той, у которой стоимость минимальна.

 

Как работает алгоритм «A Star»

Посетив одну конкретную вершину, алгоритм «A Star» перед переходом к следующей исследует все соседние вершины. Все вершины алгоритм разделяет на 3 категории:

  1. Неизвестные вершины. Это те, которые не были еще посещены и пока что даже не найдены. Получается, что и путь к ним пока остается загадкой. Таким образом, изначально все вершины, кроме стартовой, будут в этой категории.

  2. Известные вершины. Это те вершины, о которых уже известно алгоритму и уже даже известен путь к ним. Такие вершины сохраняются в «списке алгоритма» и становятся в очередь для их посещения и исследования. Из этого списка исследуются те вершины, которые считаются наиболее перспективными.

  3. Исследованные вершины. В эту категорию попадают те вершины, которые уже были посещены алгоритмом «A Star». К этим вершинам известен самый короткий путь, поэтому они попадают в «закрытый список» этот список нужен для того, чтобы исключить многократное исследование одних и тех же вершин.

Когда одна из вершин становится полностью исследованной, она попадает в категорию «исследованные вершины», а все ее соседи попадают в категорию «известные вершины» и становятся годными для исследования. На каждой уже исследованной вершине устанавливается указатель до той уже исследованной вершины, к которой у нее будет кратчайший путь.

Алгоритм «A Star» завершает свою работу только в том случае, если конечная вершина переносится в категорию «исследованные вершины». В этом случае уже будет весь список исследованных вершин, а на каждой из них будет стоять указатель с кратчайшим путем. Поэтому несложно будет по указателям отследить кратчайший путь от конечной вершины до начальной.

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

 

Алгоритм «A Star»: альтернативы

Алгоритм «A Star» не единственный в своем роде алгоритм, который используют для поиска кратчайших путей. У него есть два ближайших альтернативных алгоритма:

  • алгоритм Дейкстры;

  • «жадный» алгоритм.

Ни тот ни другой в своих расчетах не используют эвристическую функцию — этим они существенно отличаются от «A Star». Алгоритм Дейкстры осуществляет свой исследовательский переход от вершины к вершине, основываясь на стоимости текущего пути, то есть где меньше будет прирост стоимости пути, туда и движется алгоритм. Этот алгоритм часто применяют там, где неизвестна конечная вершина.

«Жадный» алгоритм определяет свой исследовательский путь от вершины к вершине, основываясь только на предположении, что через выбранную вершину, возможно, будет самый короткий маршрут.

Еще альтернативами алгоритму «A Star» являются следующие алгоритмы, у которых главное отличие от «A Star» это то, что им для работы требуется намного меньшее количество памяти:

  • IDA Star;

  • RBFS;

  • MA Star.

Эти алгоритмы считаются более быстродействующими, потому что потребляют в своей работе меньше памяти. Например, некоторые из них просто «забывают» посещенные вершины, которые точно не будут использованы для прокладки кратчайшего пути. Их применение оптимально, когда есть ограничения в использовании памяти.

Еще можно услышать про такой алгоритм, как «D Star». Фактически он является усовершенствованным алгоритмом «A Star». Еще его называют «динамический A».

 

Заключение

Алгоритм «A Star» довольно популярен при поиске кратчайшего пути, однако его применение ограничивается его главным недостатком — потребностью в большом количестве памяти, потому что алгоритм «A Star» хранит всю информацию об известных и исследованных вершинах. Из этого получается, что «A Star» не всегда пригоден для использования, поэтому нужно знать о его альтернативах, которым не нужен большой объем памяти для работы.

Схожие статьи

Web

Почему событие Onclick работает, даже если форма пуста? И после нажатия на кнопку submit появляется оповещение, которое показывает, что поле ввода является обязательным

Web

Когда использовать константу PHP «PHP_EOL»

Web

Принудительное использование SSL/https с помощью .htaccess и mod_rewrite

Web

Как распарсить и обработать HTML/XML в PHP?