Алгоритъм А*

В областта на компютърните науки, алгоритъмът за търсене А* (произнася се „А-звезда“) е алгоритъм за намиране на път между начален и краен връх в граф.

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

Питър Харт, Нилс Нилсон и Бертрам Рафаел от Станфордския изследователски институт (сега SRI International) първи описват алгоритъма през 1968 г. Той е разширение на алгоритъма на Дейкстра от 1959 г. А* постига по-добри времеви резултати чрез използване на евристични методи за направляване на търсенето.

История

През 1968 г. специалистът по ИИ Нилс Нилсон се опитва да подобри подхода за планиране на пътища на Shakey – робот прототип, който може да се придвижва през помещение с препятствия. Алгоритъмът за намиране на път, наречен от него А1, е по-бърза версия на тогавашния най-добър подход, алгоритъма на Дейкстра, за намиране на най-кратките пътища в графи. Бертрам Рафаел предлага няколко съществени подобрения в този алгоритъм, наричайки подобрената версия А2. След това Питър Е. Харт прави малки промени и въвежда аргумент, който затвърждава А2 като най-добрия възможен към момента алгоритъм за намиране на най-кратките пътища. Впоследствие Харт, Нилсон и Рафаел заедно разработват доказателство, че подобреният алгоритъм А2 е оптимален за намиране на най-къси пътища при определени ясно дефинирани условия.

Описание

A* е алгоритъм за информирано търсене, или търсене по метода на най-доброто спускане (на английски: best-first search), което означава, че търси пътя с най-малка цена (изминато разстояние, изминало време и т.н.) измежду всички възможни пътища до решението (върха цел), като измежду тях избира първо тези, за които изглежда, че водят най-бързо до решението. Алгоритъмът се формулира в контекста на претеглен граф: започвайки от определен връх на графа, той конструира дърво от пътища, започващи от този връх, и ги удължава с по една стъпка на всяка итерация, докато някой от тях достигне върха цел.

На всяка итерация на основния си цикъл A* трябва да определи кой от частичните пътища да бъде продължен в една или повече посоки. За тази цел се използва оценка на цената (сумарното тегло), оставаща до върха цел. По-конкретно, A* избира пътя, за който

f(x)=g(x)+h(x)

има най-малка стойност, където g(x) е цената на оптималния път от началния връх до $x$ , а h(x) е евристика, оценяваща цената на оптималния път от $x$ до целта. Евристиката зависи от конкретната задача. За да бъде намерен действително най-късият път, евристичната оценка трябва да бъде приемлива (оптимистична), което означава, че никога не надценява действителната цена за достигане на най-близкия целеви връх.

Типичните реализации на A* използват приоритетна опашка за многократния избор на върхове с минимална (евристична) цена, които да бъдат продължени. Тази опашка се нарича множество на отворените върхове (open set) или фронт (fringe). На всяка стъпка върхът с най-ниска стойност на f(x) се премахва от опашката, изчисляват се стойностите на $f$ и $g$ за съседите му и те се добавят в опашката. Алгоритъмът продължава, докато се окаже, че някой от целевите върхове има по-ниска стойност на $f$ от който и да е връх в опашката (или докато опашката се изпразни).^[1] Тогава стойността на $f$ за целта е дължината на най-късия път, тъй като при приемлива евристика $h$ за целта е нула.

Описаният по-горе алгоритъм намира само дължината на най-късия път. За да се открие действителната последователност от стъпки, той може лесно да бъде допълнен, така че за всеки връх от пътя да се съхранява предшественикът му. След изпълнението на допълнения алгоритъм последният връх сочи към предшественика си, той към своя и т.н., докато поредният предшественик се окаже началният връх.

Като пример за евристика, при търсене на най-къс географски маршрут h(x) може да представлява разстоянието по права линия до целта, тъй като това е най-малкото възможно разстояние между две точки.

Ако h удовлетворява допълнителното условие h(x) ≤ d(x, y) + h(y) за всяко ребро (x, y) на графа (където $d$ е дължината на реброто), тя се нарича монотонна или постоянна. В този случай А* може да се реализира по-ефективно, тъй като няма нужда върховете да се обработват повече от веднъж (вижте множество от затворени върхове по-долу). Така А* става еквивалентен на алгоритъма на Дейкстра с понижена цена d'(x, y) = d(x, y) + h(y) − h(x).

Псевдокод

Долният псевдокод описва алгоритъма.

function A*(start, goal)
    // Множеството на вече разгледаните върхове
    closedSet := {}

    // Множеството върхове, които са открити, но още не са оценени.
    // Отначало е известен само началният връх.
    openSet := {start}

    // За всеки връх – от кой друг връх може да бъде достигнат най-ефективно.
    // Ако върхът е достижим от няколко върха, cameFrom ще съдържа най-ефективната
    // предходна стъпка.
    cameFrom := an empty map

    // За всеки връх – цената за достигане от началния връх до този връх.
    gScore := map with default value of Infinity

    // Цената за достигане от началния връх до началния връх е нула.
    gScore[start] := 0

    // За всеки връх – сумарната цена за достигане от началния връх до целта с
    // преминаване през този връх. Тази стойност е отчасти известна, отчасти евристика.
    fScore := map with default value of Infinity

    // За първия връх стойността е изцяло евристична.
    fScore[start] := heuristic_cost_estimate(start, goal)

    while openSet is not empty
        current := the node in openSet having the lowest fScore[] value
        if current = goal
            return reconstruct_path(cameFrom, current)

        openSet.Remove(current)
        closedSet.Add(current)

        for each neighbor of current
            if neighbor in closedSet
                continue		// Вече обходените съседи се игнорират.

            if neighbor not in openSet	// Откриване на нов връх
                openSet.Add(neighbor)

            // Разстояние от началото до съсед
            // Функцията "dist_between" се мени според изискванията към решението.
            tentative_gScore := gScore[current] + dist_between(current, neighbor)
            if tentative_gScore >= gScore[neighbor]
                continue		// Това не е по-добър път.

            // Това е най-добрият път до момента. Запомняме го!
            cameFrom[neighbor] := current
            gScore[neighbor] := tentative_gScore
            fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)

    return failure

function reconstruct_path(cameFrom, current)
    total_path := {current}
    while current in cameFrom.Keys:
        current := cameFrom[current]
        total_path.append(current)
    return total_path

Бележка: горният псевдокод приема, че евристичната функция е монотонна, което е често срещан случай в много практически задачи, например най-къси пътища в железопътни мрежи. Ако обаче това предположение не е валидно, върховете в множеството closed може да бъдат повторно открити и оценката им да се подобри. С други думи, множеството от затворени възли може да се пропусне, ако съществуването на решение е гарантирано или ако алгоритъмът се приспособи така, че новите върхове се добавят към множеството open само ако имат по-ниска стойност на f, отколкото на която и да е предишна итерация.

Илюстрация на търсене с A* в задача за планиране движение на робот. Празните кръгчета са върховете от *фронта*, т.е. тези, които очакват да бъдат изследвани, а запълнените са затворените върхове. Цветът на затворените върхове показва разстоянието от началото: по-зелено означава по-далеч. Вижда се как отначало A* върви по права линия към целта, а когато среща препятствие, изследва алтернативни пътища през върховете от фронта.

Пример

Пример за алгоритъма А* в действие, като върховете са градове, свързани с шосета, а h(x) е права линия до целевата точка:

Легенда: зелено: начало; синьо: цел; оранжево: посетен

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

Свойства

Също като обхождането в ширина, А* е пълен алгоритъм и винаги ще намери решение, ако съществува такова, стига за някое фиксирано $\varepsilon$ да е изпълнено ${\textstyle d(x,y)>\varepsilon >0}$ .

Ако евристичната функция $h$ е приемлива, тоест никога не надценява действителната минимална цена за достигане на целта, тогава и самият А* е приемлив (или оптимален), ако не използваме множество от затворени върхове. Ако се използва множество от затворени върхове, тогава $h$ трябва да бъде монотонна, за да бъде А* оптимален. Това означава, че за всяка двойка от съседни върхове $x$ и $y$ , ако $d(x,y)$ е дължината на реброто между тях, трябва да имаме:

h(x)\leq d(x,y)+h(y)

Това гарантира, че за всеки път $X$ от началния връх до $x$ е изпълнено:

L(x)+h(x)\leq L(X)+d(x,y)+h(y)=L(Y)+h(y)

където $L$ е функция, която означава дължината на път, а $Y$ е пътят $X$ , удължен с върха $y$ . С други думи, не е възможно да се намали (общото разстояние дотук + оставащото) чрез удължаване на път до съседен връх. (Това е аналогично на ограничението за неотрицателни тегла на ребрата в алгоритъма на Дейкстра). Монотонността предполага приемливост, когато евристичната оценка на някой от целевите върхове е нула, защото (ако $P=(f,v_{1},v_{2},\ldots ,v_{n},g)$ е най-краткият път от който и да е връх $f$ до най-близката цел $g$ ):

h(f)\leq d(f,v_{1})+h(v_{1})\leq d(f,v_{1})+d(v_{1},v_{2})+h(v_{2})\leq \ldots \leq L(P)+h(g)=L(P)

А* е също така оптимално ефективен за всяка евристика $h$ , което означава, че никой оптимален алгоритъм, използващ същата евристична функция, няма да изследва по-малко върхове от А*, освен когато има множество частични решения, за които $h$ точно прогнозира цената на оптималния път. Дори в този случай, за всеки граф съществува някакъв ред на разрешаване на конфликтите в опашката, при който А* проверява възможно най-малко върхове.

Частни случаи

Алгоритъмът на Дейкстра също е алгоритъм за търсене с равномерна цена и може да се разглежда като частен случай на А* с h(x) = 0 за всички x. Обхождането в дълбочина в общия случай може да се реализира чрез А*, като се използва глобален брояч C, инициализиран с много голяма стойност. Всеки път, когато обработваме връх, присвояваме С на всички новооткрити съседни върхове. След всяко отделно присвояване намаляваме брояча С с единица. По този начин колкото по-рано се намери даден връх, толкова по-голяма стойност за h(x) има той. Както алгоритъмът на Дейкстра, така и търсенето в дълбочина могат да бъдат реализирани по-ефективно без да се разглежда стойността на h(x) за всеки връх.

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

Някои прости оптимизации и подробности по реализацията могат значително да повлияят върху производителността на А*. Първо трябва да отбележим, че в определени ситуации начинът, по който приоритетната опашка разрешава конфликтите при елементи с равни оценки, може да се отрази сериозно на производителността. Ако конфликтите се разрешават чрез подреждане като в стек (LIFO), при равни по цена пътища А* ще работи като обхождане в дълбочина (ще проучва само по едно от няколко еднакво оптимални решения).

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

Приемливост и оптималност

Алгоритъмът А* е приемлив и обхожда по-малко върхове от всеки друг приемлив алгоритъм за търсене със същата евристика. Това е така, защото A* използва „оптимистична“ оценка на цената за пътя през всеки разглеждан връх, в смисъл че истинската цена на пътя през този връх към целта ще бъде поне толкова, колкото е оценката. Ключовото е, че доколкото А* „знае“, оптимистичната оценка е постижима.

За да се докаже приемливостта на A*, се използва полученият от алгоритъма път към решението по следния начин:

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

Да предположим, че друг алгоритъм за търсене Б завърши своето търсене с път, чиято действителна цена не е по-малка от очакваната цена за път през някой отворен връх. Въз основа на достъпната му евристична информация, алгоритъмът Б не може да изключи възможността пътят през този връх е с по-ниска цена. И така, макар че Б може да обходи по-малко възли от A*, той не може да бъде приемлив. Следователно A* обхожда най-малко върхове от всички приемливи алгоритми за търсене.

Това е вярно, само ако и двете твърдения са изпълнени:

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

Ограничено отслабване на критерия

Макар че критерият за приемливост гарантира решение, което е оптимален път, той означава също, че А* трябва да разглежда всички еднакво перспективни пътища, за да намери оптималния. Възможно е да се ускори търсенето за сметка на оптималността чрез отслабване на критерия за приемливост. Често искаме да ограничим това отслабване, за да можем да гарантираме, че съотношението между намерения път и оптималния е не по-лошо от $(1+\varepsilon )$ . Тази нова гаранция наричаме „ $\varepsilon$ -приемлив“.

Съществуват редица $\varepsilon$ -приемливи алгоритми:

Претеглен А*/Статично претегляне. Ако $h_{a}(n)$ е приемлива евристична функция, в претеглената версия на А* за евристика се използва $h_{w}(n)=\varepsilon h_{a}(n),\varepsilon >1$ и търсенето се изпълнява както обикновено (в крайна сметка то е по-бързо, отколкото с $h_{a}$ , защото се изследват по-малко върхове). Следователно цената на пътя, открит от алгоритъма, може да надвишава най-много $\varepsilon$ пъти тази на оптималния път през графа.
Вариантът с динамично претегляне използва оценяващата функция $f(n)=g(n)+(1+\varepsilon w(n))h(n)$ , където $w(n)={\begin{cases}1-{\frac {d(n)}{N}}&d(n)\leq N\\0&{\text{в прот. сл.}}\end{cases}}$ , като $d(n)$ е дълбочината на търсенето, а $N$ e очакваната дължина на пътя решение.
Вариантът с динамично претегляне на извадка използва представителна извадка на върховете с цел по-добро оценяване и компенсиране на системната грешка на евристиката.
$A_{\varepsilon }^{*}$ използва две евристични функции. Първата е списъкът FOCAL, който се използва за избиране на върхове кандидати, а втората, $hF$ – за избиране на най-перспективния връх от списъка FOCAL.
A_ε избира върхове с функцията $Af(n)+Bh_{F}(n)$ , където $A$ и $B$ са константи. Ако не могат да бъдат избрани върхове, алгоритъмът ще се върне назад с функцията $Cf(n)+Dh_{F}(n)$ , където $C$ и $D$ са константи.
AlphА* се опитва да дава предимство на обхождането в дълбочина, като предпочита скоро продължените възли. AlphА* използва оценяващата функция $f_{\alpha }(n)=(1+w_{\alpha }(n))f(n)$ , където $w_{\alpha }(n)={\begin{cases}\lambda &g(\pi (n))\leq g({\tilde {n}})\\\Lambda &{\text{в прот. сл.}}\end{cases}}$ , където $\lambda$ и $\Lambda$ са константи и $\lambda \leq \Lambda$ , $\pi (n)$ е родител на $n$ и ${\tilde {n}}$ е най-близкият продължен връх.

Сложност

Времевата сложност на А* зависи от използваната евристика. При най-лошия случай на търсене в неограничено пространство, броят на изследваните върхове е експоненциален спрямо дължината на решението (най-краткия път) $d$ : ${\mathcal {O}}(b^{d})$ , където $b$ е коефициентът на разклоняване (средният брой наследници на състояние). Това предполага, че съществува поне едно крайно състояние и то е достижимо от началното състояние; ако не е и пространството на състоянието е безкрайно, алгоритъмът ще е безкраен.

Оценяващата функция силно влияе върху практическото бързодействие на търсенето с A*, тъй като добрата евристика позволява на алгоритъма да отсече много от тези $b^{d}$ върха, които би изследвало евентуално неинформирано търсене. Качеството ѝ може да се изрази с помощта на действителния коефициент на разклоняване $b^{*}$ , който може да се определи емпирично за примерна задача, като се измери броят на изследваните възли, $N$ , и дълбочината на решението, а после се реши

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

Добри евристики са тези с нисък действителен коефициент на разклоняване (оптимумът е $b^{*}{=}1$ ).

Времевата сложност е полиномиална, когато пространството на търсенето е дърво, има едно-единствено крайно състояние и евристичната функция $h$ изпълнява следното условие:

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

,

където $h^{*}$ е оптималната евристика – точната цена за достигане от $x$ до целта. С други думи, грешката на $h$ няма да расте по-бързо от логаритъма на „съвършената евристика“ $h^{*}$ , която връща реалното разстояние от $x$ до целта.

Приложения

А* често се използва за търсене на път в приложения като игрите, но първоначално е проектиран като общ алгоритъм за обхождане на графи. Той намира приложение в решаването на различни задачи, включително синтактичен анализ чрез стохастични граматики в областта на обработката на естествени езици.

Бележки

↑ Целевите върхове може да се разглеждат по няколко пъти, ако остават други върхове с по-ниски стойности на $f$ , защото те могат да доведат до по-кратък път до някоя от целите.

Вижте също

Алгоритъм на Дейкстра, специален случай на А*, където h(n) = 0 за всички върхове.

Тази страница частично или изцяло представлява превод на страницата „А* search algorithm“ в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.

[1] Целевите върхове може да се разглеждат по няколко пъти, ако остават други върхове с по-ниски стойности на $f$ , защото те могат да доведат до по-кратък път до някоя от целите.

[1]