A* algoritmus forrásának megtekintése

Az '''A*''' (''A csillag''nak ejtve) egy [[Gráfbejárás|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.<ref name="ReferenceA">{{Hivatkozás/Könyv |last=Russell, Stuart J. |others=Norvig, Peter |title=Artificial intelligence a modern approach |edition=4th |date=2018 |publisher=Pearson |location=Boston |isbn=978-0134610993 |oclc=1021874142}}</ref> Az egyik fő gyakorlati hátránya az <math>O(b^d)</math> 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,<ref>{{Hivatkozás/Könyv |last=Delling |first=D. |title=Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation |series=Lecture Notes in Computer Science |year=2009 |publisher=Springer |isbn=978-3-642-02093-3 |doi=10.1007/978-3-642-02094-0_7 |page=11个$7–139 |chapter=Engineering Route Planning Algorithms}}</ref> ahogy a memóriakorlátos megközelítések is. Sok esetben azonban az A* továbbra is a legjobb megoldás.<ref name="Zeng">{{Cite journal|first=W.|author=Zeng|title=Finding shortest paths on real road networks: the case for A*|journal=International Journal of Geographical Information Science|issue=4|pages=531–543|year=2009|doi=10.1080/13658810801949850|volume=23|url=https://zenodo.org/record/979689}}</ref>

Peter Hart, Nils Nilsson és Bertram Raphael a Stanford Kutatóintézetben (ma SRI International) 1968-ban publikálta először az algoritmust.<ref name="nilsson">{{Cite journal|first=P. E.|author=Hart|title=A Formal Basis for the Heuristic Determination of Minimum Cost Paths|journal=IEEE Transactions on Systems Science and Cybernetics|issue=2|pages=100–107|year=1968|doi=10.1109/TSSC.1968.300136|volume=4}}</ref> Ez [[Edsger Wybe Dijkstra|Edsger Dijkstra]] 1959-es [[Dijkstra-algoritmus|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 ==
[[Fájl:SRI_Shakey_with_callouts.jpg|jobbra|bélyegkép| Az A*-ot a Shakey the Robot útjának tervezésén dolgozó kutatók találták ki]]
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<ref>{{Cite journal|author=Doran|first=J. E.|date=1966-09-20|title=Experiments with the Graph Traverser program|journal=Proc. R. Soc. Lond. A|language=en|volume=294|issue=1437|pages=235–259|doi=10.1098/rspa.1966.0205|issn=0080-4630}}</ref> használatát javasolta Shakey útjának tervezéséhez.<ref name=":0">{{Hivatkozás/Könyv |last=Nilsson |first=Nils J. |title=The Quest for Artificial Intelligence |url=https://ai.stanford.edu/~nilsson/QAI/qai.pdf |date=2009-10-30 |publisher=Cambridge University Press |location=Cambridge |language=English |isbn=9780521122931 |page=}}</ref> A Graph Traverser algoritmust egy <math>h(n)</math> heurisztikus függvény, az <math>n</math> csúcstól a célcsúcsig becsült távolság vezérli: teljesen figyelmen kívül hagyja <math>g(n)</math>-t, a kezdőcsúcstól <math>n</math>-ig való távolságot. Bertram Raphael a <math>g(n) + h(n)</math> ö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.<ref>{{Cite web |url=https://people.inf.elte.hu/gt/mi/05-06.grafker.pdf#page=15 |title=Gráfkeresések (előadásjegyzet) |accessdate=2020-07-03 |author=Gregorics Tibor |format=PDF |pages=15}}</ref> 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.<ref>{{Cite journal|author=Edelkamp|first=Stefan|date=2005|title=Cost-Algebraic Heuristic Search|url=http://www.aaai.org/Papers/AAAI/2005/AAAI05-216.pdf|journal=Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI)|volume=|pages=1362–1367}}</ref>

Az eredeti 1968-as A*-cikkben<ref name="nilsson" /> szerepel egy tétel, miszerint egyetlen A*-hoz hasonló algoritmus<ref>“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*.</ref> 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é,<ref>{{Cite journal|author=Hart|first=Peter E.|date=1972-12-01|title=Correction to 'A Formal Basis for the Heuristic Determination of Minimum Cost Paths'|url=https://www.ics.uci.edu/~dechter/publications/r0.pdf|journal=ACM SIGART Bulletin|volume=|issue=37|pages=28–29|doi=10.1145/1056777.1056779|issn=0163-5719}}</ref> 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.<ref name=":1">{{Cite journal|first=Rina|author=Dechter|title=Generalized best-first search strategies and the optimality of A*|journal=[[Journal of the ACM]]|volume=32|issue=3|pages=505–536|year=1985|doi=10.1145/3828.3830}}
</ref>

== Leírás ==
Az A* egy informált [[keresőalgoritmus]], avagy [[legjobbat először keresés]], vagyis [[súlyozott gráf]]okkal van megfogalmazva: a [[gráf]] egy adott kezdő[[Csúcs (gráfelmélet)|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 [[Fa (adatszerkezet)|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

: <math>f(n) = g(n) + h(n)</math>

függvényt minimalizáló utat, ahol {{Mvar|n}} az úton található következő csúcs, {{Math|''g''(''n'')}} a kezdőcsúcstól {{Mvar|n}}-ig tartó út költsége, és {{Math|''h''(''n'')}} egy [[Heurisztika|heurisztikus]] függvény, amely az {{Mvar|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 {{Math|''f''(''x'')}} értékű csomópontot eltávolítja a sorból, a szomszédainak {{Mvar|f}} és {{Mvar|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 {{Mvar|f}} értékkel nem rendelkezik, mint a sorban lévő bármelyik csomópont (vagy amíg a sor ki nem ürül).<ref group="*">A célcsúcsokon többször is áthaladhat az algoritmus, amíg van kisebb <math>f</math> értékű másik csúcs, mivel ezek a csúcsok adhatnak olcsóbb utat a célcsúcshoz.</ref> A cél {{Mvar|f}} értéke ekkor a legrövidebb út költsége, mivel {{Mvar|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 {{Math|''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 {{Mvar|h}} [[heurisztika]] kielégíti a {{Math|''h''(''x'') ≤ ''d''(''x'', ''y'') + ''h''(''y'')}} kiegészítő feltételt a gráf minden {{Math|(''x'', ''y'')}} élére (ahol {{Mvar|d}} az adott él hosszát jelöli), akkor {{Mvar|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|Dijkstra algoritmusának]] futtatásával a <math>d'(x, y) = d(x, y) + h(y) - h(x)</math> csökkentett költséggel.

=== Pszeudokód ===
A következő [[pszeudokód]] leírja az algoritmust: <syntaxhighlight lang="pascal" start="1">
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
</syntaxhighlight>
'''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 <code>tentative_gScore < gScore [neighbor]</code> feltétel mindig hamis. 
[[Fájl:Astar_progress_animation.gif|bélyegkép|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:

[[File:AstarExampleEn.gif|link=https://en.wikipedia.org/wiki/File:AstarExampleEn.gif|An example of A* algorithm in action (nodes are cities connected with roads, h(x) is the straight-line distance to target point) Green: Start, Blue: Target, Orange: Visited]]

'''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 [[Ortodroma|főköri távolság]] (a lehető legrövidebb gömbfelületi távolság) a célig. Az algoritmus utat keres [[Washington (főváros)|Washington]] és [[Los Angeles]] között.

[[File:A*_Search_Example_on_North_American_Freight_Train_Network.gif| Az A* algoritmus, amely vasúti utat talál Washington, DC é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 [[Verem (adatszerkezet)|LIFO]] módon viselkedik, akkor A* [[mélységi keresés]]ké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 kupac|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ábla|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-algoritmus|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''.<ref name="geospatial">{{Citation|title=Geospatial Analysis: A Comprehensive Guide to Principles, Techniques and Software Tools|first1=Michael John|last1=De Smith|first2=Michael F.|last2=Goodchild|first3=Paul|last3=Longley|publisher=Troubadour Publishing Ltd|year=2007|isbn=9781905886609|page=344|url=https://books.google.com/books?id=SULMdT8qPwEC&pg=PA344}}.</ref><ref name="pythalgs">{{Citation|title=Python Algorithms: Mastering Basic Algorithms in the Python Language|first1=Magnus Lie|last1=Hetland|publisher=Apress|year=2010|isbn=9781430232377|page=214|url=https://books.google.com/books?id=9_AXCmGDiz8C&pg=PA214}}.</ref> Az általános [[Mélységben először keresés|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 (<math display="inline">d(x,y)>\varepsilon>0</math> valamely rögzített <math>\varepsilon</math>-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észhalmaz]]a 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.<ref name=":1">{{Cite journal|first=Rina|author=Dechter|title=Generalized best-first search strategies and the optimality of A*|journal=[[Journal of the ACM]]|volume=32|issue=3|pages=505–536|year=1985|doi=10.1145/3828.3830}}
</ref> 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. <!-- A nem patologikus probléma fogalmán az értették, amit most „up to tie-breaking” megszorításon értünk. –  mi az az „up to tie-breaking”? --> 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.<ref name="Martelli">{{Cite journal|first=Alberto|author=Martelli|title=On the Complexity of Admissible Search Algorithms|journal=[[Artificial Intelligence]]|volume=8|issue=1|pages=1–13|year=1977|doi=10.1016/0004-3702(77)90002-9}}
</ref> Ilyen körülmények között Dijkstra algoritmusa jelentősen felülmúlhatja az A*-ot.

== Korlátozott enyhítés ==
[[Fájl:Weighted_A_star_with_eps_5.gif|bélyegkép|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 <math>(1 + \varepsilon)</math>-szorosa. Ezt az új garanciát ''ε''-megengedhetőnek nevezzük.

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

* Súlyozott A* / statikus súlyozás.<ref>{{Cite journal|first=Ira|author=Pohl|title=First results on the effect of error in heuristic search|journal=Machine Intelligence|volume=5|pages=219–236|year=1970}}</ref> Ha <math>h_a(n)</math> egy megengedhető heurisztikus függvény, az A* súlyozott változata a <math>h_w(n) = \varepsilon h_a(n)</math> (<math>\varepsilon > 1</math>) 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 <math>h_a</math> 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.<ref name="pearl84">{{Hivatkozás/Könyv |last=Pearl |first=Judea |title=Heuristics: Intelligent Search Strategies for Computer Problem Solving |url=https://archive.org/details/heuristicsintell00pear |year=1984 |publisher=Addison-Wesley |isbn=978-0-201-05594-8}}</ref>
* A dinamikus súlyozás<ref>{{Cite conference|first=Ira|last=Pohl|title=The avoidance of (relative) catastrophe, heuristic competence, genuine dynamic weighting and computational issues in heuristic problem solving|volume=3|pages=11–17|url=https://www.cs.auckland.ac.nz/courses/compsci709s2c/resources/Mike.d/Pohl1973WeightedAStar.pdf}}</ref> az <math>f(n) = g(n) + (1\!+\!w(n))h(n)</math> költségfüggvényt használja, ahol <math>w(n) = \begin{cases} 1 - \frac{d(n)}{N}, & d(n) \le N \\ 0, & d(n) > N \end{cases}</math>, 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<ref>{{Cite conference|first=Andreas|last=Köll|title=A new approach to dynamic weighting|pages=16–17}}</ref> a csomópontok mintavételével a heurisztikus hibát jobban becsüli meg és távolítja el.
* <math>A^*_\varepsilon</math>.<ref>{{Cite journal|first=Judea|author=Pearl|title=Studies in semi-admissible heuristics|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=4|issue=4|pages=392–399|year=1982|doi=10.1109/TPAMI.1982.4767270}}</ref> 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<sub>F</sub>'' pedig a legígéretesebb csomópont kiválasztására szolgál a FOCAL listából.
* ''A<sub>ε</sub>'' a <math>A f(n) + B h_F(n)</math> 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 <math>C f(n) + D h_F(n)</math> függvényhez, ahol ''C'' és ''D'' konstans.
* Az AlphA*<ref>{{Cite journal|first=Bjørn|author=Reese|title=AlphA*: An ''ε''-admissible heuristic search algorithm|year=1999|url=http://home1.stofanet.dk/breese/astaralpha-submitted.pdf.gz|accessdate=2014-11-05|archiveurl=https://web.archive.org/web/20160131214618/http://home1.stofanet.dk/breese/astaralpha-submitted.pdf.gz|archivedate=2016-01-31}}</ref> 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 <math>f_\alpha(n) = (1 + w_\alpha(n)) f(n)</math> költségfüggvényt használja, ahol <math>w_\alpha(n) = \begin{cases} \lambda, & g(\pi(n)) \le g(\tilde{n}) \\ \Lambda, & g(\pi(n)) > g(\tilde{n}) \end{cases}</math>, ahol ''λ'' és ''Λ'' konstans, <math>\lambda \le \Lambda</math>, <math>\pi(n)</math> az <math>n</math> szülője, és <math>\tilde{n}</math> 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) {{Mvar|d}} mélységében: {{Math|''O''(''b<sup>d</sup>'')}}, ahol {{Mvar|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őségi reláció|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 <math>b^d</math> csúcsból sok olyat lemetsszen, amit egy nem informált keresés kiterjesztene. Minőségét kifejezhetjük {{Math|''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, {{Mvar|N}}-nek és a megoldás mélységének megmérésével, majd az

:<math>N + 1 = 1 + b^* + (b^*)^2 + \dots + (b^*)^d</math>
egyenlet megoldásával.

A jó heurisztika alacsony effektív elágazási tényezővel rendelkezik (az optimális {{Math|''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

: <math>|h(x) - h^*(x)| = O(\log h^*(x))</math>

feltételnek, ahol {{Math|''h''<sup>*</sup>}} az optimális heurisztika, az {{Mvar|x}}-től a célig való eljutás pontos költsége. Más szóval, a {{Mvar|h}} hibája nem fog gyorsabban növekedni, mint a {{Math|''h''<sup>*</sup>}} „tökéletes heurisztika” [[logaritmus]]a, amely az {{Mvar|x}}-től a célig tartó valódi távolságot adja vissza.<ref name="pearl84">{{Hivatkozás/Könyv |last=Pearl |first=Judea |title=Heuristics: Intelligent Search Strategies for Computer Problem Solving |url=https://archive.org/details/heuristicsintell00pear |year=1984 |publisher=Addison-Wesley |isbn=978-0-201-05594-8}}</ref>

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.<ref name="ReferenceA"/> 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 [[Iteratív mélyítés A* algoritmus|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.<ref name="nilsson" /> Számos különféle problémában alkalmazzák, beleértve a sztochasztikus nyelvtanok [[Elemző (informatika)|elemzésével]] kapcsolatos problémát az a természetes nyelvek feldolgozásakor.<ref>{{Cite conference|title=A* parsing: fast exact Viterbi parse selection|year=2003}}</ref> Használják ezen kívül például online tanulásos információs keresésben is.<ref name="WPCleanerAuto1">{{Cite journal|url=http://www.eng.tau.ac.il/~bengal/GTA.pdf|title=A Group-Testing Algorithm with Online Informational Learning|author=Kagan E. and Ben-Gal I.|publisher=IIE Transactions, 46:2, 164-184|year=2014|accessdate=2020-05-18|archiveurl=https://web.archive.org/web/20161105103321/http://www.eng.tau.ac.il/~bengal/GTA.pdf|archivedate=2016-11-05}}</ref>

== Kapcsolatok más algoritmusokkal ==
Az A*-ot az különbözteti meg egy [[mohó algoritmus|mohó]] best-first algoritmustól, hogy figyelembe veszi a már megtett költségeket/távolságot, {{Math|''g''(''n'')}}-t.

[[Dijkstra-algoritmus|Dijkstra algoritmusának]] néhány általános változatát az A* speciális esetének tekinthetjük, ahol heurisztika <math>h(n) = 0</math> 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.<ref>{{Cite journal|author=Nau|first=Dana S.|title=General branch and bound, and its relation to A∗ and AO∗|journal=Artificial Intelligence|volume=23|issue=1|year=1984|pages=29–58|url=https://www.cs.umd.edu/~nau/papers/nau1984general.pdf|doi=10.1016/0004-3702(84)90004-3}}</ref>

== Változatok ==
* Bármikor A*<ref>Hansen, Eric A., and Rong Zhou. "[http://www.jair.org/media/2096/live-2096-3136-jair.pdf?q=anytime: Anytime Heuristic Search.] {{Wayback|url=http://www.jair.org/media/2096/live-2096-3136-jair.pdf?q=anytime: |date=20161105102805 }}" J. Artif. Intell. Res.(JAIR) 28 (2007): 267-297.</ref> vagy bármikor javítható A* (ARA*)<ref>Likhachev, Maxim; Gordon, Geoff; Thrun, Sebastian. "[http://robots.stanford.edu/papers/Likhachev03b.pdf 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.</ref> 
* 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<ref name="WPCleanerAuto1">{{Cite journal|url=http://www.eng.tau.ac.il/~bengal/GTA.pdf|title=A Group-Testing Algorithm with Online Informational Learning|author=Kagan E. and Ben-Gal I.|publisher=IIE Transactions, 46:2, 164-184|year=2014|accessdate=2020-05-18|archiveurl=https://web.archive.org/web/20161105103321/http://www.eng.tau.ac.il/~bengal/GTA.pdf|archivedate=2016-11-05}}</ref> 
* [[Iteratív mélyítés A* algoritmus|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*)<ref>Li, Jerry and Zimmerle, Daniel (2019), [https://ieeexplore.ieee.org/document/8994527 "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 [https://www.researchgate.net/publication/339266504_Designing_Optimal_Network_for_Rural_Electrification_using_Multiplier-accelerated_A_Algorithm Researchgate] or [http://www.drjerryli.com/articles/APPEEC19_accepted.pdf the author's personal page]</ref> 
* Új kétirányú A* (NBA*)<ref>Pijls, Wim; Post, Henk "[https://repub.eur.nl/pub/16100/ei2009-10.pdf Yet another bidirectional algorithm for shortest paths]" In ''Econometric Institute Report EI 2009-10/Econometric Institute, Erasmus University Rotterdam. Erasmus School of Economics.''</ref> 
* Egyszerűsített memória, határolt A* (SMA*) 
* Valós idejű A*<ref>Korf, Richard E. "[https://pdfs.semanticscholar.org/2fda/10f6079156c4621fefc8b7cad72c1829ee94.pdf Real-time heuristic search.] {{Wayback|url=https://pdfs.semanticscholar.org/2fda/10f6079156c4621fefc8b7cad72c1829ee94.pdf |date=20171007115930 }}" Artificial intelligence 42.2-3 (1990): 189-211.</ref> 
* Theta* 
* Időkorlátozott A* (TBA*)<ref>{{Cite conference|url=http://web.cs.du.edu/~sturtevant/papers/TBA.pdf|title=TBA*: time-bounded A*|first=Yngvi|last=Björnsson|accessdate=2020-05-18|archiveurl=https://web.archive.org/web/20200924081447/https://web.cs.du.edu/~sturtevant/papers/TBA.pdf|archivedate=2020-09-24}}</ref>

Az A* egy [[kétirányú keresés]]i algoritmushoz is adaptálható. Különös figyelmet kell fordítani a megállási kritériumra.<ref>{{Cite journal|title=Efficient Point-to-Point Shortest Path Algorithms|url=http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf}} from [[Princetoni Egyetem|Princeton University]]</ref>

== Megjegyzések ==
{{Megjegyzések}}

== Hivatkozások ==
{{Hivatkozások}}

== Fordítás ==
{{fordítás|en|A* search algorithm|oldid=953687217}}

== További információk ==
* {{cite book |last=Nilsson |first=N. J. |title=Principles of Artificial Intelligence |url=https://archive.org/details/principlesofarti00nils |year=1980 |publisher=Tioga Publishing Company |location=Palo Alto, California |isbn=978-0-935382-01-3}}
* [http://theory.stanford.edu/~amitp/GameProgramming/ Tiszta vizuális A* magyarázat, tanácsokkal és gondolatokkal az ösvény-felfedezésről]
* Változat az A*-on, úgynevezett [https://web.archive.org/web/20090917155722/http://www.cs.ualberta.ca/~mmueller/ps/hpastar.pdf hierarchikus útmeghatározó] A*-on
* [https://web.archive.org/web/20090917155722/http://www.cs.ualberta.ca/~mmueller/ps/hpastar.pdf (HPA*)]

== Kapcsolódó szócikkek ==
* [[B* algoritmus]] 
* [[Szélességi keresés]] 
* [[Mélységi keresés]]

[[Kategória:Gráfalgoritmusok]]
[[Kategória:Keresőalgoritmusok]]