AlegsaOnline.com

A* (A-звезда) — алгоритъм за намиране на най-кратък път

A* (A‑звезда) — ефективен алгоритъм за намиране на най-кратък път: обяснение, сравнение с Дийкстра и примери за приложение в графи и навигация.

Автор: Leandro Alegsa Дата на създаване: 18 юни 2022 г. Последна актуализация: 22 септември 2025 г.

A* е набор от стъпки (алгоритъм), който компютрите използват, за да намерят най-краткия или най-евтиния път между две места в граф (набор от възли и връзки между тях). Ако имате списък с места и колко струва (или колко време отнема) да се премине директно от едно място до друго, A* може бързо да открие най-добрия маршрут. Алгоритъмът е свързан с алгоритъма на Дийкстра — в общия случай, когато евристиката е нула, A* става еквивалентен на Дийкстра — но A* прави „интелигентни предположения“ (евристика), за да не разглежда ненужно много пътища. Това е подходящ метод, ако искате един добър път между две точки. Ако трябва да намерите много пътища за всички двойки възли в една и съща карта, има алгоритми като Флойд–Уоршал, които могат да са по-ефективни за тази задача. A* не е подходящ за задачи като задачата за пътуващия търговец, където трябва да посетите много места в едно пътуване.

Как работи A*

Основната идея на A* е да комбинира вече изминатия разход и оценката за оставащия разстояние, за да приоритизира кои възли да се изследват първо. За всеки възел алгоритъмът поддържа три стойности:

g(n) — реалния разход от началния възел до възел n (колко струва вече пътят до тук);
h(n) — евристична оценка за разхода от n до целта (оценка на оставащото разстояние);
f(n) = g(n) + h(n) — оценка за общия разход през възел n.

Алгоритъмът използва две множества: open (възли, които предстои да се разгледат, обикновено реализирано като приоритетна опашка по f) и closed (възли, които вече са разгледани). Всяка стъпка A* вади от open възела с най-ниско f, разглежда съседите му и актуализира техните g/h/f стойности, докато не достигне целта.

Евристика (h)

Евристиката е важна за бързината и коректността на A*:

Адмисибилна евристика: никога не надценява истинския минимален разход до целта. Ако h е адмисибилна, A* гарантира, че ще намери оптимален (най-кратък) път.
Конзистентна (монотонна) евристика: за всяко ребро (n → m) важи h(n) ≤ cost(n,m) + h(m). Конзистентността гарантира, че f-стойността на възлите не намалява при разширяване и позволява проста реализация без повторни вмъквания в open.
Примери за евристики в равнинни мрежи: Манхатънско разстояние (за движение само по вертикал/хоризонтал), Евклидово разстояние (за движение в произволна посока), Чебишев (за движение и по диагонал с еднаква цена).

Свойства и сложност

Оптималност: Ако евристиката е адмисибилна (и особено ако е и конзистентна), A* намира оптимален път.
Пълнота: A* е пълен при крайни графи и положителни ребърни тежести — ще намери път, ако такъв съществува.
Времева и пространствена сложност: в най-лошия случай може да бъде експоненална по дълбочина/размер на графа, но в практиката — и с добра евристика — е много по-бърз от неевристични търсения като Дийкстра.

Основни стъпки (псевдокод като последователност)

Постави началния възел в open с g(start)=0 и f=start.h.
Докато open не е празно:
- Вземи възела current от open с най-ниско f.
- Ако current е целта → възстанови пътя чрез проследяване назад и приключи.
- Премести current в closed.
- За всеки съсед neighbor на current:
  - Изчисли tentative_g = g(current) + cost(current, neighbor).
  - Ако neighbor е в closed и tentative_g ≥ g(neighbor) → пропусни.
  - Ако neighbor не е в open или tentative_g < g(neighbor):
    - Актуализирай g(neighbor) = tentative_g, запази parent pointer към current, и пресметни f = g + h.
    - Ако neighbor не е в open → вмъкни го в open.

Практически съвети за имплементация

Използвайте ефективна приоритетна опашка (heap) за open; за поддръжка на актуализации може да е полезна структура, която поддържа намаление на ключ (decrease-key) или запис на записи с версия/идентификатор.
Поддържайте parent (предходник) за всеки възел, за да може да възстановите пътя при достигане на целта.
За големи карти помислете за варианти като итеративен дълбочинен A* (IDA*), Jump Point Search (за решетки) или предварително изчислени навигационни мрежи, за да намалите паметните и временни разходи.
В реални приложения често се използват и практични оптимизации: ограничение на обхвата, използване на евристики, комбиниране с водещи алгоритми за предварително маршрутизиране и др.

Къде се използва A*

Видео игри и симулации — за навигация на герои и NPC.
Роботика и автономни превозни средства — за планиране на траектории.
Географски информационни системи (карти и навигация).
Всички задачи, където трябва бързо да се намери един най-добър път между две точки при познати преходни разходи.

Разширения и варианти

Weighted A* — използва f = g + w·h (w > 1) за по-бързи, но евентуално ненапълно оптимални решения.
IDA* — итеративно задълбочаване, което намалява паметните изисквания.
Theta* и други алгоритми — търсят по-гладки или по-кратки траектории в непрекъснати пространства.

A* е много практичен и гъвкав инструмент за търсене на кратки пътища. С правилно избрана евристика и подходяща структура за данни той често намира оптималния маршрут много по-бързо от класическото безевристично търсене.

Стъпките

A* първо се нуждае от списък на всички места, до които можете да отидете, а след това от списък на разстоянието между тях. След това ще ви посочи най-бързия начин да стигнете от място А до място Z.

За пример ще кажем, че A е свързан с местата B и C, а B и C са свързани с D и E. D и E са свързани с Z. Има 4 възможни начина да отидете от A до Z. Можете да отидете A-B-D-Z, A-C-D-Z, A-B-E-Z или A-C-E-Z. Компютърът, използващ A*, първо поглежда колко трудно е да се стигне от A до B и от A до C. Това е "цената" за тези места. Цената на дадено място означава колко трудно е да се стигне от А до това място. След като запише двете разходи, компютърът разглежда колко трудно е да се стигне от B до D и добавя това към разходите на B. Той записва това като цена на D. След това компютърът поглежда колко трудно е да се стигне от C до D и добавя това към разходите на C. Това е различна цена за D и ако тя е по-малка от тази, която вече има, той ще замени старата. Компютърът иска да знае само най-добрия път, затова пренебрегва пътя с по-висока цена. Той ще запомни само един от A-B-D и A-C-D, в зависимост от това кой е по-бърз.

Компютърът продължава и намира най-бързия начин да стигне до E. Накрая той преминава от D до Z и намира цена, а от E до Z и намира цена. Той получава крайната цена за Z и това е най-малката цена, която може да получи. Сега компютърът знае кой път е най-бърз и има отговор. Компютърът може да направи подобна поредица от стъпки, но с много, много повече места. Всеки път той ще разглежда мястото, което е най-близо до А, и ще сумира разходите за съседите на това място.

Горната поредица от стъпки се нарича алгоритъм на Дийкстра. Алгоритъмът на Дийкстра може да бъде бавен, тъй като ще търси на много места, които може да се намират в погрешна посока от Z. Ако попитате компютъра как да стигнете от един град до близък, алгоритъмът на Дийкстра може да се окаже, че търси в друга държава.

A* решава този проблем. A* ви позволява да кажете на компютъра колко ще е разстоянието от всяко място до края. Компютърът може да използва предположението, за да определи приблизително колко време ще отнеме да се стигне от определено място до Z. Вместо да избере само мястото, което е най-близо до А, той ще разгледа това, което вероятно ще има най-малък общ сбор. Той намира тази обща сума, като добавя разходите към очакваното оставащо разстояние. По този начин той може да търси само в посока, в която нещата вероятно ще се подобрят. Не е проблем, ако предположението не е перфектно, но дори едно обикновено лошо предположение може да накара програмата да работи много по-бързо. Ако се опитвате да намерите път между две места в реалния свят, доброто предположение е просто разстоянието между тях по права линия. Реалният път по пътищата ще бъде по-дълъг, но това позволява на програмата да го познае и тя няма да тръгне в грешна посока.

В литературата по математика и информатика това предположение често е функция на мястото и се нарича евристика. Всяко място е връх, а всеки път между две места е ребро. Това са думи от теорията на графите.