Tip:
Highlight text to annotate it
X
Mi smo gledali 2 algoritma pretrage.
Jedan, pretraga prvo u širinu, u kojoj uvek prvo proširimo
najplići put, nakraći put.
Drugi, pretraga prvo-najjeftiniji, u kojoj smo uvek proširili prvi put
sa najnižim ukupnim troškom.
Iskoristiću priliku da predstavim treći algoritam, pretraga prvo u dubinu,
koji je na neki način suprotan od pretrage prvo u širinu.
U pretrazi prvo u dubinu, mi uvek proširimo najduži put,
put sa najviše dužina.
Sada tražim od vas da za svaki čvor u svakom ovom drvetu,
kažete redosled kojim su istraženi,
prvi, drugi, treći, četvrti, peti i tako dalje označavajući ih brojem.
Ako su dva čvora jednaka, stavite taj broj i rešite problem tako što ćete ih proširiti sa leva na desno.
Onda hoću da vas upitam da odgovorite na pitanje
koja od ovih pretraga je optimalna?
To jest, da li garantuju da će pronaći najbolje rešenje?
Kod pretrage prvo u širinu, optimalno bi značilo pronaći najkraći put.
Ako mislite da garantuje da će pronaći nakraći put, označite ovde.
Za pretragu prvo najjeftiniji, to bi značilo pronaći put sa najnižom ukupnom cenom puta.
Označite ovde ako mislite da garantuje da će to pronaći.
I pretpostavićemo da svi troškovi moraju biti pozitivni.
U pretrazi prvo u dubinu, najjeftiniji ili optimalan bi značilo,
kao i u pretrazi prvo u širinu, pronaći najkraći put u smislu broja dužina.
Označite ovde ako mislite da će pretraga prvo u dubinu uvek pronaći to.