Tip:
Highlight text to annotate it
X
Her er svarene.
Bredde-først søgning udfolder, som navnet antyder, noderne i denne rækkefølge.
1, 2, 3, 4, 5, 6, 7.
Så den gennemgår en stribe af gangen, bredden først.
Er den optimal?
Tja, den udvider altid de korteste stier først,
så uanset hvor målet gemmer sig, vil den finde det ved kun at undersøge
stier der ikke er længere, så den er faktisk optimal.
Billigst-først. Først udvider vi stien med længde 0,
dernæst stien med længde 2.
Nu er der en sti med længde 4, en sti med længde 5,
en sti med længde 6, en sti med længde 7 og til sidst, en sti med længde 8.
Og som vi har set, er den garanteret at finde den billigste sti af dem alle,
hvis vi antager at alle de individuelle sti-omkostninger ikke er negative.
Dybde-først søgning prøver først at gå så dybt som den kan,
så den går til 1, 2, 3, bakker så op til 4,
bakker så op, 5, 6, 7.
Og man kan se, at den ikke nødvendigvis finder den korteste af alle stier.
Lad os sige, at der var målnoder på plads 5 og på plads 3.
Den ville finde den længere sti til plads 3 og finde målet der
og ville ikke finde målet på plads 5.
Så den er ikke optimal.