Tip:
Highlight text to annotate it
X
Med tanke på att djup-först-sökningen inte är optimal,
Varför skulle någon välja att använda den?
Svaret har att göra med lagringskraven.
Här har jag illustrerat tillståndsrymden
bestående av ett mycket stort eller till och med oändligt stort binärt träd.
När vi går till nivåerna 1, 2, 3, ned till nivå N,
blir trädet större och större.
Nu, låt oss betrakta gränsen för varje av dessa sökalgoritmer.
För bredd-först-sökning, vet vi hur en gräns ser ut,
och så när vi kommer ned till nivå n, krävs ett lagringsutrymme på
2 till n turer i en bredd-först sökning.
För billigast-först, kommer gränsen att bli mer komplicerat.
Den kommer att räkna ut denna kontur av kostnader,
men den kommer att ha ett liknande antal noder.
Men för djup-först-sökning, när vi går nedför trädet, börjar vi gå nedför denna gren,
och sedan går vi tillbaka upp, men vid varje godtycklig punkt består gränsen bara av n noder
istället för 2 till N noder, så det är en avsevärd besparing för djup-först-sökning.
Nu, naturligtvis, om vi också hålla reda på de utforskade noderna,
då vi inte får så stora besparingar.
Men utan det utforskade tillstånden, har djup-först-sökning en enorm fördel
vad gäller sparat utrymme.
Ytterligare en egenskap att beakta hos algoritmer
är egenskapen fullständighet, det vill säga att om det finns ett nåbart mål,
kommer algoritmen hitta den?
Så, låt oss gå från mycket stora träd till oändliga träd,
och låt oss säga att det finns något mål gömt någonstans djupt ned i detta träd.
Och frågan är, är var och en av dessa algoritmer kompletta?
Alltså: är de garanterade att hitta en väg till målet?
Markera i kryssrutorna för de algoritmer som du tror är kompletta i denna mening.