A* keresési algoritmus
Az A* egy lépéssorozat (algoritmus), amelyet a számítógépek arra használhatnak, hogy kitalálják, hogyan juthatnak el gyorsan két hely között. Ha van egy lista a helyszínekről, és arról, hogy milyen nehéz eljutni az egyikből egyenesen a másikba, az A* segítségével gyorsan meg lehet mondani a leggyorsabb utat. Ez a módszer a Dijkstra algoritmusával rokon, de okos találgatásokat tesz, így nem kell olyan sokáig próbálkoznia a lassú utakkal. Ez egy jó lépéssorozat, ha csak két hely közötti útra van szükséged. Ha sok utat akarsz kérdezni ugyanabból a térképből, akkor vannak gyorsabb módszerek, amelyek egyszerre találják meg az összes választ, mint például a Floyd-Warshall algoritmus. Az A* nem fog működni, ha egy út során több helyet akarsz meglátogatni (az utazó ügynök problémája).
A lépések
Az A*-nak először is szüksége van egy listára az összes helyről, ahová el lehet menni, majd egy listára arról, hogy milyen messze van az út az egyes helyek között. Ezután megmondja, hogy melyik a leggyorsabb út A helyről Z helyre.
Egy példa kedvéért mondjuk, hogy A kapcsolódik B és C helyekkel, és B és C mindkettő kapcsolódik D és E helyekkel. D és E mindkettő kapcsolódik Z-vel. 4 lehetséges módja van, hogy A-tól Z-ig menjünk. Mehetünk A-B-D-Z, A-C-D-Z, A-B-E-Z, vagy A-C-E-Z. Az A*-t használó számítógép először megnézi, hogy milyen nehéz eljutni A-tól B-be, illetve A-tól C-be. Ez a "költsége" ezeknek a helyeknek. Egy hely költsége azt jelenti, hogy mennyire nehéz eljutni A-ból az adott helyre. Miután felírta mindkét költséget, a számítógép megnézi, hogy milyen nehéz eljutni B-ből D-be, és ezt hozzáadja B költségéhez. Ezt írja le D költségeként. Ezután a számítógép megnézi, hogy milyen nehéz eljutni C-ből D-be, és ezt hozzáadja C költségéhez. Ez egy másik költség D számára, és ha ez kisebb, mint a már meglévő, akkor lecseréli a régit. A számítógép csak a legjobb útvonalra kíváncsi, ezért figyelmen kívül hagyja a magasabb költségű utat. Az A-B-D és az A-C-D közül csak az egyiket fogja megjegyezni, amelyik gyorsabb.
A számítógép továbbmegy, és megtalálja a leggyorsabb utat E-be. Végül D-ből Z-be megy, és talál egy költséget, majd E-ből Z-be, és talál egy költséget. Z-re kap egy végső költséget, és ez a legkisebb költség, amit kaphat. Most már a számítógép tudja, hogy melyik a leggyorsabb út, és megvan a válasz. A számítógép hasonló lépéssorozatot tud elvégezni, de sokkal, de sokkal több helyen. Minden egyes alkalommal megnézi az A-hoz legközelebb eső helyet, és összeadja az adott hely szomszédos helyeinek költségeit.
A fenti lépéssorozatot Dijkstra algoritmusának nevezik. Dijkstra algoritmusa lassú lehet, mert sok olyan helyet fog megnézni, amely esetleg rossz irányba megy Z-ből. Ha megkérdeznéd a számítógépet, hogyan juthatsz el egy városból egy közeli városba, Dijkstra algoritmusa végül egy másik államban kereshet.
Az A* megoldja ezt a problémát. Az A* lehetővé teszi, hogy megmondja a számítógépnek, hogy milyen messze lesz az egyes helyektől a végállomásig. A számítógép a becslést arra tudja használni, hogy megmondja, nagyjából mennyi idő alatt lehet eljutni egy adott helyről Z-be. Ahelyett, hogy csak az A-hoz legközelebbi helyet választaná ki, azt fogja megnézni, amelyik valószínűleg a legalacsonyabb összeggel fog rendelkezni. Ezt a végösszeget úgy találja meg, hogy a költséget hozzáadja a hátralévő várható távolsághoz. Így csak abba az irányba tud nézni, ahol a dolgok valószínűleg jobbak lesznek. Nem baj, ha a tipp nem tökéletes, de már egy egyszerű rossz tipp is sokkal gyorsabbá teheti a programot. Ha a való világban két hely között próbálsz utat találni, akkor a jó tipp csak a köztük lévő távolságot jelenti egyenes vonalban. A valódi út az utakon keresztül hosszabb lesz, de így a program kitalálhatja, és nem fog rossz irányba menni.
A matematikai vagy informatikai szakirodalomban ez a találgatás gyakran a hely függvénye, és heurisztikának nevezik. Minden hely egy csúcs, és minden két hely közötti út egy él. Ezek a szavak a gráfelméletből származnak.
