Dybde-først-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.