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
Ultima versiune Ambele părți următoarea reviziune
laboratoare:laborator-07 [2017/04/01 17:52]
mihai.iacov [4.1 Algoritmul Floyd-Warshall] 		laboratoare:laborator-07 [2017/04/07 16:55]
iulian.matesica [6. Exercițîi laborator]
Linia 1: Linia 1:
-====== Laborator 07: Parcurgerea grafurilor ======+====== Laborator 07: Drumuri de cost minim ======
  
 ===== 1.Obiective laborator ====== ===== 1.Obiective laborator ======
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 137: Linia 149:
 4. Pentru fiecare pas k (de la 1 la N) 4. Pentru fiecare pas k (de la 1 la N)
  1. Pentru fiecare nod i (de la 1 la N)  1. Pentru fiecare nod i (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];  1. calculăm costul nou = dist[i][k] + dist[k][j];
  2. comparăm costul nou cu costul vechi = dist[i][j]  2. comparăm costul nou cu costul vechi = dist[i][j]
Linia 146: Linia 158:
 </code> </code>
  
-===== 5.Exiciții laborator ======+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. Exerciții laborator ====== 
 + 
 +  - Daţi un exemplu de graf orientat cu un singur arc cu cost negativ pentru care algoritmul lui Dijkstra dă rezultate greşite. 
 +  - Cum putem folosi algoritmul lui Dijkstra sau algoritmul Bellman-Ford pentru a obţine aceleaşi rezultate ca algoritmul Floyd-Warshall(drumul de cost minim pentru toate perechile de noduri)? Ne limităm la grafurile pe care merg toţi cei trei algoritmi. 
 +  - Implementaţi unul din algoritmi pentru a calcula drumurile de cost minim de la un nod sursă la toate celelalte noduri într-un graf cu toate muchiile/arcele cu cost pozitiv. 
 +  - Verificaţi dacă un graf conţine cicluri negative. 
 + 
 +====6.1. Exerciții - schelet de laborator==== 
 +Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab7_drumuri_minime-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o.  
 + 
 +=== Linux=== 
 +Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare. 
 + 
 +  * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab7_drumuri_minime-skel.zip%%'' 
 +  * ''%%unzip lab7_drumuri_minime-skel.zip%%'' 
 + 
 +Pentru compilare folositi comanda ''%%make%%''. Pentru rulare puteti folosi comanda ''%%make run%%'' sau ''%%./graph%%''. 
 + 
 + 
 +===Extra=== 
 + 
 +  - Se dă un graf pentru care se cunoaşte drumul de cost minim de la un nod sursă(S) la un nod destinaţie(D). Dacă adăugăm 100 la costul fiecărei muchii, se modifică drumul de cost minim? (dacă da, daţi un exemplu; dacă nu, explicaţi de ce). 
 +  - Aceeaşi întrebare dacă înmulţim fiecare cost cu 100. 
 +  - Cum găsiţi(mai rapid decât cu cei 3 algoritmi prezentaţi) drumul de cost minim de la S la D într-un graf în care toate muchiile au acelaşi cost(1)? Cum adaptaţi soluţia în cazul în care toate muchiile au costul 1 sau 2? 
 +  - Daţi un exemplu în care folosirea algoritmului lui Dijkstra(pentru a obţine drumul de cost minim pentru toate perechile de noduri) ar fi mai rapidă decât algoritmul Floyd-Warshall. 
  
-===== 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