Keresés tájékozódás nélkül
Informálatlan keresésnek azt hívjuk, amikor a gépnek nincs semmilyen becslése arról, melyik állapot van közelebb a célhoz. Csak annyit tud, hol járt már, és milyen lépések állnak előtte. Olyan, mint egy sötét labirintusban tapogatózni, ahol nem látszik a kijárat iránya, csak a következő elágazás. Ez elsőre gyengének tűnhet, mégis fontos alapeset, mert világosan megmutatja, mit jelent egyáltalán módszeresen bejárni egy állapotteret.
A kérdés csupán annyi, milyen sorrendben nézzük meg a még ki nem bontott állapotokat. Erre a látszólag apró döntésre két klasszikus válasz van, és a kettő egészen máshogy viselkedik. Az egyik a keresési fát szintenként járja be, a másik egy ágon halad mélyre, amíg csak tud.
Szélességi keresés, szintenként
A szélességi keresés türelmes. Előbb a kiindulás összes közvetlen szomszédját nézi meg, aztán azoknak az összes szomszédját, és csak ezután megy egy szinttel mélyebbre. Úgy terjed, mint a vízbe dobott kavics körül a hullámok, egyenletesen minden irányba. Ennek van egy nagyon értékes tulajdonsága. Ha van megoldás, biztosan megtalálja, méghozzá a legkevesebb lépést igénylőt találja meg elsőként. Ha minden lépés ugyanannyiba kerül, akkor ez egyben a legrövidebb út is.
Ennek azonban ára van. Ahhoz, hogy szintenként haladjon, a gépnek nyilván kell tartania egy egész szint állapotait egyszerre. Ahogy a szintek egyre szélesebbek lesznek, ez a nyilvántartás gyorsan nagyra nő. A szélességi keresés tehát biztos és jó utat ad, de sok memóriát ehet.
Mélységi keresés, egy ágon mélyre
A mélységi keresés türelmetlen. Fog egy ágat, és megy rajta lefelé, amíg csak tud, egészen az ág aljáig. Csak ha ott zsákutcába jut, akkor lép vissza egy elágazással, és próbálja a következő irányt. Olyan, mint a labirintusban mindig a jobb kéz felőli falat követni. A nagy előnye, hogy nagyon takarékos a memóriával. Egyszerre csak egyetlen aktuális utat kell nyilvántartania a gyökértől a jelenlegi állapotig, nem egész szinteket.
A hátulütő az, hogy a mélységi keresés nem garantálja a legrövidebb utat. Könnyen lehet, hogy talál egy hosszú, kacskaringós megoldást, miközben egy sokkal rövidebb ott lett volna egy szomszédos ágon. Ráadásul ha egy ág nagyon mélyre, akár végtelenbe fut, a mélységi keresés beleragadhat, és sosem tér vissza megnézni a többi lehetőséget. A rövid úthoz és a biztonsághoz ezért gyakran egy korlátot is beépítenek, ameddig legfeljebb elmegy egy ágon.
Szélességi keresés
- Szintenként, egyenletesen terjed
- A legkevesebb lépésű megoldást találja meg
- Biztosan megtalálja a megoldást, ha van
- Sok memóriát igényel, egész szinteket tárol
Mélységi keresés
- Egy ágon halad mélyre, aztán visszalép
- Nem garantálja a legrövidebb utat
- Mély vagy végtelen ágba beleragadhat
- Nagyon takarékos a memóriával
Melyiket mikor érdemes
A választás mindig a probléma természetén múlik. Ha fontos, hogy a lehető legrövidebb megoldást találjuk meg, és van elég memória, a szélességi keresés a biztos választás. Ha a megoldások jellemzően mélyen vannak, és a memória szűk, a mélységi keresés hatékonyabb lehet. Sok gyakorlati rendszer a kettő erényeit próbálja ötvözni, például úgy, hogy mélységi módon keres, de fokozatosan növeli, meddig mehet el egy ágon.
A közös bennük, hogy egyik sem tudja, merre van a cél. Vakon, tájékozódás nélkül tapogatóznak. A következő leckében pontosan ezen változtatunk. Adunk a gépnek egy becslést arról, melyik irány visz közelebb a célhoz, és ezzel a keresés sokkal okosabbá válik.
Két stratégia, egy kompromisszum. A szélességi keresés a legrövidebb utat adja, de sok memóriát kér. A mélységi takarékos a memóriával, de hosszabb utat is elfogadhat. A klasszikus MI-ben szinte mindig ez a fajta kompromisszum dönt.
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 →