A* algoritmus

Az A* (A csillagnak ejtve) egy gráfbejáró és útvonalkeresési algoritmus, amelyet teljessége, optimális hatékonysága miatt gyakran használnak a számítástechnikában.^[1] Az egyik fő gyakorlati hátránya az ${\displaystyle O(b^{d})}$ tárhelybonyolultsága, mivel az összes generált csomópontot eltárolja a memóriában. Így a gyakorlati útkereső rendszerekben általában jobban teljesítenek nála olyan algoritmusok, amelyek képesek a gráf előfeldolgozására a jobb teljesítmény érdekében,^[2] ahogy a memóriakorlátos megközelítések is. Sok esetben azonban az A* továbbra is a legjobb megoldás.^[3]

Peter Hart, Nils Nilsson és Bertram Raphael a Stanford Kutatóintézetben (ma SRI International) 1968-ban publikálta először az algoritmust.^[4] Ez Edsger Dijkstra 1959-es algoritmusa kiterjesztésének tekinthető. Az A* azáltal ér el jobb teljesítményt, hogy heurisztikát használ a keresés irányításához.

Az A*-ot a Shakey projekt részeként hozták létre, amelynek célja egy mobil robot felépítése volt, amely meg tudja tervezni a saját tevékenységeit. Nils Nilsson eredetileg a Graph Traverser algoritmus^[5] használatát javasolta Shakey útjának tervezéséhez.^[6] A Graph Traverser algoritmust egy ${\displaystyle h(n)}$ heurisztikus függvény, az ${\displaystyle n}$ csúcstól a célcsúcsig becsült távolság vezérli: teljesen figyelmen kívül hagyja ${\displaystyle g(n)}$-t, a kezdőcsúcstól ${\displaystyle n}$-ig való távolságot. Bertram Raphael a ${\displaystyle g(n)+h(n)}$ összeg használatát javasolta. Peter Hart alkotta meg azokat a fogalmakat, amelyeket ma a heurisztikus függvények megengedhetőségének (admissibility) és konzisztenciájának vagy monotonitásának (consistency/monotonity) hívunk.^[7] Az A*-ot eredetileg a legolcsóbb útvonalak megtalálására tervezték, amikor egy út költsége a élköltségek összege. De kimutatták, hogy az A* felhasználható bármely olyan probléma megoldására, ahol egy költségalgebra feltételeinek megfelelő optimális útvonalak megtalálása a cél.^[8]

Az eredeti 1968-as A*-cikkben^[4] szerepel egy tétel, miszerint egyetlen A*-hoz hasonló algoritmus^[9] sem tud kevesebb csúcsot kiterjeszteni, mint az A*, ha a heurisztikus függvény monoton, és az egyenlőséget feloldó szabályok (tie-breaking rule-ok) megfelelően vannak megválasztva. Néhány évvel később egy „korrekciót” tettek közzé,^[10] amelyben azt állították, hogy nincs szükség monotonitásra, de ezt Dechter és Pearl cáfolta az A* optimálisságáról (mai megnevezéssel optimális hatékonyságról) szóló végleges tanulmányában, amiben példát adtak az A*-ra egy olyan megengedhető, de nem monoton heurisztikával, ami tetszőlegesen több csúcsot terjeszt ki egy alternatív A*-szerű algoritmusnál.^[11]

Az A* egy informált keresőalgoritmus, avagy legjobbat először keresés, vagyis súlyozott gráfokkal van megfogalmazva: a gráf egy adott kezdőcsúcsából kiindulva arra törekszik, hogy olyan utat keressen az adott célcsomóponthoz, amelynek a legkisebb a költsége (a legrövidebb távolság, a legrövidebb idő stb.). Ezt a kezdőcsúcsból induló utak fájának karbantartásával és az utakhoz az élek egyenkénti hozzáfűzésével teszi, amíg el nem éri a terminálási feltételét.

A fő ciklus minden iterációjánál az A*-nak meg kell határoznia a kiterjesztendő utat. Ehhez az út költségét és a cél eléréséhez szükséges becsült költséget veszi figyelembe. Pontosabban, az A* kiválasztja az

${\displaystyle f(n)=g(n)+h(n)}$

függvényt minimalizáló utat, ahol n az úton található következő csúcs, g(n) a kezdőcsúcstól n-ig tartó út költsége, és h(n) egy heurisztikus függvény, amely az n-től a célig vezető legolcsóbb út költségét becsli. Az A* akkor fejeződik be, amikor a kezdőcsúcstól a célcsúcsig vezető utat próbálná kiterjeszteni, vagy ha nincsenek kiterjesztendő utak. A heurisztikus függvény problémaspecifikus. Ha a heurisztikus függvény megengedhető (azaz soha nem becsüli felül a cél eléréséhez szükséges tényleges költségeket), akkor az A* garantáltan a kezdőcsúcstól a célcsúcsig vezető optimális utat adja meg.

Az A* tipikus megvalósítása egy prioritásos sort alkalmaz a kiterjesztendő, minimális (becsült) költségű csúcsok ismételt kiválasztásához. Ezt a prioritásos sort nyílt halmaznak vagy peremnek nevezzük. Az algoritmus minden lépésénél a legkisebb f(x) értékű csomópontot eltávolítja a sorból, a szomszédainak f és g értékeit ennek megfelelően frissíti, és ezeket a szomszédokat hozzáadja a sorhoz. Az algoritmus addig folytatódik, amíg a célcsúcs alacsonyabb f értékkel nem rendelkezik, mint a sorban lévő bármelyik csomópont (vagy amíg a sor ki nem ürül).^{[* 1]} A cél f értéke ekkor a legrövidebb út költsége, mivel h értéke nulla a célcsúcsban megengedhető heurisztika esetén.

Az eddig leírt algoritmus csak a legrövidebb út hosszát adja meg. A tényleges lépések sorrendjének megtalálásához az algoritmus könnyen módosítható úgy, hogy az útvonalon lévő minden csúcsban eltároljuk a szülőcsúcsát. Az algoritmus terminálása után a célcsúcs az elődjére mutat, és így tovább, amíg valamelyik csúcs elődje a kezdőcsúcs.

Például amikor a térképen a legrövidebb utat keressük, a h(x) képviselheti a célhoz vezető légvonalbeli távolságot, mivel fizikailag ez a lehető legkisebb távolság a két pont között.

Ha a h heurisztika kielégíti a h(x) ≤ d(x, y) + h(y) kiegészítő feltételt a gráf minden (x, y) élére (ahol d az adott él hosszát jelöli), akkor h monoton vagy konzisztens. Konzisztens heurisztikával garantált, hogy az A* optimális utat talál egy csomópont többszöri feldolgozása nélkül, és A* egyenértékű Dijkstra algoritmusának futtatásával a ${\displaystyle d'(x,y)=d(x,y)+h(y)-h(x)}$ csökkentett költséggel.

A következő pszeudokód leírja az algoritmust:

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

// Az A* keres egy utat a kezdőcsúcsból a célcsúcsba.
// h a heurisztikus függvény. h(n) becsüli a cél elérésének
// költségét az n csúcsból kiindulva.
function A_Star(start, goal, h)
  // A felfedezett csúcsok halmaza, amelyeket szükséges lehet (újra) kiterjeszteni.
  // Induláskor csak a kezdőcsúcs ismert.
  // Ez általában egy min-kupaccal vagy prioritásos sorral van megvalósítva,
  // nem hasításos halmazzal.
  openSet := {start}

  // Az n csúcsra cameFrom[n] az azt közvetlenül megelőző csúcs a kezdőcsúcsból
  // n-be vezető legolcsóbb eddig ismert úton.
  cameFrom := an empty map

  // Az n csúcsra gScore[n] a kezdőcsúcsból n-be vezető legolcsóbb eddig ismert
  // út költsége.
  gScore := map with default value of Infinity
  gScore[start] := 0

  // Az n csúcsra fScore[n] := gScore[n] + h(n). fScore[n] értéke az aktuális
  // legjobb becslésünk a kezdőcsúcsból a célcsúcsba vezető, n-en átmenő
  // optimális út költségére.
  fScore := map with default value of Infinity
  fScore[start] := h(start)

  while openSet is not empty
    // Ez a művelet O(1) idejű, ha openSet min-kupac vagy prioritásos sor
    current := the node in openSet having the lowest fScore[] value
    if current = goal
      return reconstruct_path(cameFrom, current)

    openSet.Remove(current)
    for each neighbor of current
      // d(current,neighbor) a jelenlegiből a szomszéd csúcsba vezető él költsége
      // tentative_gScore a kezdőcsúcsból az aktuális csúcson át a szomszédba
      // vezető út költsége
      tentative_gScore := gScore[current] + d(current, neighbor)
      if tentative_gScore < gScore[neighbor]
        // Ez a szomszédba vezető út jobb minden eddiginél. Rögzítsük!
        cameFrom[neighbor] := current
        gScore[neighbor] := tentative_gScore
        fScore[neighbor] := gScore[neighbor] + h(neighbor)
        if neighbor not in openSet
          openSet.add(neighbor)

  // A nyílt halmaz üres, de soha nem értük el a célcsúcsot
  return failure

Megjegyzés: Ebben a pszeudokódban, ha egy csúcsot elérünk egy úttal, eltávolítjuk a nyílt halmazból, majd ha később egy olcsóbb útvonalon újra elérjük, akkor az ismét hozzáadódik a nyílt halmazhoz. Ez elengedhetetlen annak garantálásához, hogy a visszaadott út optimális legyen, ha a heurisztikus függvény megengedhető, de nem konzisztens. Ha a heurisztika konzisztens, akkor, amikor egy csúcs kikerül a nyílt halmazból, akkor az elérési út garantáltan optimális lesz, tehát a csúcs újabb elérésekor a tentative_gScore < gScore [neighbor] feltétel mindig hamis.

Példa egy működő A* algoritmusra, ahol a csomópontok utakkal összekötött városok, és h(x) a célponthoz való egyenes távolság:

Kulcs: zöld: kezdőcsúcs; kék: célcsúcs; narancs: meglátogatott

Az A* algoritmus valós alkalmazásokkal is rendelkezik. Ebben a példában az élek vasútvonalak, és h(x) a főköri távolság (a lehető legrövidebb gömbfelületi távolság) a célig. Az algoritmus utat keres Washington és Los Angeles között.

Számos egyszerű optimalizálás vagy megvalósítási részlet létezik, amelyek jelentősen befolyásolhatják az A* megvalósítási teljesítményét. Az első fontos részlet az, hogy a prioritási sor hogyan kezeli az azonos heurisztikusfüggvény-értékeket, mert ez bizonyos helyzetekben jelentős hatással lehet a teljesítményre. Ha ilyen esetben a sor LIFO módon viselkedik, akkor A* mélységi keresésként viselkedik az egyenlő költségek között (elkerülve, hogy egynél több egyformán optimális megoldást fedezzen fel).

Ha a keresés végén elérési út szükséges, általában minden csomópontnál hivatkozást kell megadni a csomópont szülőjére. A keresés végén ezek a referenciák felhasználhatók az optimális út visszaállítására. Ha ezeket a hivatkozásokat megtartjuk, akkor fontos lehet, hogy ugyanaz a csomópont csak egyszer jelenjen meg a prioritásos sorban (mindegyik bejegyzés a csomópont eltérő útvonalának felel meg, és mindegyik eltérő költséggel rendelkezik). Általános megközelítés itt annak ellenőrzése, hogy a hozzáadandó csomópont már megjelenik-e a prioritásos sorban. Ha igen, akkor a prioritást és a szülőmutatót módosítjuk, hogy azok megfeleljenek az alacsonyabb költségű útnak. A szokásos bináris halom alapú prioritási sor nem támogatja közvetlenül egyik elemének keresését sem, de kiegészíthető egy hash táblával, amely leképezi az elemeket a halomban lévő helyzetükre, lehetővé téve ezzel a végrehajtáskor a prioritáscsökkentési művelet időigényének logaritmikusra csökkentését. Alternatív megoldásként egy Fibonacci-halom ugyanazokat a prioritáscsökkentési műveleteket hajthatja végre konstans amortizált időben.

Dijkstra algoritmusa, mint egy egységes költségű keresési algoritmus további példája, tekinthető az A* speciális esetének, ahol h(x) = 0 minden x-re.^[12][13] Az általános mélységi keresés az A* használatával valósítható meg, figyelembe véve, hogy létezik egy nagyon nagy értékkel inicializált globális C számláló. Minden egyes csomópont feldolgozásakor C-t rendelünk az összes újonnan felfedezett szomszédához. Minden egyes hozzárendelés után csökkentjük a C számlálót eggyel. Így minél korábban fedez fel egy csomópontot, annál magasabb h(x) értéke. Mind Dijkstra algoritmusa, mind a mélységi keresés hatékonyabban megvalósítható anélkül, hogy el kellene tárolni h(x) értékét minden csúcshoz.

A nem negatív élsúlyú véges gráfokon hogy az A* garantáltan terminál, és teljes, azaz mindig megtalálja a megoldást (egy utat a kezdetektől a célig), ha létezik. Végtelen gráfokon, véges elágazási tényezővel és pozitív alsó korlátú élköltséggel (${\textstyle d(x,y)>\varepsilon >0}$ valamely rögzített ${\displaystyle \varepsilon }$-ra) az A* csak akkor terminál garantáltan, ha van megoldás.

A keresési algoritmus megengedhető, ha garantáltan megtalálja az optimális megoldást. Ha az A* által használt heurisztikus függvény megengedhető, akkor A* is megengedhető. Ennek intuitív „bizonyítéka” a következő:

Amikor A* befejezi a keresést, megtalált egy utat az kezdőcsúcstól a célig, amelynek tényleges költsége alacsonyabb a kezdőcsúcstól a célig tartó bármely út becsült költségénél bármely nyúlt csúcson át (azaz a csúcs f értékénél). Ha a heurisztika megengedhető, ezek a becslések optimisták (nem egészen – lásd a következő bekezdést), így az A* biztonságosan figyelmen kívül hagyhatja ezeket a csomópontokat, mert nem vezethetnek a meglévőnél olcsóbb megoldáshoz. Más szóval az A* soha nem hagyja figyelmen kívül az alacsonyabb költségekkel járó út lehetőségét a kezdetektől a célig, ezért folytatja a kutatást, amíg ilyen lehetőségek léteznek.

A tényleges bizonyíték egy kicsit bonyolultabb, mert a nyílt csúcsok f értékei nem garantáltan optimálisak, még megengedhető heurisztika esetén sem. Ennek oka az, hogy a nyitott csomópontok g értéke nem garantáltan optimális, tehát az összeg g+h nem feltétlenül optimális.

Az A algoritmus optimálisan hatékony alternatív algoritmusok Alt halmazára nézve a P problémahalmazon, ha P minden P problémájára és Alts minden A′ algoritmusára az A által P megoldása közben kiterjesztett csúcsok halmaza (nem feltétlenül valódi) részhalmaza az A′ által P megoldása közben kiterjesztett csúcsokénak. Az A* optimális hatékonyságának végleges vizsgálata Rina Dechter és Judea Pearl eredménye.^[11] Az Alts és a P sokféle meghatározását tekintették mind megengedhető, mind monoton és megengedhető A*-heurisztikákkal. A legérdekesebb pozitív eredmény, amelyet bebizonyítottak, hogy az A* monoton heurisztikával optimálisan hatékony az összes megengedhető A*-hoz hasonló keresési algoritmusra nézve az összes „nem patologikus” keresési probléma esetén. Ez az eredmény nem érvényes, ha az A* heurisztikája megengedhető, de nem monoton. Ebben az esetben Dechter és Pearl megmutatta, hogy léteznek olyan megengedhető A*-hoz hasonló algoritmusok, amelyek bizonyos nem patologikus problémák esetén tetszőlegesen kevesebb csomópontot tudnak kiterjeszteni, mint az A*.

Az optimális hatékonyság a kiterjesztett csúcsok halmazáról szól, nem a kiterjesztések számáról (A* fő ciklusának iterációszámáról). Ha a heurisztika megengedhető, de nem monoton, akkor egy csúcsot az A* többször, legrosszabb esetben exponenciálisan sokszor is kiterjeszthet.^[14] Ilyen körülmények között Dijkstra algoritmusa jelentősen felülmúlhatja az A*-ot.

Noha a megengedhetőségi kitétel garantálja az optimális megoldási utat, ez azt is jelenti, hogy az A*-nak meg kell vizsgálnia az összes egyformán érdemes utat az optimális megtalálásához. Hozzávetőlegesen legrövidebb utak kiszámításához a megengedhetőség kritériumának enyhítésével fel lehet gyorsítani a keresést az optimalitás rovására. Gyakran szeretnénk úgy korlátozni ezt az enyhítést, hogy garantáljuk, hogy a megoldás útja nem rosszabb, mint az optimális megoldási út ${\displaystyle (1+\varepsilon )}$-szorosa. Ezt az új garanciát ε-megengedhetőnek nevezzük.

Számos ε-megengedhető algoritmus létezik:

• Súlyozott A* / statikus súlyozás.^[15] Ha ${\displaystyle h_{a}(n)}$ egy megengedhető heurisztikus függvény, az A* súlyozott változata a ${\displaystyle h_{w}(n)=\varepsilon h_{a}(n)}$ (${\displaystyle \varepsilon >1}$) heurisztikus függvényt használva a szokasos módon végzi el az A* keresést (ami végül gyorsabban történik, mint ${\displaystyle h_{a}}$ használatával, mivel kevesebb csúcs kiterjesztésére kerül sor). Ennélfogva a keresési algoritmus által megtalált út legfeljebb költsége legfeljebb ε-szorosa a gráf legolcsóbb útjának költségének.^[16]
• A dinamikus súlyozás^[17] az ${\displaystyle f(n)=g(n)+(1\!+\!w(n))h(n)}$ költségfüggvényt használja, ahol ${\displaystyle w(n)={\begin{cases}1-{\frac {d(n)}{N}},&d(n)\leq N\\0,&d(n)>N\end{cases}}}$, ahol d(n) a keresés mélysége, N pedig a megoldási út várható hossza.
• A mintavételezett dinamikus súlyozás^[18] a csomópontok mintavételével a heurisztikus hibát jobban becsüli meg és távolítja el.
• ${\displaystyle A_{\varepsilon }^{*}}$.^[19] két heurisztikus függvényt használ. Az első a FOCAL lista, amelyet a jelölt csomópontok kiválasztására használunk, a második h_F pedig a legígéretesebb csomópont kiválasztására szolgál a FOCAL listából.
• A_ε a ${\displaystyle Af(n)+Bh_{F}(n)}$ függvénnyel választja ki a csúcsokat, ahol A és B konstans. Ha nem lehet egyetlen csúcsot sem kiválasztani, akkor az algoritmus visszalép a ${\displaystyle Cf(n)+Dh_{F}(n)}$ függvényhez, ahol C és D konstans.
• Az AlphA*^[20] megpróbálja elősegíteni az mélységi kiaknázást azáltal, hogy a nemrégiben kibővített csomópontokat részesíti előnyben. Az AlphA* az ${\displaystyle f_{\alpha }(n)=(1+w_{\alpha }(n))f(n)}$ költségfüggvényt használja, ahol ${\displaystyle w_{\alpha }(n)={\begin{cases}\lambda ,&g(\pi (n))\leq g({\tilde {n}})\\\Lambda ,&g(\pi (n))>g({\tilde {n}})\end{cases}}}$, ahol λ és Λ konstans, ${\displaystyle \lambda \leq \Lambda }$, ${\displaystyle \pi (n)}$ az ${\displaystyle n}$ szülője, és ${\displaystyle {\tilde {n}}}$ a legutóbb kiterjesztett csúcs.

Az A* időbonyolultsága a heurisztikától függ. Legrosszabb esetben egy korlátlan keresőtérben a kibontott csomópontok száma exponenciális a megoldás (a legrövidebb út) d mélységében: O(b^d), ahol b az elágazási tényező (az utódok átlagos száma állapotonként). Ez feltételezi, hogy egy célállapot egyáltalán létezik, és a kiindulási állapotból elérhető; ha nem, és az állapottér végtelen, akkor az algoritmus soha nem terminál.

A heurisztikus függvény nagymértékben befolyásolja az A* keresés gyakorlati végrehajtását, mivel egy jó heurisztika lehetővé teszi, hogy az A* a ${\displaystyle b^{d}}$ csúcsból sok olyat lemetsszen, amit egy nem informált keresés kiterjesztene. Minőségét kifejezhetjük b* effektív elágazási tényezőjével, amelyet empirikusan meg lehet határozni egy probléma esetén a kiterjesztett csúcsok számának, N-nek és a megoldás mélységének megmérésével, majd az

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

egyenlet megoldásával.

A jó heurisztika alacsony effektív elágazási tényezővel rendelkezik (az optimális b* = 1).

Az időbonyolultsága polinomiális, ha a keresési tér egy fa, egyetlen célállapot van, és a h heurisztikus függvény megfelel a

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

feltételnek, ahol h^* az optimális heurisztika, az x-től a célig való eljutás pontos költsége. Más szóval, a h hibája nem fog gyorsabban növekedni, mint a h^* „tökéletes heurisztika” logaritmusa, amely az x-től a célig tartó valódi távolságot adja vissza.^[16]

Az A* tárhelybonyolultsága nagyjából ugyanaz, mint az összes többi gráfkeresési algoritmusé, mivel az összes generált csomópontot a memóriában tartja.^[1] A gyakorlatban ez az A* keresés legnagyobb hátránya, ami az olyan memóriakorlátos heurisztikus keresések kifejlesztéséhez vezet, mint például az A* iteratív mélyítése, a memóriakorlátos A* és az SMA*.

Az A*-ot gyakran használják az általános útmeghatározási problémára olyan alkalmazásokban, mint például a videójátékok, de eredetileg egy általános gráfbejáró algoritmusnak tervezték.^[4] Számos különféle problémában alkalmazzák, beleértve a sztochasztikus nyelvtanok elemzésével kapcsolatos problémát az a természetes nyelvek feldolgozásakor.^[21] Használják ezen kívül például online tanulásos információs keresésben is.^[22]

Az A*-ot az különbözteti meg egy mohó best-first algoritmustól, hogy figyelembe veszi a már megtett költségeket/távolságot, g(n)-t.

Dijkstra algoritmusának néhány általános változatát az A* speciális esetének tekinthetjük, ahol heurisztika ${\displaystyle h(n)=0}$ minden csúcsra, miközben Dijkstra és A* egyaránt a dinamikus programozás speciális esetei. Maga az A* az elágazás és korlátozás egy általánosításának egy speciális esete.^[23]

• Bármikor A*^[24] vagy bármikor javítható A* (ARA*)^[25]
• Bármikor Dynamic A*
• A* blokk
• D*
• D mező*
• Peremkeresés
• Peremmegtakarítás* (FSA*)
• Általános adaptív A* (GAA*)
• Növekményes heurisztikus keresés
• Információs keresés^[22]
• Iteratív elmélyítés A* (IDA*)
• Ugrópontkeresés
• Egész életen át tartó tervezés A* (LPA*)
• Szorzóval gyorsított A* (MAA*)^[26]
• Új kétirányú A* (NBA*)^[27]
• Egyszerűsített memória, határolt A* (SMA*)
• Valós idejű A*^[28]
• Theta*
• Időkorlátozott A* (TBA*)^[29]

Az A* egy kétirányú keresési algoritmushoz is adaptálható. Különös figyelmet kell fordítani a megállási kritériumra.^[30]

Ez a szócikk részben vagy egészben az A* search algorithm című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

• Nilsson, N. J.. Principles of Artificial Intelligence. Palo Alto, California: Tioga Publishing Company (1980). ISBN 978-0-935382-01-3 
• Tiszta vizuális A* magyarázat, tanácsokkal és gondolatokkal az ösvény-felfedezésről
• Változat az A*-on, úgynevezett hierarchikus útmeghatározó A*-on
• (HPA*)

• B* algoritmus
• Szélességi keresés
• Mélységi keresés