Tip:
Highlight text to annotate it
X
Her er svarene.
Bredde-først søk, som navnet tilsier, utvider nodene i denne rekkefølgen.
En, 2, 3, 4, 5, 6, 7.
Så den går over en stripe om gangen, bredde først.
Er det optimalt?
Vel, den utvider alltid den korteste ruten først,
så uansett hvor målet gjemmer seg, kommer den til å finne det gjennom ikke å undersøke
lengere rute, så den er faktisk optimal.
Billigste først, først utvider vi ruten med lengde null,
så ruten med lengde 2.
Nå er det en rute med lengde 4, en med lengde 5,
en med lengde 6, en med lengde 7, og en med lengde 8.
Som vi har sett vil den garantert finne den billigste ruten,
antatt at ingen av stegenes kostnad er negativ.
Dybde-først søk prøver å gå så dypt som mulig først,
så den går 1, 2, 3, returnerer, 4,
returnerer, 5, 6, 7.
Så du ser at den ikke nødvendigvis finner den korteste ruten.
La oss si at målene lå i posisjon 5 og i posisjon 3.
Den ville vinne den lengere ruten til posisjon 3 og finne målet der
og så ikke finne målet i posisjon 5.
Så den er ikke optimal.