A*

Keresés A * (ejtsd: "A star" vagy "A star", angolul  A star ) - a számítástechnikában és a matematikában egy olyan keresési algoritmus , amely az első legjobb egyezést keresi egy grafikonon , amely megtalálja az útvonalat a legalacsonyabb költséggel egy csúcsból ( kezdő) másikra (cél, végleges).

A csúcsok bejárásának sorrendjét a távolság + költség heurisztikus függvény határozza meg (általában f(x) jelöléssel ). Ez a függvény két másik összege: a figyelembe vett csúcs ( x ) kezdeti csúcsból való elérésének költségfüggvénye (ezt általában g(x) -ként jelölik, és lehet heurisztikus vagy nem), és a távolság heurisztikus becslésének függvénye. a figyelembe vett csúcstól a végső csúcsig ( h (x) jelöléssel ).

A h(x) függvénynek érvényes heurisztikus becslésnek kell lennie , azaz nem szabad túlbecsülnie a célcsúcs távolságait. Például egy útválasztási probléma esetén h(x) lehet a cél távolsága egy egyenes vonalban, mivel ez a fizikailag lehetséges legkisebb távolság két pont között.

Ezt az algoritmust először 1968 -ban írta le Peter Hart , Nils Nilsson és Bertram Raphael . Ez lényegében Dijkstra 1959-ben létrehozott algoritmusának kiterjesztése volt. Az új algoritmus nagyobb teljesítményt ért el (időben) heurisztikák segítségével. Munkájukban "A" algoritmusként hivatkoznak rá. De mivel a legjobb útvonalat számítja ki egy adott heurisztikához, ezért az A* nevet kapta.

Ennek általánosítása a kétirányú heurisztikus keresési algoritmus .

Történelem

1964-ben Nils Nilsson feltalált egy heurisztikus megközelítést Dijkstra algoritmusának felgyorsítására . Ezt az algoritmust A1 -nek hívták . 1967-ben Bertram Raphael jelentős fejlesztéseket hajtott végre ezen az algoritmuson, de nem sikerült elérnie az optimálisat. Ezt az algoritmust A2 -nek nevezte el . Aztán 1968 -ban Peter E. Hart olyan érveket terjesztett elő, amelyek szerint az A2 optimális a szekvenciális heurisztika használatakor, csak kisebb módosításokkal. Az algoritmus bizonyítása egy szakaszt is tartalmazott, amely megmutatta, hogy az új A2 algoritmus a feltételek mellett valószínűleg a legjobb algoritmus. Így az új algoritmust a szintaxisban csillaggal jelölte, A -val kezdődik és minden lehetséges verziószámot tartalmazott.

Az algoritmus leírása

Az A* végighalad az összes útvonalon, amely a kezdőcsúcstól a végcsúcsig vezet, amíg meg nem találja a legkisebbet. Mint minden tájékozott keresési algoritmus , ez is először azokat az útvonalakat vizsgálja, amelyek „úgy tűnik”, hogy a célhoz vezetnek. A mohó algoritmustól , amely egyben az első legjobb egyezés keresési algoritmusa is, abban különbözik , hogy a csúcs kiválasztásakor figyelembe veszi többek között a hozzá megtett teljes utat. A g(x) komponens  az útvonal költsége a kezdeti csúcsból, és nem az előzőből, mint a mohó algoritmusban.

A munka elején átnézik a kiindulóponttal szomszédos csomópontokat; azt választjuk ki, amelyiknek minimális az f(x) értéke , majd ez a csomópont kibővül. Az algoritmus minden szakaszban a kiindulási ponttól a gráf összes, még feltáratlan (levél) csúcsáig tartó utak halmazán működik - adott megoldások halmaza -, amely prioritási sorba kerül . Az útvonal prioritást az f(x) = g(x) + h(x) érték határozza meg . Az algoritmus mindaddig folytatja munkáját, amíg a célcsúcs f(x) értéke kisebb lesz, mint bármely érték a sorban, vagy amíg a teljes fa vizsgálatra nem kerül. A megoldások halmazából a legalacsonyabb költségű megoldás kerül kiválasztásra.

Minél kisebb a h(x) heurisztikus érték, annál nagyobb a prioritás, így a fák rendezése használható a sor megvalósításához .

A megtekintett csúcsok halmazát a rendszer tárolja closed, és a figyelembe veendő útvonalak a prioritási sorban vannak open. Az elérési út prioritása az f(x) függvény segítségével kerül kiszámításra a prioritási sor megvalósításán belül.

Pszeudokód:

A* függvény ( kezdet, cél, f ) A csúcsok % halmaza már áthaladt var zárva := az üres halmaz adott megoldások % halmaza var open := make_queue ( f ) enqueue ( nyitott , elérési út ( start )) míg nyitva nem üres _ var p := remove_first ( megnyitás ) var x : = p utolsó csomópontja _ ha x zárva _ folytatni ha x = cél visszatérés p hozzáadás ( zárt , x ) % hozzáadja a szomszédos csúcsokat foreach y az utódokban ( x ) enqueue ( open , add_to_path ( p , y )) visszaküldési hiba

A már átadott csúcsok halmaza elhagyható (ebben az esetben az algoritmus döntési fa kereséssé válik), ha ismert, hogy a megoldás létezik, vagy ha ciklusokatsuccessors tud levágni .

Példa

Példa az A* algoritmusra működés közben, ahol a csomópontok olyan városok, amelyeket utak kötnek össze, és H(x) a legrövidebb távolság a célponttól:

Kulcs: zöld - start, kék - cél, narancs - meglátogatott csomópontok.

Tulajdonságok

A Breadth First Searchhez hasonlóan az A* is teljes abban az értelemben, hogy mindig talál megoldást, ha létezik.

Ha a h heurisztikus függvény megengedhető, azaz soha nem becsüli túl a cél elérésének tényleges minimális költségét, akkor maga az A* is elfogadható (vagy optimális ), feltéve, hogy nem vágjuk le a bejárt csúcsokat. Ha ezt tesszük, akkor az algoritmus optimálisságához szükséges, hogy h(x) is monoton vagy szukcessziós heurisztika. A monotonitási tulajdonság azt jelenti, hogy ha vannak A-B-C és A-C utak (nem feltétlenül B -n keresztül), akkor az A - tól C -ig tartó út költségbecslésének kisebbnek vagy egyenlőnek kell lennie, mint az A-B és B-C utak becsléseinek összege . (A monotonitást háromszög- egyenlőtlenségnek is nevezik: a háromszög egyik oldala nem lehet hosszabb, mint a másik két oldal összege.) Matematikailag minden x út esetén y (ahol y az x  gyermeke ) a következő:

Az A* adott h heurisztikusan is optimálisan hatékony . Ez azt jelenti, hogy bármely más algoritmus legalább annyi csomópontot kutat fel, mint A* (kivéve, ha van több konkrét megoldás, amelyek ugyanazzal a heurisztikával pontosan megfelelnek az optimális útvonal költségének).

Míg az A* optimális a "véletlenszerűen" megadott gráfokhoz, nincs garancia arra, hogy jobb munkát végez, mint az egyszerűbb, de jobban tartomány -tudatos algoritmusok. Előfordulhat például, hogy egy bizonyos labirintusban először a kijárattól a megfelelő irányba kell mennie , és csak azután kell visszafordulnia. Ebben az esetben a kijárathoz közelebb eső (egyenes vonalú) csúcsok elején végzett felmérés időpocsékolás lesz.

Különleges alkalmak

Általánosságban elmondható, hogy a mélység – első keresés és a szélesség – az első keresés az A* algoritmus két speciális esete. A mélységi kereséshez vegyünk egy globális változó - számlálót C , inicializálva azt valamilyen nagy értékkel. Minden alkalommal, amikor kiterjesztünk egy csúcsot, a számláló értékét hozzárendeljük a szomszédos csúcsokhoz, és minden hozzárendelés után eggyel csökkentjük. Így minél korábban nyitunk meg egy csúcsot, annál nagyobb h(x) értéket kap, ami azt jelenti, hogy utoljára lesz megtekintve. Ha minden csúcsra h(x) = 0 -t teszünk, akkor egy másik speciális esetet kapunk - Dijkstra algoritmusát .

A megvalósítás részletei

Számos megvalósítási jellemző és technika van, amelyek jelentősen befolyásolhatják az algoritmus hatékonyságát. Az első dolog, amire nem árt odafigyelni, az az, hogy a prioritási sor hogyan kezeli a csúcsok közötti kapcsolatokat. Ha olyan csúcsokat adunk hozzá, hogy a sor LIFO elv szerint működjön , akkor az azonos minősítésű csúcsok esetén A* "megy" a mélységbe. Ha azonban a csúcsok összeadásakor a FIFO elvet alkalmazzuk , akkor az azonos becslésű csúcsok esetében az algoritmus éppen ellenkezőleg, szélességi keresést hajt végre. Egyes esetekben ez a körülmény jelentős hatással lehet a teljesítményre .

Ha a munka végén egy útvonalra van szükség az algoritmusból, akkor általában minden csúcshoz eltárolnak egy hivatkozást a szülőcsomóponthoz. Ezek a linkek lehetővé teszik az optimális útvonal rekonstrukcióját. Ha igen, akkor fontos, hogy ugyanaz a csúcs ne jelenjen meg kétszer a sorban (miközben saját útvonala és költségbecslése van). Általában ennek a problémának a megoldására egy csúcs hozzáadásakor ellenőrzik, hogy van-e róla bejegyzés a sorban. Ha igen, akkor a rekord frissül, hogy megfeleljen a kettő minimális költségének. A rendezési fában lévő csúcs megtalálásához sok szabványos algoritmusnak O(n) időre van szüksége. Ha javítja a fát egy hash táblázattal , akkor csökkentheti ezt az időt.

Miért érvényes és optimális az A*

Az A* algoritmus megengedett és a minimális számú csúcsot bejárja, mivel a csúcson áthaladó útvonal "optimista" becslésével működik. Optimista abban az értelemben, hogy ha átmegy ezen a csúcson, az algoritmusnak "van esélye", hogy az eredmény valós költsége egyenlő lesz ezzel a becsléssel, de nem kevesebb. De mivel A* egy informált algoritmus, egy ilyen egyenlőség lehetséges.

Amikor A* befejezi a keresést, definíció szerint talált egy utat, amelynek valós költsége kisebb, mint bármely nyitott csomóponton áthaladó útvonal becsült költsége. De mivel ezek a becslések optimisták, a megfelelő csomópontokat minden kétséget kizáróan el lehet vetni. Más szavakkal, az A* soha nem hagy ki egy lehetőséget az útvonal hosszának minimalizálására, ezért törvényes.

Tegyük fel most, hogy valamelyik B algoritmus eredményeként olyan utat adott vissza, amelynek hossza nagyobb, mint a valamely csúcson áthaladó útvonal becsült költsége. Heurisztikus információk alapján a B algoritmus esetében nem zárható ki, hogy ennek az útnak a valós hossza rövidebb volt, mint az eredmény. Ennek megfelelően, míg a B algoritmus kevesebb csúcsot vett figyelembe, mint A*, ez nem lesz érvényes. Tehát az A* a legkevesebb gráfcsúcsot járja be az érvényes algoritmusok közül, ugyanazt a pontos (vagy kevésbé pontos) heurisztikát használva.

Nehézségi fok

Az A* algoritmus időbeli összetettsége a heurisztikától függ. A legrosszabb esetben az algoritmus által feltárt csúcsok száma exponenciálisan növekszik az optimális út hosszához képest, de a komplexitás polinomiálissá válik, ha a heurisztika teljesíti a következő feltételt:

;

ahol h* az optimális heurisztika, azaz az x és a cél közötti távolság pontos becslése. Más szóval, a h(x) hiba nem nőhet gyorsabban, mint az optimális heurisztika logaritmusa .

De az időbonyolultságnál is nagyobb probléma az algoritmus által felhasznált memória erőforrások mennyisége . A legrosszabb esetben exponenciális számú csomópontot kell megjegyeznie. Ennek leküzdésére az algoritmus számos változatát javasolták, mint például az A* algoritmus iteratív elmélyítéssel (iteratív mélyítés A*, IDA*), A* memóriakorlátos A*, MA*, egyszerűsített MA* (egyszerűsített MA) *, SMA*) és a rekurzív legjobb első keresés (RBFS).

Irodalom

  • Laurier J.-L. Mesterséges intelligencia rendszerek / Per. fr. és szerk. V. L. Stefanyuk. - M .: Mir, 1991. - S. 238-244. — 20.000 példány. másolat.  — ISBN 5-03-001408-X .
  • Russell S.J., Norvig, P. Artificial Intelligence: A Modern Approach = Artificial Intelligence: A Modern Approach / Per. angolról. és szerk. K. A. Ptitsina. - 2. kiadás - M . : Williams, 2006. - S. 157-162. - 3000 példányban. másolat.  — ISBN 5-8459-0887-6 .
  • Nilson N. Artificial Intelligence: Methods for Finding Solutions = Problémamegoldó módszerek a mesterséges intelligenciában / Per. angolról. V. L. Stefanyuk; szerk. S. V. Fomina. - M . : Mir, 1973. - S. 70-80.
  • Dechter, R., Pearl, J. Generalized best-first search strategies and the Optimity of A*  // Journal of the ACM. - 1985. - T. 32 , 3. sz . - S. 505 - 536 .
  • Hart PE, Nilsson, NJ, Raphael, B. Formális alap a minimális költségutak heurisztikus meghatározásához // IEEE Transactions on Systems Science and Cybernetics SSC4. - 1968. - 2. sz . - S. 100 - 107 .
  • Hart PE, Nilsson, NJ, Raphael, B. „A minimális költségutak heurisztikus meghatározásának formális alapja” helyesbítése // SIGART hírlevél. - 1972. - T. 37 . - S. 28 - 29 .
  • Pearl J. Heuristics: Intelligens keresési stratégiák számítógépes problémamegoldáshoz. - Addison-Wesley, 1984. - ISBN 0-201-05594-5 .

Linkek

 Grafikon keresési algoritmusok
Tájékozatlan módszerek
Tájékozott módszerek
Parancsikonok
Minimálisan átívelő fa
Egyéb