Egy iránytű a kereséshez
Az előző leckében a gép vakon keresett, nem tudta, merre van a cél. A gyakorlatban azonban gyakran van legalább egy sejtésünk arról, melyik irány visz közelebb. Ha egy térképen A pontból B pontba akarunk eljutni, akkor a légvonalban mért távolság már önmagában jó tippet ad arról, melyik szomszédos város felé érdemes indulni. Ez a sejtés a heurisztika, egy becslés arról, hogy egy adott állapotból mennyire van még hátra a célig.
A heurisztika nem pontos érték. Nem tudja, mekkora lesz a valódi út, csak megbecsüli. Mégis hatalmas segítség, mert a keresést a célhoz közelebb vivő irányba tereli. Az ilyen, becslést használó keresést hívjuk informált keresésnek, szemben az előző leckében látott informálatlan, tájékozódás nélküli kereséssel.
A mohó keresés és a csapdája
A legegyszerűbb ötlet az, hogy mindig arrafelé lépjünk, amerre a heurisztika szerint legközelebb van a cél. Ezt hívjuk mohó keresésnek. Sokszor gyorsan is célba ér, mert egyenesen a cél felé tart. Van azonban egy komoly gyengéje. Csak arra figyel, mennyi van még hátra, arra viszont nem, mennyit tettünk már meg. Ezért könnyen becsapja egy irány, amely elsőre a cél felé mutat, de valójában egy hosszú kerülőbe vagy zsákutcába visz.
Olyan ez, mint egy túrázó, aki mindig egyenesen a hegycsúcs felé indul, és nem veszi észre, hogy közben egy szakadékhoz ér. A mohó keresés a pillanatnyi közelséget nézi, de nem méri fel az út egészét. Ahhoz, hogy megbízhatóan a legjobb utat találjuk meg, két dolgot kell egyszerre mérlegelni.
Az A* algoritmus
Az A* algoritmus a mohó keresés hibáját javítja ki egy egyszerű, de nagyszerű ötlettel. Nem csak azt nézi, mennyi van még hátra, hanem azt is, mennyit tettünk már meg. Minden állapothoz két számot rendel. Az egyik a már megtett út valódi költsége, a másik a célig hátralévő út becslése. A kettő összege adja meg, hogy összességében mennyire ígéretes ez az állapot. Az A* mindig azt az állapotot bontja ki legközelebb, amelynél ez az összeg a legkisebb.
Így az A* nem hagyja magát becsapni egy csábító, de hosszú iránytól, mert az addig felhalmozott költséget is beszámítja. Emiatt egyszerre marad célirányos és óvatos. Ez a kettősség teszi olyan erőssé. A navigációs alkalmazások, a játékbeli útkeresés és sok más gyakorlati rendszer szíve pontosan ez az algoritmus, vagy annak egy változata.
Mitől lesz jó egy heurisztika
Az A* csak annyira jó, amennyire a becslés, amit használ. Egy heurisztikáról akkor mondjuk, hogy megbízható, ha soha nem becsüli túl a hátralévő utat. Vagyis a becslése lehet pontos vagy óvatosan alacsony, de sosem mondhatja, hogy messzebb van a cél, mint amennyire valójában. Ha ez teljesül, az A* garantáltan a legjobb, legkisebb költségű megoldást találja meg. Ha viszont a becslés túllő, előfordulhat, hogy a gép egy jó utat idő előtt elvet, és rosszabb megoldással éri be.
A jó heurisztika megtalálása gyakran a legkreatívabb rész. A légvonalbeli távolság a térképen ilyen, hiszen a valódi út a kanyarok miatt sosem lehet rövidebb nála. A művészet abban áll, hogy a becslés minél közelebb kerüljön a valósághoz anélkül, hogy valaha is túllőne rajta. Minél pontosabb, annál kevesebb felesleges állapotot kell a gépnek megvizsgálnia.
Az A* két számot mérlegel. A már megtett út valódi költségét és a hátralévő út becslését. Ez a párosítás óvja meg a mohó keresés csapdájától, és teszi a klasszikus MI egyik legfontosabb, ma is használt keresőjévé.
Workshop
AI Transformation Day
Egésznapos, vezetőknek szóló program. Feltérképezzük, hol tart a szervezet, mi az első reális lépés, és milyen belső feltételek szükségesek a sikerhez. A nap végén konkrét, prioritizált cselekvési lista.
Érdekel a program →