Uinformeret søgning (også blind søgning , brute force method , eng. uninformed search, blind search, brute-force search ) er en strategi til at finde løsninger i tilstandsrummet , som ikke bruger yderligere information om tilstande, bortset fra den, der præsenteres i opgavedefinition. Alt hvad metoden med uinformeret søgning er i stand til er at udvikle efterfølgere og skelne måltilstanden fra den ikke-måltilstand [1] [2] [3] .
Breadth-first search ( BFS ) er en tilstand-space-løsningssøgestrategi, der først udvider rodnoden, derefter alle efterfølgere af rodnoden, derefter udvider efterfølgerne af disse efterfølgere, og så videre. Før nogen noder udvides på næste niveau, udvides alle noder i en given dybde i søgetræet.
Algoritmen er færdig. Hvis alle handlinger har samme pris, er bredde-først-søgning optimal.
Det samlede antal af genererede knudepunkter (tidskompleksitet) er O( bd +1 ), hvor b er forgreningsfaktoren, d er søgedybden . Rumkompleksiteten er også O( b d +1 ) [1] .
En bred første søgeimplementering kan bruge en FIFO - kø . I begyndelsen indeholder køen kun rodnoden. Ved hver iteration af hovedsløjfen hentes curr -noden fra køens hoved . Hvis noden curr er målknuden, stopper søgningen, ellers rulles curr noden ud, og alle dens efterfølgere tilføjes til slutningen af køen [4] [5] .
funktion BFS ( v : Node ) : Boolean ; start kø ( v ) ; mens køen ikke er tom , skal du begynde curr := dequeue () ; hvis is_goal ( curr ) så start BFS := sand ; udgang ; ende ; mærke ( curr ) ; for næste i efterfølgere ( curr ) gør hvis ikke markeret ( næste ), så start køen ( næste ) ; ende ; ende ; BFS := falsk ; ende ;
Omkostningssøgning (uniform-cost search, UCS ) er en generalisering af bredde-først søgealgoritmen, der tager højde for omkostningerne ved handlinger (kanter af tilstandsgrafen). Omkostningsbaseret søgning udvider noder i stigende rækkefølge efter prisen på den korteste vej fra rodnoden. Ved hvert trin i algoritmen implementeres noden med den laveste pris g ( n ). Noder er gemt i en prioritetskø [6] .
Denne algoritme er komplet og optimal, hvis omkostningerne ved faserne er strengt taget positive. Hvis omkostningerne for alle faser er lige store, er omkostningssøgningen identisk med bredde-først-søgningen.
Omkostningsopslagsproceduren kan gå ind i en uendelig løkke, hvis der tilfældigvis er installeret en node, der har en nul-omkostningshandling, der igen peger på den samme tilstand. Det er muligt at garantere fuldstændigheden og optimaliteten af søgningen, forudsat at omkostningerne ved alle handlinger er strengt taget positive [1] .
Omkostningsbaseret søgning svarer logisk til Dijkstra 's single-source shortest-path algoritme . Især implementerer begge algoritmer de samme noder i samme rækkefølge. Den væsentligste forskel er relateret til tilstedeværelsen af noder i prioritetskøen: i Dijkstras algoritme tilføjes alle noder til køen under initialisering, mens der i den omkostningsbaserede søgealgoritme tilføjes noder "on-the-fly" ( eng . på farten, dovent ) under eftersøgningen. Det følger heraf, at Dijkstras algoritme er anvendelig på eksplicitte grafer, mens UCS-algoritmen kan anvendes på både eksplicitte og implicitte grafer [7] .
Depth -first search ( DFS ) er en tilstands-rum beslutningssøgestrategi, der altid udvider den dybeste knude i søgetræets aktuelle periferi. Dybde-først-søgning analyserer den første efterfølger af den aktuelle node på listen, derefter dens første efterfølger osv. Udvidede noder fjernes fra periferien, så yderligere søgning "genoptages" fra den næste mest lavvandede node, som stadig er uudforsket efterfølgere [1] .
Dybde-først søgestrategien kan implementeres med en LIFO stack eller med en rekursiv funktion [8] .
funktion DFS ( v : Node ; dybde : Heltal ) : Boolean ; start if is_goal ( v ) så start DFS := true ; udgang ; ende ; for næste i efterfølgere ( v ) gør hvis DFS ( næste , dybde + 1 ), så begynder DFS := sand ; udgang ; ende ; DFS := falsk ; ende ;
Dybde -begrænset søgning ( DLS ) er en variant af dybde-først søgning, der anvender en foruddefineret dybdegrænse l for at løse problemet med uendelig vej.
Dybdebegrænset søgning er ikke færdig, fordi for l < d vil målet ikke blive fundet, og er ikke optimalt for l > d . Dens tidskompleksitet er O( b l ), og dens rumkompleksitet er O( b · l ) [1] [9] .
Dybdebegrænset søgning bruges i den iterative uddybningssøgningsalgoritme.
funktion DLS ( v : Node ; dybde , grænse : Heltal ) : Boolean ; start if ( depth < limit ) then start if is_goal ( v ) then start DLS := true ; udgang ; ende ; for næste i efterfølgere ( v ) begynder hvis DLS ( næste , dybde + 1 , grænse ), så begynder DLS : = sand ; udgang ; ende ; ende ; ende ; DLS := falsk ; ende ;
Dybde-først-søgning med iterativ uddybning (iterative-deepening depth-first search, IDDFS , DFID ) er en strategi, der giver dig mulighed for at finde den bedste dybdegrænse for DLS-søgning. Dette opnås ved trinvist at øge grænsen l , indtil målet er fundet.
Iterativ uddybningssøgning kombinerer fordelene ved dybde-først-søgning (rumkompleksitet O( b · l )) og bredde-først-søgning (fuldstændighed og optimalitet for finite b og ikke-negative kantvægte).
Selvom iterativ dyb søgning genererer de samme tilstande flere gange, er de fleste af noderne i bunden af søgetræet, så den tid, der bruges på at genudvide noder, kan normalt ignoreres. Algoritmens tidskompleksitet er O( b l ) [1] [9] [10] .
funktion IDDFS ( v : Node ) : Heltal ; var lim : Heltal ; begynde lim := 0 ; mens ikke DLS ( v , 0 , lim ) gør lim := lim + 1 ; IDDFS := lim ; ende ;
Bredde (eller dybde) tovejssøgning er en sofistikeret bredde (eller dybde) søgealgoritme, hvis idé er, at to søgninger kan udføres samtidigt (i fremadgående retning, fra starttilstanden og i den modsatte retning, fra mål), stopper efter at de to søgeprocesser mødes i midten.
Den tovejssøgning kan være baseret på en iterativ uddybningsstrategi. En iteration inkluderer en søgning til dybden k i fremadgående retning og to søgninger til dybden k og k + 1 i retningen bagud. Da kun de tilstande, der findes ved direkte søgning i dybden k , er lagret i hukommelsen, er pladskompleksiteten af søgningen defineret som O ( bd /2 ). Kontrol af, om en node fundet ved en baglæns søgning tilhører periferien af et fremadgående søgetræ, kan udføres i konstant tid, så tidskompleksiteten af en tovejssøgning er defineret som O ( b d /2 ) [1] [9] [ 11] .
| Algoritmer til grafsøgning | ||
|---|---|---|
| Uoplyste metoder | ||
| Informerede metoder | ||
| Genveje | ||
| Minimumspændende træ | ||
| Andet | ||