Iterativ fordypning av dybde-første søk - Iterative deepening depth-first search

Iterativ utdyping dybde-første søk

Klasse	Søkealgoritme
Data struktur	Tre , graf
Verste fall ytelse	${\ displaystyle O (b ^ {d})}$ , hvor er forgreningsfaktoren og er dybden av den grunne løsningen ${\ displaystyle b}$${\ displaystyle d}$
Verste sakskompleksitet	${\ displaystyle O (d)}$

Graf og tre søkealgoritmer
α – β EN* B * Backtracking Stråle Bellman – Ford Best-først Toveis Borůvka Gren & bundet BFS Britisk museum D * DFS Dijkstra Edmonds Floyd – Warshall Frynsøk Hill klatring IDA * Iterativ utdyping Johnson Hopppunkt Kruskal Leksikografisk BFS LPA * Prim SMA *
Oppføringer
Grafalgoritmer Søk algoritmer Liste over grafalgoritmer
relaterte temaer
Dynamisk programmering Grafovergang Tregjennomgang Søk i spill
v t e

I datavitenskap er iterativ utdyping av søk eller mer spesifikt iterativ utdyping dybde-første søk (IDS eller IDDFS) en tilstandsrom / graf-søkestrategi der en dybdebegrenset versjon av dybde-første søk kjøres gjentatte ganger med økende dybdegrenser til målet er funnet. IDDFS er optimal som bredt-første-søk , men bruker mye mindre minne; ved hver iterasjon besøker den nodene i søketreet i samme rekkefølge som dybde-første-søk, men den kumulative rekkefølgen som noder først blir besøkt er effektivt bredde-først.

Algoritme for dirigerte grafer

Følgende pseudokode viser IDDFS implementert i form av en rekursiv dybdebegrenset DFS (kalt DLS) for dirigerte grafer . Denne implementeringen av IDDFS tar ikke hensyn til allerede besøkte noder og fungerer derfor ikke for ikke-rettede grafer .

function IDDFS(root) is
    for depth from 0 to ∞ do
        found, remaining ← DLS(root, depth)
        if found ≠ null then
            return found
        else if not remaining then
            return null

function DLS(node, depth) is
    if depth = 0 then
        if node is a goal then
            return (node, true)
        else
            return (null, true)    (Not found, but may have children)

    else if depth > 0 then
        any_remaining ← false
        foreach child of node do
            found, remaining ← DLS(child, depth−1)
            if found ≠ null then
                return (found, true)   
            if remaining then
                any_remaining ← true    (At least one node found at depth, let IDDFS deepen)
        return (null, any_remaining)

Hvis målknutepunktet blir funnet, avvikler DLS rekursjonen tilbake uten ytterligere iterasjoner. Ellers, hvis det finnes minst en node på det dybdenivået, vil gjenværende flagg la IDDFS fortsette.

2-tupler er nyttige som returverdi for å signalisere IDDFS om å fortsette å utdype eller stoppe, i tilfelle treddybde og målmedlemskap er ukjent på forhånd . En annen løsning kan bruke sentinelverdier i stedet for å representere ikke funnet eller gjenværende nivåresultater .

Egenskaper

IDDFS kombinerer dybde-første søkes plasseffektivitet og bredde-første søkets fullstendighet (når forgreningsfaktoren er endelig). Hvis det finnes en løsning, vil den finne en løsningsbane med færrest buer.

Siden iterative utdypningsbesøk sier flere ganger, kan det virke sløsende, men det viser seg ikke å være så kostbart, siden i et tre er de fleste nodene i bunnnivå, så det spiller ingen rolle om de øvre nivåene blir besøkt flere ganger.

Den største fordelen med IDDFS i søket på treet er at tidligere søk har en tendens til å forbedre heuristikken som brukes ofte, slik som killer heuristisk og alfa-beta beskjæring , slik at et mer nøyaktig estimat av poengsummen for forskjellige noder ved det endelige dybdesøket. kan forekomme, og søket fullføres raskere siden det gjøres i en bedre orden. For eksempel er alfa – beta-beskjæring mest effektiv hvis den søker de beste trekkene først.

En annen fordel er responsen til algoritmen. Fordi tidlige iterasjoner bruker små verdier for , utføres de ekstremt raskt. Dette gjør at algoritmen kan levere tidlige indikasjoner på resultatet nesten umiddelbart, etterfulgt av forbedringer når det øker. Når det brukes i en interaktiv setting, for eksempel i et sjakk- spill-program, lar dette anlegget programmet spille når som helst med gjeldende beste trekk funnet i søket det har fullført så langt. Dette kan uttrykkes på en som hver dybde av søke co rekursivt å produsere en bedre tilnærming av oppløsningen, selv om arbeidet utføres på hvert trinn er rekursivt. Dette er ikke mulig med et tradisjonelt dybde-første søk, som ikke gir mellomresultater. ${\ displaystyle d}$${\ displaystyle d}$

Asymptotisk analyse

Tidskompleksitet

Den tid kompleksiteten av IDDFS i en (velbalansert) treet virker ut til å være den samme som bredde-først-søk, det vil si , der er forgreningsgrad og er dybden av målet. ${\ displaystyle O (b ^ {d})}$${\ displaystyle b}$${\ displaystyle d}$

Bevis

I et iterativt utdypende søk utvides nodene på dybden en gang, de på dybden utvides to ganger, og så videre opp til roten av søketreet, som utvides ganger. Så det totale antallet utvidelser i et iterativt utdypende søk er ${\ displaystyle d}$${\ displaystyle d-1}$${\ displaystyle d + 1}$

${\ displaystyle b ^ {d} + 2b ^ {d-1} + 3b ^ {d-2} + \ cdots + (d-1) b ^ {2} + db + (d + 1) = \ sum _ { i = 0} ^ {d} (d + 1-i) b ^ {i}}$

hvor er antall utvidelser på dybden , er antall utvidelser på dybden , og så videre. Faktoring ut gir ${\ displaystyle b ^ {d}}$${\ displaystyle d}$${\ displaystyle 2b ^ {d-1}}$${\ displaystyle d-1}$${\ displaystyle b ^ {d}}$

${\ displaystyle b ^ {d} (1 + 2b ^ {- 1} + 3b ^ {- 2} + \ cdots + (d-1) b ^ {2-d} + db ^ {1-d} + ( d + 1) b ^ {- d})}$

La det nå . Så har vi det ${\ displaystyle x = {\ frac {1} {b}} = b ^ {- 1}}$

${\ displaystyle b ^ {d} (1 + 2x + 3x ^ {2} + \ cdots + (d-1) x ^ {d-2} + dx ^ {d-1} + (d + 1) x ^ {d})}$

Dette er mindre enn den uendelige serien

${\ displaystyle b ^ {d} (1 + 2x + 3x ^ {2} + 4x ^ {3} + \ cdots) = b ^ {d} \ left (\ sum _ {n = 1} ^ {\ infty} nx ^ {n-1} \ høyre)}$

som konvergerer til

${\ displaystyle b ^ {d} (1-x) ^ {- 2} = b ^ {d} {\ frac {1} {(1-x) ^ {2}}}}$ , for ${\ displaystyle abs (x) <1}$

Det vil si at vi har

${\ displaystyle b ^ {d} (1 + 2x + 3x ^ {2} + \ cdots + (d-1) x ^ {d-2} + dx ^ {d-1} + (d + 1) x ^ {d}) \ leq b ^ {d} (1-x) ^ {- 2}}$ , for ${\ displaystyle abs (x) <1}$

Siden eller er konstant uavhengig av (dybden), hvis (dvs. hvis forgreningsfaktoren er større enn 1), er kjøretiden til dybden-første iterative utdypingssøk . ${\ displaystyle (1-x) ^ {- 2}}$${\ displaystyle \ left (1 - {\ frac {1} {b}} \ right) ^ {- 2}}$${\ displaystyle d}$${\ displaystyle b> 1}$${\ displaystyle O (b ^ {d})}$

Eksempel

For og tallet er ${\ displaystyle b = 10}$${\ displaystyle d = 5}$

${\ displaystyle \ sum _ {i = 0} ^ {5} (5 + 1-i) 10 ^ {i} = 6 + 50 + 400 + 3000 + 20000 + 100000 = 123456}$

Alt i alt utvider et iterativt utdypende søk fra dybde helt ned til dybde bare om flere noder enn et enkelt bredde-første eller dybdebegrenset søk til dybde , når . ${\ displaystyle 1}$${\ displaystyle d}$${\ displaystyle 11 \%}$${\ displaystyle d}$${\ displaystyle b = 10}$

Jo høyere forgreningsfaktor, desto lavere er overhead for gjentatte ganger utvidede tilstander, men selv når forgreningsfaktoren er 2, tar iterativ utdypingssøk bare omtrent dobbelt så lang tid som et fullstendig bredt-første-søk. Dette betyr at tidskompleksiteten til iterativ utdyping fortsatt er . ${\ displaystyle O (b ^ {d})}$

Romkompleksitet

Den plassen kompleksiteten av IDDFS er , der er dybden i mål. ${\ displaystyle O (d)}$${\ displaystyle d}$

Bevis

Siden IDDFS, når som helst, er engasjert i et dybdeforsøk, trenger den bare å lagre en stabel med noder som representerer grenen til treet den utvider. Siden den finner en løsning med optimal lengde, er den maksimale dybden til denne stabelen , og dermed er den maksimale mengden plass . ${\ displaystyle d}$${\ displaystyle O (d)}$

Generelt er iterativ utdyping den foretrukne søkemetoden når det er et stort søkeområde og dybden på løsningen ikke er kjent.

Eksempel

For følgende graf:

et dybde-første søk som starter ved A, forutsatt at de venstre kantene i den viste grafen er valgt før høyre kanter, og forutsatt at søket husker tidligere besøkte noder og ikke vil gjenta dem (siden dette er en liten graf), vil besøke noder i følgende rekkefølge: A, B, D, F, E, C, G. Kantene som krysses i dette søket danner et Trémaux-tre , en struktur med viktige anvendelser i grafteori .

Å utføre det samme søket uten å huske tidligere besøkte noder resulterer i å besøke noder i rekkefølgen A, B, D, F, E, A, B, D, F, E osv. For alltid, fanget i A, B, D, F , E syklus og aldri nå C eller G.

Iterativ utdyping forhindrer denne sløyfen og vil nå følgende noder på følgende dybder, forutsatt at den fortsetter fra venstre mot høyre som ovenfor:

• 0: A.
• 1: A, B, C, E

(Iterativ fordypning har nå sett C, da et konvensjonelt dybde-første søk ikke gjorde det.)

• 2: A, B, D, F, C, G, E, F

(Den ser fortsatt C, men at den kom senere. Også den ser E via en annen bane, og sløyfer tilbake til F to ganger.)

• 3: A, B, D, F, E, C, G, E, F, B

Når denne dybden er lagt til, vil de to syklusene "ABFE" og "AEFB" bare bli lenger før algoritmen gir opp og prøver en annen gren.

Relaterte algoritmer

I likhet med iterativ utdyping er en søkestrategi kalt iterativ forlengelse av søk som fungerer med økende banekostnadsgrenser i stedet for dybdegrenser. Det utvider noder i rekkefølgen av økende banekostnad; derfor er det første målet det møter den med den billigste banekostnaden. Men iterativ forlengelse medfører betydelig overhead som gjør den mindre nyttig enn iterativ fordypning.

Iterativ utdyping A * er et best første søk som utfører iterativ utdyping basert på " f " -verdier som ligner på de som er beregnet i A * -algoritmen .

Toveis IDDFS

IDDFS har en toveis motstykke, som veksler to søk: en starter fra kildekoden og beveger seg langs de rettet buene, og en annen starter fra målnoden og fortsetter langs de rettet buene i motsatt retning (fra lysbuehodeknuten til lysbuen haleknute). Søkeprosessen sjekker først at kildekoden og målnoden er den samme, og returnerer i så fall den trivielle banen som består av en enkelt kilde / målnode. Ellers utvider den fremover søkende prosessen undernodene til kildenoden (settet ), den bakovergående søkeprosessen utvider foreldrenodene til målnoden (settet ), og det blir sjekket om og skjærer seg. I så fall blir en korteste vei funnet. Ellers økes søkedybden, og den samme beregningen finner sted. ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$

En begrensning av algoritmen er at den korteste banen som består av et ulikt antall buer ikke vil bli oppdaget. Anta at vi har kortest vei Når dybden når to humle langs buene, vil fremover-søket fortsette til fra , og bakover-søket vil fortsette fra til . På billedet vil søkegrensene gå gjennom hverandre, og i stedet vil en suboptimal bane bestående av et jevnt antall buer returneres. Dette er illustrert i diagrammene nedenfor: ${\ displaystyle \ langle s, u, v, t \ rangle.}$${\ displaystyle v}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle u}$

Hva som kommer til romkompleksitet, farger algoritmen de dypeste nodene i fremover søkeprosessen for å oppdage eksistensen av den midterste noden der de to søkeprosessene møtes.

Ytterligere problemer med å bruke toveis IDDFS er at hvis kilden og målnodene er i forskjellige sterkt tilkoblede komponenter, for eksempel hvis det ikke er noen lysbue som går og går inn , vil søket aldri avsluttes. ${\ displaystyle s \ i S, t \ i T}$${\ displaystyle S}$${\ displaystyle T}$

Kompleksitet i tid og rom

Kjøretiden for toveis IDDFS er gitt av

${\ displaystyle 2 \ sum _ {k = 0} ^ {n / 2} b ^ {k}}$

og romkompleksiteten er gitt av

${\ displaystyle b ^ {n / 2},}$

hvor er antall noder i den korteste stien. Siden løpetidskompleksiteten til iterativ utdyping av dybde-første søk er , er hastigheten omtrent ${\ displaystyle n}$${\ displaystyle s, t}$${\ displaystyle \ sum _ {k = 0} ^ {n} b ^ {k}}$

${\ displaystyle {\ frac {\ sum _ {k = 0} ^ {n} b ^ {k}} {2 \ sum _ {k = 0} ^ {n / 2} b ^ {k}}} = { \ frac {\ frac {1-b ^ {n + 1}} {1-b}} {2 {\ frac {1-b ^ {n / 2 + 1}} {1-b}}}} = { \ frac {1-b ^ {n + 1}} {2 (1-b ^ {n / 2 + 1})}} = {\ frac {b ^ {n + 1} -1} {2 (b ^ {n / 2 + 1} -1)}} \ approx {\ frac {b ^ {n + 1}} {2b ^ {n / 2 + 1}}} = \ Theta (b ^ {n / 2}) .}$

Pseudokode

function Build-Path(s, μ, B) is
    π ← Find-Shortest-Path(s, μ) (Recursively compute the path to the relay node)
    remove the last node from π
    return π ${\displaystyle \circ }$ B (Append the backward search stack)

function Depth-Limited-Search-Forward(u, Δ, F) is
    if Δ = 0 then
        F ← F ${\displaystyle \cup }$ {u} (Mark the node)
        return
    foreach child of u do
        Depth-Limited-Search-Forward(child, Δ − 1, F)

function Depth-Limited-Search-Backward(u, Δ, B, F) is
    prepend u to B
    if Δ = 0 then
        if u in F  then
            return u (Reached the marked node, use it as a relay node)
        remove the head node of B
        return null
    foreach parent of u do
        μ ← Depth-Limited-Search-Backward(parent, Δ − 1, B, F)
        if μ ${\displaystyle \neq }$ null then
            return μ
    remove the head node of B
    return null

function Find-Shortest-Path(s, t) is
   if s = t then
       return <s>
   F, B, Δ ← ∅, ∅, 0
   forever do
       Depth-Limited-Search-Forward(s, Δ, F)
       foreach δ = Δ, Δ + 1 do
           μ ← Depth-Limited-Search-Backward(t, δ, B, F)
           if μ ${\displaystyle \neq }$ null then
               return Build-Path(s, μ, B) (Found a relay node)
       F, Δ ← ∅, Δ + 1

Referanser