Dybde-først søgning

Dybde-først søgning er en algoritme til gennemkører eller søger træ eller graf datastrukturer. Man starter ved roden og udforsker så vidt muligt langs hver gren før trækker i land.

En version af dybde-først søgning blev undersøgt i det 19. århundrede af den franske matematiker Charles Pierre Trémaux som en strategi til løsning af labyrinter.

Egenskaber

Den tid og rum-analyse af DFS er forskellig i henhold til dens anvendelsesområde. I teoretisk datalogi, er DFS typisk til at krydse en hel graf, og tager tid, lineær i størrelsen af ​​grafen. I disse anvendelser er det anvender også plads i værste fald at gemme stakken af ​​knuder på søgestien samt sættet af allerede besøgte toppunkter. Således i denne indstilling, tid og rum grænser er de samme som for bredde-først søgning og valg af hvilken af ​​disse to algoritmer til at bruge, afhænger mindre på deres kompleksitet og mere på de forskellige egenskaber af vertex orderings de to algoritmer producerer .

Anvendelser af DFS i forhold til specifikke domæner, såsom at søge efter løsninger i kunstig intelligens eller web-crawling, at grafen skal gennemløbes ofte enten for store til at besøge i sin helhed eller uendelig. I sådanne tilfælde er søgning kun udføres i begrænset dybde; på grund af begrænsede ressourcer, såsom hukommelse eller diskplads, man typisk ikke bruger datastrukturer til at holde styr på mængden af ​​alle tidligere besøgte toppunkter. Når søgningen er udført til en begrænset dybde, er den tid stadig lineær med hensyn til antallet af udvidede knuder og kanter men pladsen kompleksitet variant af DFS er kun proportional med dybdegrænsen, og som et resultat, er meget mindre end den nødvendige plads til at søge til den samme dybde ved hjælp af bredde-først søgning. For sådanne anvendelser, DFS egner sig også meget bedre at heuristiske metoder til at vælge en sandsynlig udseende gren. Når en passende dybde grænse ikke er kendt på forhånd, iterativ uddybning dybde-først søgning anvender DFS gentagne gange med en sekvens af stigende grænser. I den kunstige intelligens form for analyse, med en forgrening faktor større end en, iterativ uddybning øger køretid med kun en konstant faktor i det tilfælde, hvor den korrekte dybde grænse er kendt på grund af den geometriske vækst i antallet af knudepunkter per niveau .

DFS kan også anvendes til at indsamle en prøve af graf knudepunkter. Men ufuldstændig DFS, på samme måde som ufuldstændig BFS er forudindtaget mod knudepunkter i høj grad.

Eksempel

For følgende graf:

en dybde-først søgning starter ved A, under forudsætning af at den venstre kanter i det viste graf er valgt før højre kanter, og under forudsætning af søgningen husker tidligere besøgt noder og vil ikke gentage dem, vil besøge knudepunkterne i følgende rækkefølge: A, B , D, F, E, C, G. kanter gennemløbes i denne søgning danne en Trémaux træ, en struktur med vigtige anvendelser i grafteori.

At udføre den samme søgning uden at huske tidligere besøgte noder resulterer i at besøge knudepunkter i den rækkefølge A, B, D, F, E, A, B, D, F, E osv evigt, fanget i A, B, D, F E cyklus og aldrig nå C eller G.

Iterativ uddybning er en teknik til at undgå denne uendelig løkke, og ville nå alle noder.

Output af en dybde-først søgning

En bekvem beskrivelse af en dybde første ransagning af en graf er i form af et udspændende træ af de knudepunkter nået under søgningen. Baseret på denne spanning tree, kan kanterne på det oprindelige graf opdeles i tre klasser: forreste kanter, som peger fra et knudepunkt af træet til en af ​​dens efterkommere, bagkanter, der peger fra et knudepunkt til et af sine forfædre, og cross kanter, som gør ingen af ​​delene. Sommetider træ kanter, kanter, som hører til den udspændende træ selv, klassificeres separat fra forward kanter. Hvis den oprindelige graf er ikke-orienteret så alle sine kanter er træ kanter eller ryg kanter.

Vertex orderings

Det er også muligt at anvende dybde-først søgning til lineært bestille knudepunkter af den oprindelige graf. Der er tre almindelige måder at gøre dette:

  • En preordering er en liste over de knudepunkter i den rækkefølge, de først blev besøgt af den dybde-først søgealgoritme. Dette er en kompakt og naturlig måde at beskrive forløbet af søgningen, som det blev gjort tidligere i denne artikel. En preordering af et udtryk træ er udtrykket i polsk notation.
  • En postordering er en liste over de knudepunkter i den rækkefølge, de stadig blev besøgt af algoritmen. En postordering af et udtryk træet er udtryk i omvendt polsk notation.
  • En omvendt postordering er det modsatte af en postordering, dvs. en liste over de knudepunkter i den modsatte rækkefølge af deres sidste besøg. Omvendt postordering er ikke det samme som preordering. For eksempel, når du søger på orienteret graf i forudbestilles

Pseudokode

Input: En graf G og et toppunkt v G

Output: Alle knudepunkter nås fra v mærket som opdagede

En rekursiv implementering af DFS:

En ikke-rekursiv gennemførelse af DFS:

Disse to varianter af DFS besøge naboer hvert hjørne i modsat rækkefølge fra hinanden: den første nabo mod besøg af den rekursive variation er den første på listen over tilstødende kanter, mens der i den iterative variation det første besøgte nabo er den sidste på listen over tilstødende kanter. Den ikke-rekursive gennemførelse ligner Bredde-først søge, men adskiller sig fra det på to måder: det bruger en stak i stedet for en kø, og det forsinker kontrollere, om et hjørne er blevet opdaget indtil toppunktet springer fra stablen snarere end at gøre denne kontrol før skubbe vinkelspids.

Applikationer

Algoritmer der anvender dybde-først søgning som byggesten omfatter:

  • Finde tilsluttede komponenter.
  • Topologisk sortering.
  • Finde 2 - tilsluttede komponenter.
  • Finde 3 - tilsluttede komponenter.
  • At finde de broer af en graf.
  • Generering ord for at plotte Limit Sæt med en gruppe.
  • Finde stærkt forbundne komponenter.
  • Planarity test
  • Løse gåder med kun én løsning, såsom labyrinter.
  • Maze generation må bruge et randomiseret dybde-først søgning.
  • Finde biconnectivity i grafer.
  0   0

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha