Tip:
Highlight text to annotate it
X
Evo odgovora.
Pretraga prvo u širinu, kao što ime govori, proširuje čvorove ovim redosledom
1, 2, 3, 4, 5, 6, 7.
Pretražuje preko svakog nivoa, prvo u širinu.
Da li je optimalna?
Uvek prvo proširuje nakraće puteve,
i gde god se cilj krije, naći će ga ispitivanjem
putanja koje nisu duže, tako da je optimalna.
Prvo najjeftiniji, prvo istražimo putanju dužine 0,
onda putanju dužine 2.
Putanja dužine 4, putanja dužine 5,
putanja dužine 6, putanja dužine 7 i konačno putanja dužine 8.
Kao što vidimo, garantuje da će pronaći najjeftiniji put
pretpostavljajući da troškovi nisu negativni.
Pretraga prvo u dubinu pokušava da ide duboko koliko može,
tako da ide 1, 2, 3, onda ide nazad, 4,
ide nazad, 5, 6, 7.
Kao što vidite, ne garantuje da će pronaći najkraći put.
Recimo da su ciljevi na pozicijama 5 i 3.
Pronašla bi duži put na poziciji 3 i tamo bi našla cilj
i ne bi našla cilj na poziciji 5.
Tako da nije optimalna.