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. Az egyik fő gyakorlati hátránya az 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, ahogy a memóriakorlátos megközelítések is. Sok esetben azonban az A* továbbra is a legjobb megoldás.
Peter Hart, Nils Nilsson és Bertram Raphael a Stanford Kutatóintézetben (ma SRI International) 1968-ban publikálta először az algoritmust. 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 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 használatát javasolta Shakey útjának tervezéséhez. A Graph Traverser algoritmust egy heurisztikus függvény, az csúcstól a célcsúcsig becsült távolság vezérli: teljesen figyelmen kívül hagyja -t, a kezdőcsúcstól -ig való távolságot. Bertram Raphael a ö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. 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.
Az eredeti 1968-as A*-cikkben szerepel egy tétel, miszerint egyetlen A*-hoz hasonló algoritmus“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*. 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é, 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.
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üggvényt minimalizáló utat, ahol az úton található következő csúcs, a kezdőcsúcstól -ig tartó út költsége, és egy heurisztikus függvény, amely az -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 értékű csomópontot eltávolítja a sorból, a szomszédainak és é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 értékkel nem rendelkezik, mint a sorban lévő bármelyik csomópont (vagy amíg a sor ki nem ürül).A célcsúcsokon többször is áthaladhat az algoritmus, amíg van kisebb értékű másik csúcs, mivel ezek a csúcsok adhatnak olcsóbb utat a célcsúcshoz. A cél értéke ekkor a legrövidebb út költsége, mivel é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 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 heurisztika kielégíti a kiegészítő feltételt a gráf minden élére (ahol az adott él hosszát jelöli), akkor 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 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. 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:
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... 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édjá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