Tip:
Highlight text to annotate it
X
Iata care sunt raspunsurile.
Algoritmul de parcurgere in largime, dupa *** sugereaza si numele, extinde nodurile in aceasta ordine:
1,2,3,4,5,6,7.
Prin urmare, parcurge de fiecare data, in largime, o linie de noduri.
Este optimal?
Ei bine, de fiecare data expandeaza mai intai cele mai scurte rute,
astfel incat, oriunde s-ar gasi obiectivul, algoritmul il va gasi
examinand rutele de dimensiune maxima egala cu cea la capatul careia se afla obiectivul. Este deci un algoritm optimal.
In cazul algoritmului “cea mai ieftina varianta (cost minim)” extindem mai intai ruta de cost zero,
apoi ruta de lungime 2.
Avem o ruta de lungime 4, una de lungime 5,
una de lungime 6, una de lungime 7, si, in cele din urma, una de lungime 8.
Dupa *** am vazut, este garantat ca va gasi cea mai ieftina ruta dintre toate posibile,
presupunand ca toate costurile individuale ale pasilor nu sunt negative.
Algoritmul de parcurgere in adancime incearca mai intai sa ajunga cat mai adanc in arbore,
astfel incat parcurge graful in felul urmator: 1,2,3 apoi se intoarce inapoi, 4,
apoi se intoarce inapoi din nou, 5,6,7.
Se poate vedea ca acest algoritm nu gaseste neaparat cea mai scurta ruta posibila.
Sa presupunem ca existau obiective in pozitiile 5 si 3.
Algoritmul gaseste ruta mai lunga catre pozitia 3, gasind obiectivul acolo
si nu ar gasi obiectivul in pozitia 5.
Cu alte cuvinte, nu este optimal.