Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

--- laboratoare:laborator-13 [2017/02/19 22:31]
mihai.iacov
+++ laboratoare:laborator-13 [2017/02/19 23:30]
mihai.iacov [1.2 Greedy vs. Dijkstra]
@@ Linia 21: / Linia 21: @@
  *Candidaţii = nodurile din graf care urmează să fie incluse în soluţie
  *Un candidat face parte din soluţie dacă drumul căutat trece prin el
- *Nodurile S şi D au costul potenţial = 0, dar considerăm nodul D "nedescoperit" iniţial şi plecăm din nodul S
+ *Nodurile S şi D au **costul potenţial = 0**, dar considerăm nodul D "nedescoperit" iniţial şi plecăm din nodul S
- *Toate celelalte noduri au iniţial costul potenţial infinit
+ *Toate celelalte noduri au iniţial **costul potenţial infinit**
  *Presupunem că ne aflăm la nodul curent(C) extras de la începutul cozii şi evaluăm nodurile vecine ale acestuia
@@ Linia 35: / Linia 35: @@
 ===Dijkstra===
-funcţia de **cost potenţial** g(N) = costul minim al drumului din punctul iniţial până în nodul curent(N)
+Definim funcţia de **cost potenţial** g(N) = costul minim al drumului din punctul iniţial(S) până în nodul N
+<note important>Algoritmul lui Dijkstra actualizează costul minim al drumului de la S la fiecare punct pe măsură ce explorează graful. Presupunem că actualizăm, în acelaşi timp, şi **costul potenţial**.</note>
+===Observaţii===
+ *În general, nu este **necesar** şi nici **suficient** ca funcţia de cost potenţial a unui nod să fie 0 pentru ca acel nod să facă parte din soluţia finală.
+ *Metoda Greedy poate duce la funcţia g(N) = 0 pentru noduri care par bune pe moment, dar nu se poate ajunge la D fără revenirea în nodul C(căutarea unui nou optim local după ce acesta a eşuat complet).
+ *La algoritmul lui Dijkstra, în afară de nodurile S şi D, celelalte noduri au cost potenţial nenul(excepţie dacă există muchii de cost 0).
+<note warning>Costul potenţial are rol doar în etapa de explorare a grafului. Pentru extragerea nodurilor ce formează drumul de cost minim, **nu** interpretăm costul potenţial. Este mult mai uşor să reţinem, într-un **vector de părinţi**, nodul "curent" din care am ajuns la nodul "următor", în momentul în care actualizăm costul potenţial al nodului următor.</note>
+===Performanţe===
+ *Metoda Greedy obţine **foarte repede** un rezultat(un drum de la S la D), dar, în multe cazuri, acesta **nu este cel mai scurt**(de cost minim).
+ *Algoritmul lui Dijkstra cu coadă prioritară are nevoie de **mai mult timp** pentru a obţine un rezultat, dar este **garantat** că, în momentul în care descoperă nodul D, a **găsit cel mai scurt drum** şi algoritmul se poate opri.
 f = g + h

Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Diferențe

Unelte pagină