А* алгоритам

Алгоритам А* за одређивање најкраћег пута између два чвора графа је један од фундаменталних и најпопуларнијих алгоритама вештачке интелигенције. Алгоритам је уопстење Дајкстриног алгоритма и обично смањује број чворова графа које треба испитати. То смањивање је засновано на коришћењу хеуристике која процењује доњу границу даљине до циљног чвора.

Прву верзију алгоритма А* су развили Peter E. Hart, Nils Nilson и Bertram Rafael на Истраживачком институту Стенфорд 1968. године, као унапређење Дајкстриног алгоритма из 1959. године.

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

Алгоритам А* обично смањује број чворова графа које треба испитати. То смањивање је засновано на коришћењу хеуристике која процењује доњу границу даљине до циљног чвора. Као и у Дајкстрином алгоритму, чворове који тек треба обрадити чувају се у реду, сортираном према неком критеријуму. Све време се одржавају листа отворених чворова — чворова који су већ посећени али нису обрађени сви њихови суседи и затворених чворова — чворова који су посећени и којима су обрађени сви њихови суседи. Кључна разлика је у томе што Дајкстрин алгоритам (као „неинформисани алгоритам“) узима у обзир само цену од полазног до текућег чвора, док А* (као „информисани алгоритам“) користи функцију евалуације $f$ над чворовима графа, дефинисану на следећи начин: $f(x)=g(x)+h(x)$ где је $g(x)$ цена пута од полазног чвора до чвора $x$, а $h(x)$ је процењена (хеуристичка) цена најјефтинијег пута од чвора $x$ до циљног чвора. Док трагамо за најкраћим путем, увек знамо текућу минималну цену од полазног чвора до чвора $x$ (тј. текућу вредност за $g(x)$), али се вредност $h(x)$ може само процењивати. Да би се обезбедила оптималност А* претраге, функција $h$ мора да буде конзистентна (енг. цонсистент), тј. да за било која два суседна чвора $x$ и $y$ важи: $h(x)<=c(x,y)+h(y)$ где је $c(x,y)$ цена придружена грани $(x,y)$. У неким специјалним случајевима довољно је да функција $h$ буде допустива (енг. адмиссибле), тј. да никада не прецењује цену стизања до циља. Својство конзистентности има за последицу својство допустивости. Додатно, допустиве функције су често и конзистентне.

Историја алгоритма

1968. године Нилс Нилссон је предложио хеуристички приступ за навигацију Схакеy тхе Робот кроз собу са препрекама. Овај алгоритам проналажења путева, назван А1, је био бржа верзија тадашњег најпознатијег формалног приступа, Дајкстра алгоритма. Бертрам Рапхаел је предложио нека значајна побољшања овог алгоритма, називајући ревидирану верзију А2. Након тога Петер Е. Харт је аргументовано показао да је А2 , са мањим изменама, најбржи алгоритам за проналажење најкраћих путева. Харт, Нилссон и Рапхаел су затим заједнички развили доказ којим су показали да је ревидирани А2 алгоритам оптималан за проналажење најкраћих путева под одређеним добро дефинисаним условима. Назвали су нови алгоритам А*.

Фазе алгоритма

Као и сви алгоритми претраге, А* прво претражује путеве који највероватније воде ка циљу. Од похлепне БФС претраге га разликује то што А* узима у обзир растојање које је већ прешао; део хеуристике $g(x)$ је цена од почетног чвора, а не само локална цена од претходно обиђеног чвора. Полазећи од почетног чвора, он памти у реду са приоритетом чворове које треба обићи, познат као отворен скуп. Што је нижа вредност функције $f(x)$ за задат чвор $x$ , већи му је приоритет. У сваком кораку алгоритма, чвор са најнижом вредношћу функције $f(x)$ се уклања из реда, ажурирају се вредности $f$ и $g$ његових суседа, и они се убацују у ред. Алгоритам се наставља све док вредност $f$ циљног чвора не буде најнижа у реду (или док има чворова у реду). Вредност $f$ циљног чвора представља дужину најкраћег пута, с обзиром на то да је вредност $h$ једнака нули у допустљивој хеуристици.

Претходно описан алгоритам нам даје само дужину најкраћег пута. Да би пронашли целокупан редослед корака, алгоритам се може лако преправити тако да сваки чвор на путу памти свог претходника. Након што је алгоритам завршен, сваки чвор ће показивати на свог претходника, све до циљног чвора. Поред тога, ако је хеуристика монотона (или конзистентна), затворен скуп чворова који су посећени се може искористити да унапреди претрагу.

Псеудокод

Алгоритам: Алгоритам А*

Улаз: Граф Г, полазни чвор соурце и циљни чвор гоал.

Излаз: најкраћи пут од чвора соурце до чвора гоал у графу Г (ако постоји пут између ова два чвора).

1. Иницијално је затворена листа празна.
2. Додај полазни чвор (заједно са процењеном ценом до циљног чвора, која је одређена функцијом х у отворену листу чворова које је потребно размотрити.
3. Извршавај следећу петљу док год има елемената у отвореној листи:
   • Изабери чвор н (зваћемо га текући чвор) из отворене листе који има најмању вредност ф(н).
   • Ако је текући чвор циљни чвор, извести о успеху, конструиши пут од полазног до циљног чвора (идући уназад - од циљног чвора) и заустави извршавање петље.
   • Испитај све чворове који су директно доступни из текућег чвора и при томе не припадају затвореној листи. За сваки такав чвор м уради следеће:
     • Ако он није у отвореној листи, додај га у отворену листу. Означи текући чвор као родитеља овог чвора (што је важно за конструисање стазе на крају). Израчунај и запамти вредности ф(м), г(м) и х(м) за чвор. (Приметимо да се вредности г(м) могу израчунати на инкременталан и ефикасан начин: вредност г(м) једнака је збиру вредности функције г за родитељ чвора м и цени пута од родитеља до м).
     • Ако је он већ у отвореној листи, провери да ли је одговарајући пут од полазног чвора до м бољи од текућег пута (преко чвора н). За ту проверу користи се вредност г(м). Мања вредност г значи да је тај пут бољи. Ако је текући пут бољи, промени информацију о родитељу чвора м на чвор н и ажурирај вредности г(м) и ф(м).

   • Избриши текући чвор из отворене листе и додај га у затворену листу чворова (он не треба да поново буде испитиван).

4. На крају, ако је петља завршена а да није пријављен успех (тада је отворена листа празна), онда не постоји тражени пут. Иначе, пут је пронађен и он се конструише од дете-родитељ веза (идући уназад од циљног чвора).

 1    function A*(start,goal)
 2        closedset := the empty set    // The set of nodes already evaluated.
 3        openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
 4        came_from := the empty map    // The map of navigated nodes.
 5
 6        g_score[start] := 0    // Cost from start along best known path.
 7        // Estimated total cost from start to goal through y.
 8        f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)
 9    
 10        while openset is not empty
 11            current := the node in openset having the lowest f_score[] value
 12            if current = goal
 13                return reconstruct_path(came_from, goal)
 14        
 15            remove current from openset
 16            add current to closedset
 17            for each neighbor in neighbor_nodes(current)
 18                tentative_g_score := g_score[current] + dist_between(current,neighbor)
 19                if neighbor in closedset and tentative_g_score >= g_score[neighbor]
 20                    continue
 21
 22                if neighbor not in openset or tentative_g_score < g_score[neighbor] 
 23                    came_from[neighbor] := current
 24                    g_score[neighbor] := tentative_g_score
 25                    f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
 26                    if neighbor not in openset
 27                        add neighbor to openset
 28
 29        return failure
 30
 31    function reconstruct_path(came_from, current_node)
 32        if current_node in came_from
 33            p := reconstruct_path(came_from, came_from[current_node])
 34            return (p + current_node)
 35        else
 36            return current_node

Пример

Илустрација А* алгоритма за проналажење пута од почетног чвора до циља у проблему планирања кретања робота. Празни кругови представљају чворове из отвореног скупа, тј. оне чворове које тек треба испитати, и обојени кругови представљају чворове из затвореног скупа. Боја сваког чвора из затвореног скупа указује на удаљеност од почетног чвора: што је чвор зеленији ближи је циљу. Може се приметити да се алгоритмом увек креће праволинијски од почетног чвора ка циљу, када се на путу наиђе на препреку испитују се алтернативни путеви кроз чворове из отвореног скупа.

Види још: Дајкстрин алгоритам

Пример А* алгоритма је тражење пута у графу где чвориови представљају градове, а гране путеве између градова, где је h(x) праволинијско растојање од почетног до крајњег града:

Зелена: Почетни град.
Плава: Крајњи град.

Нарандзаста: Посећени град.

Својства

Као и Претрага у Ширину, А* алгоритам је комплетан и увек проналази решење, уколико оно постоји. Ако је хеустичка функција $h$ допустива, што значи да никад не прецењује минималну цену за постизање циља, онда је и сам А* алгоритам допустив (оптималан), ако не користимо затворен скуп. Уколико пак, користимо затворен скуп, онда $h$ такође мора бити монотона (конзистентна) да би А* био оптималан. Ово значи да за сваки пар суседних чворова $x$ и $y$ , где је $d(x,y)$ дужина гране између њих, мора да важи: $h(x)<=d(x,y)+h(y)$ Овим је обезбеђено да за сваки пут $X$ од почетног чвора до $x$ важи:

$L(X)+h(x)<=L(X)+d(x,y)+h(y)=L(Y)+h(y)$

где је са $L(\cdot )$ означена дужина пута, а $Y$ је пут $X$ који обухвата чвор $y$. Другим речима, немогуће је смањити (укупно растојање до сад + преостао растојање ) проширивањем пута суседним чвором. Монотоност подразумева допустивост када је хеуристичка процена у било ком циљном чвору нула, јер (допуштајући да $P=(f,v_{1},v_{2},\ldots ,v_{n},g)$ буде најкраћи пут од било ког чвора $f$ до најближег циљног чвора $g$ ):

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

А* је такође оптималан за било коју хеуристику $h$, што значи да било који алгоритам који користи исту хеуристику, неће бити оптималнији од А*, осим уколико постоји више парцијалних решења где $h$ тачно предвиђа цену најкраћег пута. Чак и у овом случају, за сваки граф постоји неки ред прекидања веза у реду са приоритетом такав да А* испитује што је мање чворова.

Специјални случајеви

Обиласци графа у дубину и ширину могу се сматрати специјалним случајевима алгоритма А*.

За обилазак графа у дубину, може се користити алгоритам А* са g = 0 и погодно одабраном функцијом h. На пример, нека је бројач C иницијализован на неку веома велику вредност. Кад год обрађујемо неки чвор додајемо вредност C свим његовим суседима. Након сваке доделе смањујемо вредност C за један. Тиме ће вредност h(x) да буде већа за чворове на које се раније наишло. Приметимо да овако деfiнисана функција h није нужно допустива.

Дајкстрин алгоритам, као специјални случај обиласка графа у ширину такође је специјални случај алгоритма А* где је h(x) = 0 за сваки чвор x. Оваква функција h је допустива и конзистентна и гарантује налажење оптималног пута.
За g = 0, алгоритам А* понаша се у складу са најпре-најбољим, похлепним приступом који најпре обрађује чворове са најповољнијом хеурситичком вредношћу. Ова варијанта алгоритма није нужно оптимална.

Општи алгоритам А* често се примењује за налажење пута на униформној мрежи чворова (која одговара, на пример, дискретизованој мапи). Тада он добија специfiчну форму. Претпоставимо да је мрежа правилна (сачињена од квадрата) и да има правоугаону форму. Додатно, претпостављамо да неки чворови (тј. неки квадрати, нека поља мреже) нису доступни и да они представљају препреке. Свако поље је повезано са сваким суседним пољем (осим са препрекама), те има (изузев поља на рубу) осам суседних поља (али нека од њих могу бити препреке и као такве недоступне). У овој варијанти проблема, цене су придружене чворовима (пољима), а не гранама графа (везама између суседних чворова). У овом контексту, функција g(n) је збир свих цена поља дуж пута од полазног до поља n. На пример, сваком „хоризонталном“ или „вертикалном“ покрету може се придружити цена 1 а сваком дијагоналном цена $1.414\approx {\sqrt {2}}$ (оваква цена одговара Еуклидском растојању између средишта поља). Функција h може се описати на различите начине. Један од њих је Еуклидско растојање између два чвора, а један метод Менхетн у којем се броји укупан број поља пређених хоризонтално или вертикално да би се дошло од полазног поља до текућег поља. Приметимо да уколико су дозвољени дијагонални потези, онда Менхетн метод потенцијално прецењује растојање до циљног чвора и због тога не гарантује налажење најкраћег пута. Но, овај метод у пракси обично даје добре резултате и нађени путеви су обично довољно добри, чак и ако нису најкрачи. Када се одређује вредност h, могу да се игноришу све препреке јер вредност h(n) је процењено а не стварно растојање.

Када се алгоритам А* примењује за налажење пута на униформној мрежи, он даје кораке у осам могућих смерова што касније често доводи до неприродних путева сачињених од сегмената са једним од осам нагиба. Омекшавање (енг. smoothing) је техника за унапређивање таквих путева тако да они изгледају природније.

Потпуност и оптималност

Може се доказати да је алгоритам А* потпун и да је, под одређеним условима оптималан:

• Потпуност: Ако постоји пут између два чвора, алгоритам А* ће наћи један такав (наравно, уколико је расположиво довољно време и меморијски простор). Чак и ако је хеуристичка функција веома лоша, циљни чвор че бити достигнут у коначном броју корака.
• Оптималност: Од свих путева између два дата чвора, биче изабран најкраћи пут, уколико је функција хеуристике $h$ конзистентна. Уколико функција $h$ није допустива, али не прецењује стварно цену за више од д, онда је цена пута који ће пронаћи алгоритам А* скупљи од најкраћег за не више од д.

Уколико се не користи листа затворених чворова (тј. уколико се разматрају и суседни чворови који су већ били текући), да би алгоритам био оптималан довољно је да функција $h$ буде допустива (није неопходно да буде конзистентна).

Уколико се користи над стаблима, да би алгоритам био оптималан довољно је да функција $h$ буде ненегативна и допустива. Уколико функција $f$ одговара оптималном путу, онда алгоритам А* обрађује све чворове за које важи $f(n)<f^{*}(n)$ и неке чворове н за које важи $f(n)=f^{*}(n)$.

Сложеност

Временска сложеност алгоритма А* зависи од хеуристике. У најгорем случају, број обрађених чворова је експоненцијалан у односу на дужину најкраћег пута, али је полиномијалан ако функција хеуристике $h$ задовољава следећи услов:
$|h(x)-h^{*}(x)|\leq O(logh^{*}(x))$

где је $h^{*}$ оптимална хеуристика, тј. функција која враћа тачну цену пута од чвора x до циљног чвора. Другим речима, грешка функције $h$ не треба да расте брже од логаритма идеалне хеуристике.

Варијанте А* алгоритма

• D*
• ИДА*
• Ивична претрага
• Инкрементално хеуристичко претраживање
• СМА*
• Тета*

Литература

• Veštačka inteligencija, profesor Predrag Janičić, MATF, Beograd 2010. godina.
• A* with Jump point search
• Clear visual A* explanation, with advice and thoughts on path-finding
• Variation on A* called Hierarchical Path-Finding A* (HPA*)
• A* Algorithm tutorial

Спољашње везе

• A* Implementation in Java
• A* Implementation in C#
• A* Pathfinding in Objective-C (Xcode)
• StraightEdge open source java 2D path finding and lighting project focused on performance, with demos.