D: Søgning i en labyrint
BFS og DFS i en labyrint — hvilken udgang findes først, og worst-case kompleksitet.
Labyrinten har $n=8\cdot 8=64$ felter. Vi søger fra indgangen $S$ til en af udgangene $A$, $B$ eller $C$. Udforskningsrækkefølge: 1. højre, 2. venstre, 3. op, 4. ned.
Hvis vi benytter en bredde-først-søgning, hvilken udgang finder vi da først? Giv en kort forklaring.
Vis svar Skjul svar
Ved BFS finder man først alle felter 1 skridt fra start, derefter 2 skridt, osv. Derfor findes den udgang der kan nås i færrest skridt først — det er udgang C.
C
Hvis vi benytter dybde-først-søgning, hvilken udgang finder vi da først? Giv en kort forklaring.
Vis svar Skjul svar
Ved DFS afgøres resultatet af udforskningsrækkefølgen. Det afgørende øjeblik er felt a3: her afsøges først mod højre, og DFS finder således først udgang A.
A
Hvor mange felter vil blive besøgt under dybde-først-søgningen? Angiv antallet inkl. startfeltet ($S$) og slutfeltet ($A$, $B$ eller $C$).
Vis svar Skjul svar
Søgningen følger den korteste sti til $A$: ved a3 går vi først til højre; ved d2 igen først til højre; ved g3 først op. Dermed besøges i alt 21 felter.
21
Hvad er worst-case-kompleksiteten (i store-O notation) for bredde-først-søgning, udtrykt i antallet af felter $n$ i labyrinten? Giv en kort forklaring.
Vis svar Skjul svar
I det værste tilfælde kan vi risikere at skulle besøge alle felter. Dermed er kompleksiteten lineær.
$O(n)$