Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Ești aici: Structuri de date și algoritmi » Laboratoare » Laborator 07: Arbori minimi de acoperire
Traseu:
laboratoare:laborator-07

Diferențe

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

Link către această vizualizare comparativă

Ambele părți revizuirea anterioară Versiuni anterioare
Urmatoarea versiune 		Versiuni anterioare
Urmatoarea versiune Ambele părți următoarea reviziune
laboratoare:laborator-07 [2017/04/01 16:58]
mihai.iacov [3.2 Algoritmul Bellman-Ford] 		laboratoare:laborator-07 [2017/04/01 19:34]
mihai.iacov [5. Observaţii finale]
Linia 23: Linia 23:
  
 <note important>Pot exista mai multe drumuri de cost minim de la S la D.</note> <note important>Pot exista mai multe drumuri de cost minim de la S la D.</note>
 +
 +====2.3 Legătura muchii-arce: ====
 +<note tip>
 +Orice graf **neorientat** este echivalent cu un graf **orientat** dacă înlocuim fiecare **muchie** cu **două arce**(de acelaşi cost, câte un arc pentru fiecare sens).
 +
 +Algoritmii următori pot fi folosiţi(în limita observaţiilor finale) pe grafuri orientate la fel ca pe grafuri neorientate.
 +</note>
 +
 +
 ===== 3.Drumul de cost minim cu sursă unică ====== ===== 3.Drumul de cost minim cu sursă unică ======
 Următorii algoritmi caută drumurile de cost minim de la **un singur nod(sursă)** la **toate celelalte noduri**. Rezultatul acestor algoritmi este un **arbore cu drumuri de cost minim**, unde: Următorii algoritmi caută drumurile de cost minim de la **un singur nod(sursă)** la **toate celelalte noduri**. Rezultatul acestor algoritmi este un **arbore cu drumuri de cost minim**, unde:
Linia 44: Linia 53:
 <note tip>Construind astfel algoritmul, este **garantat** că, în momentul în care explorăm un nod(C), estimarea pentru costul drumului S-C este chiar **costul minim**.</note> <note tip>Construind astfel algoritmul, este **garantat** că, în momentul în care explorăm un nod(C), estimarea pentru costul drumului S-C este chiar **costul minim**.</note>
  
 +<note important>
 +Pentru grafuri orientate, ne referim la vecinii la care putem ajunge printr-un arc ce pleacă din C: (C,V).
 +</note>
 Paşii algoritmului lui Dijkstra: Paşii algoritmului lui Dijkstra:
 <code> <code>
Linia 104: Linia 116:
  
 ==== 4.1 Algoritmul Floyd-Warshall ==== ==== 4.1 Algoritmul Floyd-Warshall ====
-===== 5.Exiciții laborator ======+Rezultatul algoritmului este o matrice N x N(unde N = |V|, numărul de noduri), iar valorea din matrice de la poziţia [i][j] va fi costul minim pentru drumul i-j. Fie această matrice numită **dist**. 
 + 
 +Pentru simplitate, algoritmul numerotează nodurile de la 1 la N şi foloseşte următoarea construcţie: 
 +  * defineşte o funcţie costMinim(i,j,k) = cel mai ieftin drum care: 
 +  *    -pleacă din i 
 +  *    -ajunge în j 
 +  *    -în afară de primul şi de ultimul nod, conţine numai noduri din {1,2,3,...,k}(primele k noduri). 
 + 
 +Algoritmul calculează costMinim(i,j,k) pentru toate perechile (i,j,k), folosind formula: **costMin(i,j,k+1) = min(costMin(i,j,k), costMin(i,k+1,k) + costMin(k+1,j,k))**; 
 + 
 +<note tip> 
 +Observaţii: 
 +  * costMin(i,j,0) = costMuchie(i,j) (dacă există muchie de la i la j) sau infinit(altfel); 
 +  * costMin(i,j,N) = drumul de cost minim de la i la j. 
 + 
 +</note> 
 + 
 +Paşii algoritmului Floyd-Warshall: 
 + 
 +<code> 
 +1. Declarăm matricile: 
 + dist, matrice N x N şi o iniţializăm dist[i][j] = infinit, pentru orice i şi j 
 + next, matrice N x N în care vom salva prima muchie din drumul i-j de cost minim 
 + //next este necesar doar în cazul în care ne interesează muchiile folosite 
 +//pasul k = 0 
 +2. Pentru fiecare nod v 
 + 1. dist[v][v] = 0; 
 +3. Pentru fiecare pereche (u,v) a.i. există muchie de la u la v 
 + 1. dist[u][v] = costMuchie(u,v); 
 + 2. next[u][v] = v; //pentru urmărirea muchiilor ce compun drumul 
 +//am terminat pasul k = 0 
 +4. Pentru fiecare pas k (de la 1 la N) 
 + 1. Pentru fiecare nod i (de la 1 la N) 
 + 1. Pentru fiecare nod j (de la 1 la N) 
 + 1. calculăm costul nou = dist[i][k] + dist[k][j]; 
 + 2. comparăm costul nou cu costul vechi = dist[i][j] 
 + dacă e mai bun costul nou: 
 + 1. dist[i][j] = costul nou; 
 + 2. next[i][j] = next[i][k]; //pentru urmărirea muchiilor 
 + altfel păstrăm costul vechi 
 +</code> 
 + 
 +Pentru obţinerea nodurilor ce formează drumul de cost minim de la u la v, putem folosi următoarea secvenţă: 
 +<code> 
 +funcţie afişareDrum(u, v) 
 +1. dacă u == v 
 + 1. print(v); STOP 
 +2. print(u); 
 +3. afişareDrum(next[u][v], v); 
 +</code> 
 + 
 +===== 5. Observaţii finale ====== 
 +<note tip> 
 +Cei 3 algoritmi funcţionează bine atunci când **toate muchiile** au **cost pozitiv**. 
 +</note> 
 +<note warning> 
 +Drumul de cost minim **NU** este bine definit atunci când există **cicluri cu cost negativ**. 
 +  * putem ajunge de la un nod la acelaşi nod, folosind acelaşi ciclu de oricâte ori => costMinim = -infinit); 
 +  * în aceste cazuri, nu putem pune problema găsirii drumurilor de cost minim. 
 + 
 +</note> 
 +<note warning> 
 +O **muchie cu cost negativ** este echivalentă cu **2 arce cu cost negativ** şi implică existenţa unui ciclu cu cost negativ. 
 +</note> 
 +<note tip> 
 +Algoritmii **Bellman-Ford** şi **Floyd-Warshall** pot detecta dacă un graf conţine **cicluri cu cost negativ**: 
 +  * Bellman-Ford: executăm încă o evaluare a tuturor muchiilor la final. Dacă găsim cel puţin o estimare nouă mai buna, graful conţine măcar un ciclu cu cost negativ. 
 +  * Floyd-Warshall: putem verifica, la fiecare pas, dacă avem o valoare negativă pe diagonala matricei dist. Dacă găsim cel puţin o valoare negativă, graful conţine măcar un ciclu cu cost negativ. 
 + 
 +</note> 
 +<note important> 
 +Pentru algoritmul lui **Dijkstra**, "garanţia" se pierde când există chiar şi **un singur arc cu cost negativ**. 
 +  * Algoritmul se bazează pe ideea că, odată explorat un nod, drumul de cost minim până la acel nod a fost găsit, ceea ce **NU** este mereu corect în prezenţa unui arc cu cost negativ. 
 +  * De aceea, algoritmul poate produce răspunsuri **greşite** în acest caz. 
 + 
 +</note> 
 +<note tip>În schimb, algoritmii **Bellman-Ford** şi **Floyd-Warshall** funcţionează pe grafurile cu **arce cu cost negativ**, atâta timp cât drumurile de cost minim sunt bine definite(**fără cicluri cu cost negativ**). 
 +</note> 
 + 
 +===== 6.Exiciții laborator ======
  
-===== 6.Referințe ======+===== 7.Referințe ======
     - [[https://en.wikipedia.org/wiki/Dijkstra's_algorithm|Algoritmul lui Dijkstra]]     - [[https://en.wikipedia.org/wiki/Dijkstra's_algorithm|Algoritmul lui Dijkstra]]
     - [[https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm|Algoritmul lui Bellman Ford]]     - [[https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm|Algoritmul lui Bellman Ford]]
laboratoare/laborator-07.txt · Ultima modificare: 2018/02/25 22:45 de către mihai.iacov

Unelte pagină

Exceptând locurile unde este altfel specificat, conținutul acestui wiki este licențiat sub următoarea licență: CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki