A tájékozatlan keresés (a vakkeresés is , brute force method , eng. informed search, blind search, brute-force search ) az állapottérben történő megoldáskeresési stratégia , amely nem használ további információkat az állapotokról, kivéve azokat, amelyeket a feladat meghatározása. A tájékozatlan keresés módszere csak arra képes, hogy utódokat fejlesszen ki, és megkülönböztesse a célállapotot a nem célállapottól [1] [2] [3] .
A Breadth-first keresés ( BFS ) egy állapottér-megoldás-keresési stratégia, amely először a gyökércsomópontot bontja ki, majd a gyökércsomópont összes utódját, majd az utódokat, és így tovább. Mielőtt bármelyik csomópontot kiterjesztené a következő szintre, a keresési fa adott mélységében lévő összes csomópont kibővül.
Az algoritmus kész. Ha minden műveletnek azonos a költsége, a szélesség-első keresés az optimális.
A generált csomópontok teljes száma (időbonyolultsága) O( b d +1 ), ahol b az elágazási tényező, d a keresési mélység. A térkomplexitás is O( b d +1 ) [1] .
A szélességi első keresés megvalósítása használhat FIFO - sort . Kezdetben a sor csak a gyökércsomópontot tartalmazza. A fő hurok minden iterációja során a curr csomópont lekérésre kerül a sor fejéből . Ha a curr csomópont a célcsomópont, akkor a keresés leáll, ellenkező esetben a curr csomópont le lesz tekerve , és az összes utódja a sor végére kerül [4] [5] .
függvény BFS ( v : Csomópont ) : Logikai ; start enqueue ( v ) ; míg a sor nem üres , kezdje el curr : = dequeue () ; if is_goal ( curr ) , akkor kezdődik BFS := true ; kilépés ; vége ; mark ( curr ) ; a következőhöz az utódokban ( curr ) tegye, ha nincs megjelölve ( következő ) , akkor kezdje el a sorbanállást ( következő ) ; vége ; vége ; BFS := false ; vége ;
A költségkeresés (uniform-cost search, UCS ) a szélesség-első keresési algoritmus általánosítása, amely figyelembe veszi a műveletek költségét (az állapotgráf élei). A költségalapú keresés a csomópontokat a gyökércsomóponttól induló legrövidebb út költségének növekvő sorrendjében bővíti ki. Az algoritmus minden lépésében a legalacsonyabb g ( n ) költségű csomópont kerül telepítésre. A csomópontok egy prioritási sorban [6] vannak tárolva .
Ez az algoritmus akkor teljes és optimális, ha a szakaszok költsége szigorúan pozitív. Ha az összes szakasz költsége egyenlő, akkor a költségkeresés megegyezik a szélességi kereséssel.
A költségkeresési eljárás egy végtelen hurokba léphet, ha történetesen olyan csomópont van telepítve, amely nulla költségű művelettel ismét ugyanabba az állapotba mutat. A keresés teljessége és optimálissága garantálható, feltéve, hogy minden akció költsége szigorúan pozitív [1] .
A költségalapú keresés logikailag egyenértékű a Dijkstra egyforrású legrövidebb útvonalú algoritmusával . Konkrétan mindkét algoritmus ugyanazokat a csomópontokat telepíti ugyanabban a sorrendben. A fő különbség a csomópontok jelenléte a prioritási sorban: a Dijkstra algoritmusában az összes csomópont hozzáadódik a sorhoz az inicializálás során, míg a költségalapú keresési algoritmusban a csomópontok „on-the-fly” ( engl . . menet közben, lustán ) keresés közben. Ebből következik, hogy Dijkstra algoritmusa explicit gráfokra, míg az UCS algoritmus explicit és implicit gráfokra egyaránt alkalmazható [7] .
A mélység - első keresés ( DFS ) egy állapottér-döntési keresési stratégia, amely mindig kiterjeszti a keresési fa aktuális perifériájának legmélyebb csomópontját. A mélyreható keresés elemzi a lista aktuális csomópontjának első utódját, majd az első utódját, stb. A kibővített csomópontok eltávolításra kerülnek a perifériáról, így a további keresés a következő legsekélyebb csomóponttól folytatódik, amely még mindig feltáratlan. utódai [1] .
A mélységi keresési stratégia megvalósítható LIFO veremmel vagy rekurzív függvénnyel [8] .
függvény DFS ( v : csomópont ; mélység : egész ) : Logikai ; begin if is_goal ( v ) then begin DFS := true ; kilépés ; vége ; for next in utódokban ( v ) do if DFS ( következő , mélység + 1 ) , akkor kezdődik a DFS := igaz ; kilépés ; vége ; DFS := false ; vége ;
A mélységkorlátozott keresés ( DLS ) a mélység -első keresés egy olyan változata, amely előre meghatározott l mélységhatárt alkalmaz a végtelen út probléma megoldására.
A mélységben korlátozott keresés nem teljes, mert l < d esetén a cél nem található, és l > d esetén nem optimális . Időbonyolultsága O( b l ), térbeli összetettsége O( b · l ) [1] [9] .
Az iteratív mélyítő keresési algoritmusban a mélységben korlátozott keresést használják.
függvény DLS ( v : csomópont ; mélység , határ : egész ) : Logikai ; begin if ( mélység < limit ) then begin if is_goal ( v ) then begin DLS := true ; kilépés ; vége ; for next in utódokban ( v ) kezdődjön if DLS ( következő , mélység + 1 , határ ) , majd kezdődik DLS := igaz ; kilépés ; vége ; vége ; vége ; DLS := false ; vége ;
A mélység-első keresés iteratív elmélyítéssel (iteratív-mélyítő mélység-első keresés, IDDFS , DFID ) egy olyan stratégia, amely lehetővé teszi a legjobb mélységhatár megtalálását a DLS-kereséshez. Ezt úgy érjük el, hogy az l határértéket fokozatosan növeljük, amíg meg nem találjuk a célt.
Az iteratív mélyítő keresés egyesíti a mélység-első keresés (térbonyolultság O( b · l )) és a szélesség-első keresés (teljesség és optimalitás véges b és nem negatív élsúlyok esetén) előnyeit.
Bár az iteratív mélykeresés többször generálja ugyanazokat az állapotokat, a legtöbb csomópont a keresési fa alján található, így a csomópontok újrabővítésére fordított idő általában figyelmen kívül hagyható. Az algoritmus időbonyolultsága O( b l ) [1] [9] [10] .
függvény IDDFS ( v : csomópont ) : egész szám ; var lim : Integer ; kezdés lim := 0 ; míg nem DLS ( v , 0 , lim ) do lim := lim + 1 ; IDDFS := lim ; vége ;
A szélességi (vagy mélységi) kétirányú keresés egy kifinomult szélességi (vagy mélységi) keresési algoritmus, amelynek az az ötlete, hogy egyszerre két keresés hajtható végre (előre, a kezdeti állapotból, és ellenkező irányban, cél), megállva, miután a két keresési folyamat középen találkozik.
A kétirányú keresés egy iteratív elmélyítési stratégián alapulhat. Egy iteráció tartalmaz egy keresést a k mélységig előrefelé, és két keresést a k mélységig és a k + 1-et hátrafelé. Mivel csak a k mélységben közvetlen kereséssel talált állapotok tárolódnak a memóriában , a keresés térbonyolultságát O ( b d /2 )-ként definiáljuk. Annak ellenőrzése, hogy egy visszafelé irányuló kereséssel talált csomópont egy előrefelé irányuló keresési fa perifériájához tartozik-e, konstans időben elvégezhető, így a kétirányú keresés időbonyolultsága O ( b d /2 ) [1] [9] [ 11] .
| Grafikon keresési algoritmusok | ||
|---|---|---|
| Tájékozatlan módszerek | ||
| Tájékozott módszerek | ||
| Parancsikonok | ||
| Minimálisan átívelő fa | ||
| Egyéb | ||