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 $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.

Történet

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 $h(n)$ heurisztikus függvény, az $n$ csúcstól a célcsúcsig becsült távolság vezérli: teljesen figyelmen kívül hagyja $g(n)$ -t, a kezdőcsúcstól $n$ -ig való távolságot. Bertram Raphael a $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]

Leírás

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

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) \leq 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 $d'(x,y)=d(x,y)+h(y)-h(x)$ csökkentett költséggel.

Pszeudokód

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.

A robot mozgástervezési problémájának kezdőcsomóponttól egy célcsomópontig történő elérési út keresésének A* ábrája. Az üres körök a *nyitott halmaz* csomópontjait képviselik, azaz azokat, amelyeket még ki kell vizsgálni, és a kitöltött zárt halmazban vannak. Az egyes zárt csomópontok színe jelzi a távolságot a kezdetektől: minél zöldebb, annál távolabb van. Először láthatjuk, hogy az A* egyenes vonalban halad a cél felé, majd amikor akadályba ütközik, alternatív útvonalakat fedez fel a csomópontokon keresztül a nyitott készletből.

Példa

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.

A végrehajtás részletei

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.

Különleges esetek

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.

Tulajdonságok

Végesség és teljesség

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 $\varepsilon$ -ra) az A* csak akkor terminál garantáltan, ha van megoldás.

Megengedhetőség

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.

Optimális hatékonyság

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.

Korlátozott enyhítés

Egy A* keresés, amely egy heurisztikát használ, amely 5,0 (= ε) szorzata egy konzisztens heurisztikának, és szuboptimális útvonalat kap.

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 $(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 $h_{a}(n)$ egy megengedhető heurisztikus függvény, az A* súlyozott változata a $h_{w}(n)=\varepsilon h_{a}(n)$ ( $\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 $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 $f(n)=g(n)+(1\!+\!w(n))h(n)$ költségfüggvényt használja, ahol $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.
$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 $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 $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 $f_{\alpha }(n)=(1+w_{\alpha }(n))f(n)$ költségfüggvényt használja, ahol $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, $\lambda \leq \Lambda$ , $\pi (n)$ az $n$ szülője, és ${\tilde {n}}$ a legutóbb kiterjesztett csúcs.

Bonyolultság

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 $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

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

|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*.

Alkalmazások

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]

Kapcsolatok más algoritmusokkal

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 $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]

Változatok

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]

Megjegyzések

↑ A célcsúcsokon többször is áthaladhat az algoritmus, amíg van kisebb $f$ értékű másik csúcs, mivel ezek a csúcsok adhatnak olcsóbb utat a célcsúcshoz.

Hivatkozások

↑ ^a ^b Russell, Stuart J.. Artificial intelligence a modern approach, Norvig, Peter, 4th, Boston: Pearson (2018. december 8.). ISBN 978-0134610993. OCLC 1021874142
↑ Delling, D.. Engineering Route Planning Algorithms, Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation, Lecture Notes in Computer Science. Springer, 11个$7–139. o.. DOI: 10.1007/978-3-642-02094-0_7 (2009). ISBN 978-3-642-02093-3
↑ Zeng (2009). „Finding shortest paths on real road networks: the case for A*”. International Journal of Geographical Information Science 23 (4), 531–543. o. DOI:10.1080/13658810801949850.
↑ ^a ^b ^c Hart (1968). „A Formal Basis for the Heuristic Determination of Minimum Cost Paths”. IEEE Transactions on Systems Science and Cybernetics 4 (2), 100–107. o. DOI:10.1109/TSSC.1968.300136.
↑ Doran (1966. szeptember 20.). „Experiments with the Graph Traverser program” (angol nyelven). Proc. R. Soc. Lond. A 294 (1437), 235–259. o. DOI:10.1098/rspa.1966.0205. ISSN 0080-4630.
↑ Nilsson, Nils J.. The Quest for Artificial Intelligence (english nyelven). Cambridge: Cambridge University Press (2009. október 30.). ISBN 9780521122931
↑ Gregorics Tibor: Gráfkeresések (előadásjegyzet) (PDF) pp. 15. (Hozzáférés: 2020. július 3.)
↑ Edelkamp (2005. december 8.). „Cost-Algebraic Heuristic Search”. Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI), 1362–1367. o.
↑ “A*-like” means the algorithm searches by extending paths originating at the start node one edge at a time, just as A* does. This excludes, for example, algorithms that search backward from the goal or in both directions simultaneously. In addition, the algorithms covered by this theorem must be admissible and “not more informed” than A*.
↑ Hart (1972. december 1.). „Correction to 'A Formal Basis for the Heuristic Determination of Minimum Cost Paths'”. ACM SIGART Bulletin (37), 28–29. o. DOI:10.1145/1056777.1056779. ISSN 0163-5719.
↑ ^a ^b Dechter (1985). „Generalized best-first search strategies and the optimality of A*”. Journal of the ACM 32 (3), 505–536. o. DOI:10.1145/3828.3830.
↑ De Smith, Michael John; Goodchild, Michael F. & Longley, Paul (2007), Geospatial Analysis: A Comprehensive Guide to Principles, Techniques and Software Tools, Troubadour Publishing Ltd, p. 344, ISBN 9781905886609, <https://books.google.com/books?id=SULMdT8qPwEC&pg=PA344>.
↑ Hetland, Magnus Lie (2010), Python Algorithms: Mastering Basic Algorithms in the Python Language, Apress, p. 214, ISBN 9781430232377, <https://books.google.com/books?id=9_AXCmGDiz8C&pg=PA214>.
↑ Martelli (1977). „On the Complexity of Admissible Search Algorithms”. Artificial Intelligence 8 (1), 1–13. o. DOI:10.1016/0004-3702(77)90002-9.
↑ Pohl (1970). „First results on the effect of error in heuristic search”. Machine Intelligence 5, 219–236. o.
↑ ^a ^b Pearl, Judea. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley (1984). ISBN 978-0-201-05594-8
↑ Pohl, Ira. „The avoidance of (relative) catastrophe, heuristic competence, genuine dynamic weighting and computational issues in heuristic problem solving”. 3: 11–17.
↑ Köll, Andreas. „A new approach to dynamic weighting”.: 16–17.
↑ Pearl (1982). „Studies in semi-admissible heuristics”. IEEE Transactions on Pattern Analysis and Machine Intelligence 4 (4), 392–399. o. DOI:10.1109/TPAMI.1982.4767270.
↑ Reese (1999). „AlphA*: An ε-admissible heuristic search algorithm”. [2016. január 31-i dátummal az eredetiből archiválva]. (Hozzáférés: 2014. november 5.)
↑ (2003) „A* parsing: fast exact Viterbi parse selection”..
↑ ^a ^b Kagan E. and Ben-Gal I. (2014). „A Group-Testing Algorithm with Online Informational Learning”, Kiadó: IIE Transactions, 46:2, 164-184. [2016. november 5-i dátummal az eredetiből archiválva]. (Hozzáférés: 2020. május 18.)
↑ Nau (1984). „General branch and bound, and its relation to A∗ and AO∗”. Artificial Intelligence 23 (1), 29–58. o. DOI:10.1016/0004-3702(84)90004-3.
↑ Hansen, Eric A., and Rong Zhou. "Anytime Heuristic Search. Archiválva 2016. november 5-i dátummal a Wayback Machine-ben" J. Artif. Intell. Res.(JAIR) 28 (2007): 267-297.
↑ Likhachev, Maxim; Gordon, Geoff; Thrun, Sebastian. "ARA*: Anytime A* search with provable bounds on sub-optimality". In S. Thrun, L. Saul, and B. Schölkopf, editors, Proceedings of Conference on Neural Information Processing Systems (NIPS), Cambridge, MA, 2003. MIT Press.
↑ Li, Jerry and Zimmerle, Daniel (2019), "Designing Optimal Network for Rural Electrification using Multiplier-accelerated A* Algorithm", 2019 IEEE PES Asia-Pacific Power and Energy Engineering Conference (APPEEC), Macao, Macao, 2019, pp. 1-5. Accepted version of this paper is available at Researchgate or the author's personal page
↑ Pijls, Wim; Post, Henk "Yet another bidirectional algorithm for shortest paths" In Econometric Institute Report EI 2009-10/Econometric Institute, Erasmus University Rotterdam. Erasmus School of Economics.
↑ Korf, Richard E. "Real-time heuristic search. Archiválva 2017. október 7-i dátummal a Wayback Machine-ben" Artificial intelligence 42.2-3 (1990): 189-211.
↑ Björnsson, Yngvi. „TBA*: time-bounded A*”.. [2020. szeptember 24-i dátummal az eredetiből archiválva]. Hozzáférés: 2020. május 18.
↑ „Efficient Point-to-Point Shortest Path Algorithms”. from Princeton University

Fordítás

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.

További információk

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*)

Kapcsolódó szócikkek

[12] A célcsúcsokon többször is áthaladhat az algoritmus, amíg van kisebb $f$ értékű másik csúcs, mivel ezek a csúcsok adhatnak olcsóbb utat a célcsúcshoz.

[ReferenceA-1] Russell, Stuart J.. Artificial intelligence a modern approach, Norvig, Peter, 4th, Boston: Pearson (2018. december 8.). ISBN 978-0134610993. OCLC 1021874142

[2] Delling, D.. Engineering Route Planning Algorithms, Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation, Lecture Notes in Computer Science. Springer, 11个$7–139. o.. DOI: 10.1007/978-3-642-02094-0_7 (2009). ISBN 978-3-642-02093-3

[Zeng-3] Zeng (2009). „Finding shortest paths on real road networks: the case for A*”. International Journal of Geographical Information Science 23 (4), 531–543. o. DOI:10.1080/13658810801949850.

[nilsson-4] Hart (1968). „A Formal Basis for the Heuristic Determination of Minimum Cost Paths”. IEEE Transactions on Systems Science and Cybernetics 4 (2), 100–107. o. DOI:10.1109/TSSC.1968.300136.

[5] Doran (1966. szeptember 20.). „Experiments with the Graph Traverser program” (angol nyelven). Proc. R. Soc. Lond. A 294 (1437), 235–259. o. DOI:10.1098/rspa.1966.0205. ISSN 0080-4630.

[:0-6] Nilsson, Nils J.. The Quest for Artificial Intelligence (english nyelven). Cambridge: Cambridge University Press (2009. október 30.). ISBN 9780521122931

[7] Gregorics Tibor: Gráfkeresések (előadásjegyzet) (PDF) pp. 15. (Hozzáférés: 2020. július 3.)

[8] Edelkamp (2005. december 8.). „Cost-Algebraic Heuristic Search”. Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI), 1362–1367. o.

[9] “A*-like” means the algorithm searches by extending paths originating at the start node one edge at a time, just as A* does. This excludes, for example, algorithms that search backward from the goal or in both directions simultaneously. In addition, the algorithms covered by this theorem must be admissible and “not more informed” than A*.

[10] Hart (1972. december 1.). „Correction to 'A Formal Basis for the Heuristic Determination of Minimum Cost Paths'”. ACM SIGART Bulletin (37), 28–29. o. DOI:10.1145/1056777.1056779. ISSN 0163-5719.

[:1-11] Dechter (1985). „Generalized best-first search strategies and the optimality of A*”. Journal of the ACM 32 (3), 505–536. o. DOI:10.1145/3828.3830.

[geospatial-13] De Smith, Michael John; Goodchild, Michael F. & Longley, Paul (2007), Geospatial Analysis: A Comprehensive Guide to Principles, Techniques and Software Tools, Troubadour Publishing Ltd, p. 344, ISBN 9781905886609, <https://books.google.com/books?id=SULMdT8qPwEC&pg=PA344>.

[pythalgs-14] Hetland, Magnus Lie (2010), Python Algorithms: Mastering Basic Algorithms in the Python Language, Apress, p. 214, ISBN 9781430232377, <https://books.google.com/books?id=9_AXCmGDiz8C&pg=PA214>.

[Martelli-15] Martelli (1977). „On the Complexity of Admissible Search Algorithms”. Artificial Intelligence 8 (1), 1–13. o. DOI:10.1016/0004-3702(77)90002-9.

[16] Pohl (1970). „First results on the effect of error in heuristic search”. Machine Intelligence 5, 219–236. o.

[pearl84-17] Pearl, Judea. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley (1984). ISBN 978-0-201-05594-8

[18] Pohl, Ira. „The avoidance of (relative) catastrophe, heuristic competence, genuine dynamic weighting and computational issues in heuristic problem solving”. 3: 11–17.

[19] Köll, Andreas. „A new approach to dynamic weighting”.: 16–17.

[20] Pearl (1982). „Studies in semi-admissible heuristics”. IEEE Transactions on Pattern Analysis and Machine Intelligence 4 (4), 392–399. o. DOI:10.1109/TPAMI.1982.4767270.

[21] Reese (1999). „AlphA*: An ε-admissible heuristic search algorithm”. [2016. január 31-i dátummal az eredetiből archiválva]. (Hozzáférés: 2014. november 5.)

[22] (2003) „A* parsing: fast exact Viterbi parse selection”..

[WPCleanerAuto1-23] Kagan E. and Ben-Gal I. (2014). „A Group-Testing Algorithm with Online Informational Learning”, Kiadó: IIE Transactions, 46:2, 164-184. [2016. november 5-i dátummal az eredetiből archiválva]. (Hozzáférés: 2020. május 18.)

[24] Nau (1984). „General branch and bound, and its relation to A∗ and AO∗”. Artificial Intelligence 23 (1), 29–58. o. DOI:10.1016/0004-3702(84)90004-3.

[25] Hansen, Eric A., and Rong Zhou. "Anytime Heuristic Search. Archiválva 2016. november 5-i dátummal a Wayback Machine-ben" J. Artif. Intell. Res.(JAIR) 28 (2007): 267-297.

[26] Likhachev, Maxim; Gordon, Geoff; Thrun, Sebastian. "ARA*: Anytime A* search with provable bounds on sub-optimality". In S. Thrun, L. Saul, and B. Schölkopf, editors, Proceedings of Conference on Neural Information Processing Systems (NIPS), Cambridge, MA, 2003. MIT Press.

[27] Li, Jerry and Zimmerle, Daniel (2019), "Designing Optimal Network for Rural Electrification using Multiplier-accelerated A* Algorithm", 2019 IEEE PES Asia-Pacific Power and Energy Engineering Conference (APPEEC), Macao, Macao, 2019, pp. 1-5. Accepted version of this paper is available at Researchgate or the author's personal page

[28] Pijls, Wim; Post, Henk "Yet another bidirectional algorithm for shortest paths" In Econometric Institute Report EI 2009-10/Econometric Institute, Erasmus University Rotterdam. Erasmus School of Economics.

[29] Korf, Richard E. "Real-time heuristic search. Archiválva 2017. október 7-i dátummal a Wayback Machine-ben" Artificial intelligence 42.2-3 (1990): 189-211.

[30] Björnsson, Yngvi. „TBA*: time-bounded A*”.. [2020. szeptember 24-i dátummal az eredetiből archiválva]. Hozzáférés: 2020. május 18.

[31] „Efficient Point-to-Point Shortest Path Algorithms”. from Princeton University

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[* 1]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]