Tip:
Highlight text to annotate it
X
Så vi har set på 2 søgealgoritmer.
Den ene, bredde-først søgning, i hvilken vi altid først udvider
de mest overfladiske stier, de korteste stier.
Dernæst, billigst-først søgning, i hvilken vi altid først udvider den sti
med den laveste samlede omkostning.
Og jeg vil benytte mig af denne lejlighed til at introducere en tredje algoritme, dybde-først søgning,
som på en måde er det modsatte af bredde-først søgning.
I dybde-først søgning udvider vi altid først den længste sti,
den sti med flest længder i sig.
Nu vil jeg bede dig, ud for hver af noderne i hvert af disse træer
at fortælle i hvilken rækkefølge de bliver udvidet,
første, anden, tredje, fjerde, femte osv. ved at skrive et tal i feltet.
Og hvis der er uafgjorte, så skriv tallet ind og afklar uafgjortheden fra venstre mod højre.
Så vil jeg bede dig stille et spørgsmål mere--eller at besvare et spørgsmål mere--
hvilket er, er disse søgninger optimale?
Dvs. er de garanteret at finde den bedste løsning?
Og for bredde-først søgning betyder optimal at den finder den korteste sti.
Hvis du mener, den er garanteret at finde den korteste sti, så sæt kryds her.
For billigst-først ville det betyde at den finder stien med den laveste samlede omkostning.
Sæt kryds her, hvis du mener den med sikkerhed vil gøre det.
Og vi vil tillade den antagelse at alle omkostningerne skal være positive.
Og i dybde-først betyder billigst eller optimal igen,
som i bredde-først, at finde den korteste sti målt på antallet af længder.
Sæt kryds her, hvis du mener dybde-først altid vil finde dén.