Tip:
Highlight text to annotate it
X
Nå har vi sett på 2 søkealgoritmer.
En, bredde-først, der vi alltid utvider de
korteste rutene først.
Nummer to, billligste-først, der vi alltid utvider den ruten
med laveste kostnad først.
Jeg benytter nå anledningen til å introdusere en tredje algoritme, dypest-først søk,
som på en måte er det motsatte av bredde-først søk.
I bredde-først, utvider vi alltid den lengste ruten først,
den med de fleste lengdene i.
Det jeg nå vil at du gjør, er at for hver av disse nodene i hvert av disse treene,
fortell oss i hvilken rekkefølge de utvides,
første, andre, tredje, fjerde, femte, og så videre, ved at du setter et tall inn i boksen.
Og hvis du har like antall, skriv inn tallet og løs fra venstre mot høyre.
Deretter vil jeg at du spør et spørsmål til, eller svarer på ett til
hvilket av disse søkene er optimale?
Med andre ord; finner de garantert den beste løsningen?
For bredde-først vil optimal bety at den finner den korteste ruten.
Hvis du mener den er garantert å finne den korteste ruten, kryss av her.
For billigste først betyr det at den finner ruten med den laveste totalkostnaden.
Kryss av her dersom du tror den garantert vil gjøre det.
Og nå forutsetter vi at aller kostnader vil være positive.
Og i dybde først vil billigst eller optimal bety, igjen,
som i bredde først, at den finner den korteste ruten talt i antall lengder.
Kryss av her dersom du tror at dybde først alltid vil finne den.