Tip:
Highlight text to annotate it
X
S obzirom na ne-optimalnost pretrage prvo u dubinu
zašto bi je iko koristio?
Odgovor ima veze sa zahtevima skladištenja.
Ovde sam ilustrovao prostor stanja
koje se sastoji od veoma velikog ili čak neograničenog binarnog stabla.
Kako idemo ka nivoima 1, 2, 3, sve do nivoa n,
stablo postaje veće i veće.
Sada, hajde da razmotrimo granice za svaki od ovih algoritama pretrage.
Za pretragu prvo u širinu, znamo da granica izgleda ovako,
i kad stignemo na nivo n, trebaće nam mesto skladištenja veličine
2 na n za pretragu prvo u šitinu.
Za pretragu prvo najjeftiniji, granica će biti komplikovanija.
Izgledaće otprilike kao ova kontura troškova,
ali će imati sličan broj čvorova.
Za pretragu prvo u dubinu, kako idemo niz stablo, počećemo od ove grane,
i onda idemo nazad, ali u svakom trenutku naša granica će imati n čvorova
umesto 2 na n čvorova, tako da je to značajna ušteda za pretragu prvo u dubinu.
Sada, naravno, ali takođe pratimo istraženi niz,
onda nemamo toliko mnogo uštede.
Ali bez istraženog niza, pratraga prvo u dubinu ima veliku prednost
u smislu uštede prostora.
Možemo razmotriti još jednu osobinu algoritma
osobina celokupnosti, što znači da ako cilj postoji negde,
da li će ga algoritam naći?
Razmotrimo neograničena stabla
i redimo da postoji cilj sakriven negde duboko dole u tom stablu.
Pitanje je, koji od ovih algoritama je celokupan?
To jest, da li će zagarantovano pronaći put do cilja?
Označite kvadrate kod algoritama za koje verujete da su celokupni u tom smislu.