Neinformované vyhledávání (též slepé vyhledávání , metoda brute force , angl. uninformed search, blind search, brute-force search ) je strategie pro hledání řešení ve stavovém prostoru , která nepoužívá dodatečné informace o stavech, kromě těch uvedených v definice úkolu. Jediné, čeho je metoda neinformovaného vyhledávání schopna, je vyvinout nástupce a odlišit cílový stav od necílového [1] [2] [3] .
Prohledávání do šířky ( BFS ) je strategie prohledávání stavového prostoru, která nejprve rozšiřuje kořenový uzel, poté všechny následníky kořenového uzlu, poté rozšiřuje následníky těchto následníků a tak dále. Před rozbalením uzlů na další úrovni se rozbalí všechny uzly v dané hloubce ve vyhledávacím stromě.
Algoritmus je dokončen. Pokud mají všechny akce stejnou cenu, je optimální vyhledávání na šířku.
Celkový počet vygenerovaných uzlů (časová složitost) je O( b d +1 ), kde b je faktor větvení, d je hloubka vyhledávání. Prostorová složitost je také O( b d +1 ) [1] .
Implementace prohledávání do šířky může používat frontu FIFO . Na začátku fronta obsahuje pouze kořenový uzel. Při každé iteraci hlavní smyčky je uzel curr načten z hlavy fronty . Pokud je uzel curr cílovým uzlem, vyhledávání se zastaví, jinak se uzel curr rozvine a všichni jeho následníci se přidají na konec fronty [4] [5] .
funkce BFS ( v : Node ) : Boolean ; begin enqueue ( v ) ; zatímco fronta není prázdná do begin curr : = dequeue () ; if is_goal ( curr ) then begin BFS := true ; výstup ; konec ; značka ( curr ) ; for next in následníky ( curr ) do if not označené ( next ) then begin enqueue ( next ) ; konec ; konec ; BFS := false ; konec ;
Hledání nákladů (uniform-cost search, UCS ) je zobecněním algoritmu prohledávání do šířky, který bere v úvahu náklady na akce (okraje grafu stavu). Hledání založené na nákladech rozšiřuje uzly ve vzestupném pořadí podle ceny nejkratší cesty z kořenového uzlu. V každém kroku algoritmu je nasazen uzel s nejnižší cenou g ( n ). Uzly jsou uloženy v prioritní frontě [6] .
Tento algoritmus je úplný a optimální, pokud jsou náklady na etapy striktně kladné. Pokud jsou náklady ve všech fázích stejné, je hledání nákladů identické s hledáním do šířky.
Procedura vyhledávání nákladů může vstoupit do nekonečné smyčky, pokud je náhodou nasazen uzel, který má akci s nulovými náklady, která opět ukazuje na stejný stav. Úplnost a optimálnost vyhledávání je možné zaručit za předpokladu, že náklady na všechny úkony jsou striktně kladné [1] .
Hledání založené na nákladech je logicky ekvivalentní algoritmu Dijkstra s jediným zdrojem nejkratší cesty . Konkrétně oba algoritmy nasazují stejné uzly ve stejném pořadí. Hlavní rozdíl souvisí s přítomností uzlů v prioritní frontě: v Dijkstrově algoritmu jsou všechny uzly přidány do fronty během inicializace, zatímco v nákladovém vyhledávacím algoritmu jsou uzly přidávány „za běhu“ ( eng , on-the-fly, líně ) během vyhledávání. Z toho vyplývá, že Dijkstrův algoritmus je aplikovatelný na explicitní grafy, zatímco UCS algoritmus lze aplikovat na explicitní i implicitní grafy [7] .
Depth -first search ( DFS ) je rozhodovací strategie prohledávání stavového prostoru, která vždy rozšiřuje nejhlubší uzel na aktuální periferii vyhledávacího stromu. Hloubkové vyhledávání analyzuje prvního následníka aktuálního uzlu v seznamu, poté jeho prvního následníka atd. Rozšířené uzly jsou odstraněny z periferie, takže další hledání „obnovuje“ od dalšího nejmělčejšího uzlu, který ještě nebyl prozkoumán. nástupci [1] .
Strategie hledání do hloubky může být implementována pomocí zásobníku LIFO nebo pomocí rekurzivní funkce [8] .
funkce DFS ( v : Uzel ; hloubka : Celé číslo ) : Boolean ; begin if is_goal ( v ) then begin DFS := true ; výstup ; konec ; pro další v následcích ( v ) proveďte if DFS ( další , hloubka + 1 ) then begin DFS := true ; výstup ; konec ; DFS := false ; konec ;
Hloubkově omezené vyhledávání ( DLS ) je varianta hloubkového prohledávání, která používá předdefinovaný hloubkový limit l k vyřešení problému nekonečné cesty.
Hloubkově omezené hledání není kompletní, protože pro l < d nebude cíl nalezen a není optimální pro l > d . Jeho časová složitost je O( b l ) a jeho prostorová složitost je O( b · l ) [1] [9] .
Hloubkově omezené vyhledávání se používá v algoritmu iterativního prohlubování.
funkce DLS ( v : Uzel ; hloubka , limit : Celé číslo ) : Boolean ; begin if ( hloubka < limit ) then begin if is_goal ( v ) then begin DLS := true ; výstup ; konec ; for next in následníky ( v ) do begin if DLS ( další , hloubka + 1 , limit ) then begin DLS := true ; výstup ; konec ; konec ; konec ; DLS := false ; konec ;
Prohledávání do hloubky s iterativním prohlubováním (iterativní prohlubování prohledávání do hloubky, IDDFS , DFID ) je strategie, která vám umožňuje najít nejlepší hloubkový limit pro vyhledávání DLS. Toho je dosaženo postupným zvyšováním limitu l , dokud není nalezen cíl.
Iterativní prohlubování prohledávání kombinuje výhody prohledávání do hloubky (prostorová složitost O( b · l )) a prohledávání do šířky (úplnost a optimalita pro konečné b a nezáporné váhy hran).
I když iterativní hloubkové vyhledávání generuje stejné stavy vícekrát, většina uzlů je ve spodní části vyhledávacího stromu, takže čas strávený opětovným rozšiřováním uzlů lze obvykle ignorovat. Časová složitost algoritmu je O( b l ) [1] [9] [10] .
funkce IDDFS ( v : Uzel ) : Integer ; var lim : Celé číslo ; begin lim := 0 ; zatímco ne DLS ( v , 0 , lim ) do lim := lim + 1 ; IDDFS := lim ; konec ;
Obousměrné vyhledávání do šířky (nebo hloubky) je sofistikovaný algoritmus vyhledávání do šířky (nebo hloubky), jehož myšlenkou je, že lze provádět dvě vyhledávání současně (v dopředném směru, z počátečního stavu a v opačném směru, od cíl), zastaví se poté, co se dva vyhledávací procesy setkají uprostřed.
Obousměrné vyhledávání může být založeno na iterativní strategii prohlubování. Jedna iterace zahrnuje vyhledávání do hloubky k ve směru dopředu a dvě vyhledávání do hloubky k ak + 1 směrem dozadu. Protože v paměti jsou uloženy pouze stavy nalezené přímým vyhledáváním v hloubce k , je prostorová složitost vyhledávání definována jako O ( b d /2 ). Kontrola, zda uzel nalezený zpětným vyhledáváním patří na periferii dopředného vyhledávacího stromu, může být prováděna v konstantním čase, takže časová složitost obousměrného vyhledávání je definována jako O ( b d /2 ) [1] [9] [ 11] .
| Algoritmy vyhledávání grafů | ||
|---|---|---|
| Neinformované metody | ||
| Informované metody | ||
| Zkratky | ||
| Minimální kostra | ||
| jiný | ||