Oinformerad sökning (även blind sökning , brute force method , eng. uninformed search, blind search, brute-force search ) är en strategi för att hitta lösningar i tillståndsutrymmet , som inte använder ytterligare information om tillstånd, förutom den som presenteras i uppgiftsdefinition. Allt som metoden för oinformerad sökning är kapabel till är att utveckla efterföljare och skilja måltillståndet från det icke-måltillstånd [1] [2] [3] .
Bredth-first search ( BFS ) är en sökstrategi för tillståndsrymdlösning som först expanderar rotnoden, sedan alla efterföljare till rotnoden, sedan expanderar efterföljarna till dessa efterföljare, och så vidare. Innan några noder expanderas på nästa nivå, expanderas alla noder på ett givet djup i sökträdet.
Algoritmen är klar. Om alla åtgärder har samma kostnad är bredd-först-sökning optimal.
Det totala antalet genererade noder (tidskomplexitet) är O( bd +1 ), där b är förgreningsfaktorn, d är sökdjupet . Rymdkomplexiteten är också O( b d +1 ) [1] .
En breddförsta sökimplementering kan använda en FIFO- kö . I början innehåller kön endast rotnoden. Vid varje iteration av huvudslingan hämtas curr- noden från köns huvud . Om noden curr är målnoden stoppas sökningen, annars rullas currnoden upp och alla dess efterföljare läggs till i slutet av kön [4] [5] .
function BFS ( v : Node ) : Boolean ; börja kö ( v ) ; medan kön inte är tom , börja curr := dequeue () ; om is_goal ( curr ) sedan börja BFS := sant ; avsluta ; slut ; mark ( curr ) ; för nästa i efterföljare ( curr ) gör om det inte är markerat ( nästa ) , börja sedan kö ( nästa ) ; slut ; slut ; BFS := falskt ; slut ;
Kostnadssökning (uniform-cost search, UCS ) är en generalisering av bredd-först-sökningsalgoritmen som tar hänsyn till kostnaden för åtgärder (tillståndsgrafens kanter). Kostnadsbaserad sökning expanderar noder i stigande ordning efter kostnaden för den kortaste vägen från rotnoden. Vid varje steg i algoritmen distribueras noden med lägst kostnad g ( n ). Noder lagras i en prioritetskö [6] .
Denna algoritm är komplett och optimal om kostnaderna för stegen är strikt positiva. Om kostnaderna för alla steg är lika är kostnadssökningen identisk med bredd-första-sökningen.
Kostnadssökningsproceduren kan gå in i en oändlig loop om det råkar ha en nod utplacerad som har en nollkostnadsåtgärd som återigen pekar på samma tillstånd. Det är möjligt att garantera fullständigheten och optimaliteten för sökningen, förutsatt att kostnaderna för alla åtgärder är strikt positiva [1] .
Kostnadsbaserad sökning är logiskt likvärdig med Dijkstras enkällas kortaste vägsalgoritm . I synnerhet distribuerar båda algoritmerna samma noder i samma ordning. Huvudskillnaden är relaterad till närvaron av noder i prioritetskön: i Dijkstras algoritm läggs alla noder till i kön under initiering, medan i den kostnadsbaserade sökalgoritmen läggs noder till "on-the-fly" ( sv . på-the-fly, lättjefullt ) under sökningen. Av detta följer att Dijkstras algoritm är applicerbar på explicita grafer, medan UCS-algoritmen kan tillämpas på både explicita och implicita grafer [7] .
Depth -first search ( DFS ) är en sökstrategi för tillståndsrymdsbeslut som alltid expanderar den djupaste noden i sökträdets aktuella periferi. Djup-först-sökning analyserar den första efterföljaren till den aktuella noden i listan, sedan dess första efterföljare osv. Utökade noder tas bort från periferin, så ytterligare sökning "återupptas" från den näst ytligaste noden, som fortfarande är outforskad efterträdare [1] .
Sökstrategin för djupet-först kan implementeras med en LIFO - stack eller med en rekursiv funktion [8] .
function DFS ( v : Node ; djup : Heltal ) : Boolean ; börja om is_goal ( v ) sedan börja DFS := sant ; avsluta ; slut ; för nästa i efterföljare ( v ) gör om DFS ( nästa , djup + 1 ) och börja då DFS := true ; avsluta ; slut ; DFS := falskt ; slut ;
Depth -limited search ( DLS ) är en variant av depth-first search som tillämpar en fördefinierad djupgräns l för att lösa problemet med oändlig väg.
Den djupbegränsade sökningen är inte komplett, eftersom för l < d kommer målet inte att hittas och är inte optimalt för l > d . Dess tidskomplexitet är O( b l ), och dess rymdkomplexitet är O( b · l ) [1] [9] .
Djupbegränsad sökning används i den iterativa sökalgoritmen för fördjupning.
funktion DLS ( v : Nod ; djup , gräns : heltal ) : Boolean ; börja if ( djup < gräns ) sedan börja om is_goal ( v ) sedan börja DLS := sant ; avsluta ; slut ; för nästa i efterföljare ( v ) börjar om DLS ( nästa , djup + 1 , gräns ) sedan börjar DLS : = sant ; avsluta ; slut ; slut ; slut ; DLS := falskt ; slut ;
Djup-först-sökning med iterativ fördjupning (iterative-deepening depth-first search, IDDFS , DFID ) är en strategi som låter dig hitta den bästa djupgränsen för DLS-sökning. Detta uppnås genom att stegvis öka gränsen l tills målet hittas.
Iterativ fördjupningssökning kombinerar fördelarna med djup-först-sökning (rymdkomplexitet O( b · l )) och bredd-först-sökning (fullständighet och optimalitet för finita b och icke-negativa kantvikter).
Även om iterativ djupsökning genererar samma tillstånd flera gånger, är de flesta av noderna längst ner i sökträdet, så den tid som går åt till att återexpandera noder kan vanligtvis ignoreras. Algoritmens tidskomplexitet är O( b l ) [1] [9] [10] .
function IDDFS ( v : Node ) : Heltal ; var lim : Heltal ; börja lim := 0 ; medan inte DLS ( v , 0 , lim ) gör lim := lim + 1 ; IDDFS := lim ; slut ;
Bredth (eller djup) dubbelriktad sökning är en sofistikerad bredd (eller djup) sökalgoritm, vars idé är att två sökningar kan utföras samtidigt (i framåtriktningen, från initialtillståndet och i motsatt riktning, från mål), stoppas efter att de två sökprocesserna möts i mitten.
Den dubbelriktade sökningen kan baseras på en iterativ fördjupningsstrategi. En iteration inkluderar en sökning till djup k i riktning framåt och två sökningar till djup k och k + 1 i riktning bakåt. Eftersom endast tillstånden som hittas genom direktsökning på djupet k lagras i minnet definieras sökningens rymdkomplexitet som O ( bd / 2 ). Att kontrollera om en nod som hittas av en bakåtsökning tillhör periferin av ett framåtsökträd kan utföras i konstant tid, så tidskomplexiteten för en dubbelriktad sökning definieras som O ( b d /2 ) [1] [9] [ 11] .
| Algoritmer för grafsökning | ||
|---|---|---|
| Oinformerade metoder | ||
| Informerade metoder | ||
| Genvägar | ||
| Minsta spännträd | ||
| Övrig | ||