Tip:
Highlight text to annotate it
X
Takže sme videli dva algoritmy hľadania.
Po prvé prehľadávanie do šírky, v ktorom sme vždy najprv prešli
najplytkejšiu, najkratšiu cestu.
Po druhé, vyhľadávanie najlacnejšej cesty, v ktorom sem vždy najprv vybrali
s najnižšími celkovými nákladmi.
Využijem túto príležitosť na uvedenie tretieho algoritmu: prehľadávanie do hĺbky,
ktorá je v istom zmysle protipólom prehľadávania do šírky.
Pri hĺbkovom prehľadávaní, pokračujeme najprv po najdlhšej ceste
ceste s najväčším počtom spojení.
Teraz od vás chcem, aby ste pre každý z týchto uzlov v každom zo stromov
povedali, v akom poradí budú preskúmané
prvý, druhý, tretí, štvrtý, piaty a tak ďalej, zadaním čísla do príslušného poľa.
A ak narazíte na dve rovnocenné možnosti, zadajte číslo a pokračujte v poradí zľava doprava.
Chcem od vás odpoveď na ešte jednu otázku:
ktoré z týchto vyhľadávaní je optimálne?
Je zaručené, že nájdu najlepšie riešenie?
Pre prehľadávanie do šírky je optimálna najkratšia cesta.
Ak si myslíte, že zaručuje nájdenie najkratšej cesty, zaškrtnite tu.
Pre vyhľadávanie najlacnejšieho, to znamená nájdenie cesty s najnižšími celkovými nákladmi.
Zaškrtnite tu, ak si myslíte, že to zaručuje.
Predpokladáme, že všetky náklady sú pozitívne.
A pri hĺbkovom prehľadávaní by najlacnejšie alebo optimálne znamenalo podobne
ako pri prehľadávaní do šírky, nájdenie najkratšej možnej cesty vyjadrenej počtom spojení.
Zaškrtnite tu, ak si myslíte, že prehľadávanie do hĺbky to zaručuje.