Dybde-først-søk

Fra Wikipedia, den frie encyklopedi
Hopp til navigering Hopp til søk

Dybde-først-søk (DFS) er en søkealgoritme for grafer som prioriterer å gå nedover i grafen så langt råden er før den prøver andre stier. Når en kommer til en løvnode eller det ikke finns flere etterkommere å prøve, går en tilbake til forrige node for å prøve og finne neste etterkommere. Dette gjentas til løsningen er nådd eller når det er ingen flere stier å prøve.

Virkemåte[rediger | rediger kilde]

Søkefronten (frontier) er en liste av alle stier. I et dybde-først-søk, fungerer søkefronten som en LIFO (last-in first-out) stabel (stack) av stier. I en stabel blir elementene lagt til og fjernet fra toppen av stabelen.[1]

Egenskaper[rediger | rediger kilde]

  • Algoritmen spesifiserer ikke rekkefølgen av stiene til naboene som legges til i Frontier.
  • Ofte finner ikke optimale løsningen.
  • Trenger minne proporsjonalt med lengde på stien en holde på å undersøke.
  • Trenger tid proporsjonalt med tall på noder i søkerommet.

Referanser[rediger | rediger kilde]