Unelte utilizator

Unelte site


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
laboratoare:laborator-07 [2017/04/02 15:57]
mihai.iacov [6.Exiciții laborator]
laboratoare:laborator-07 [2018/02/25 22:45] (curent)
mihai.iacov
Linia 1: Linia 1:
-====== Laborator 07: Parcurgerea grafurilor ======+====== Laborator 07: Arbori minimi de acoperire ======
  
-===== 1.Obiective laborator ====== +===== 1. Obiective laborator===== 
-  * Înțelegerea ideii de cost și de drum minim într-un graf +  * Înțelegerea conceptului de arbore minim de acoperire  
-  * Prezentarea algoritmilor care calculează drumul de cost minim +  * Înțelegerea implementării algoritmilor care determină acest arbore 
-  * Înțelegerea aplicațiilor practice prezente în: +  * Înțelegere aplicațiilor practice în: 
-    * găsirea drumului minim între 2 locații (ex: GPS+    * rețele de calculatoare: obținerea unui cost redus la interconectarea mai multor stații (ex: protocolul STP folosit în LAN-uri
-    * rutarea în cazul rețelelor de calculatoare (ex: protocolul RIP)+    * prelucrarea de imagine: segmentarea cadrelor (ex: folosită în analiza medicală) 
 +    * în clustere: determinarea unei topologii de comunicare, în cazul în care topologia nu era una regulată(arbore, inel)
  
-{{ :laboratoare:rip.gif?600 | RIP protocol}} +{{ :laboratoare:segmentation.jpg?600 | Segmentarea de imagini}}
-===== 2.Considerente teoretice ======+
  
 +===== 2. Introducere =====
  
-==== 2.1 Costul unei muchii ==== +==== 2.1 Conexitate în grafuri ====
-La fel ca la arbori de acoperire, presupunem că fiecare muchie are un **cost de parcurgere**.+
  
-==== 2.2 Costul unui drum; drumul de cost minim ==== +===Componentă conexă=== 
-Într-un graf, orice drum este definit de o succesiune de muchii (cu proprietatea că, pentru oricare două muchii consecutive din succesiune, nodul destinaţie/de sosire al primei muchii este acelaşi cu nodul sursa/de plecare al celei de-a doua muchii).+O componentă conexă a unui graf **neorientat** este un subgraf cu următoarele proprietăţi: 
 +  - oricare două noduri din acest subgraf sunt **conectate**(există un lanţ între ele) 
 +  - orice nod din acest subgraf **NU este conectat** cu niciun nod din afara subgrafului(nodurile din componentă fac muchii numai cu alte noduri din componentă)
  
-Costul unui drum va fi definit ca **suma costurilor** muchiilor ce compun acel drum.+<note important>Orice graf neorientat are cel puţin o componentă conexă.</note>
  
-Fie un nod sursă(S) şi un nod destinaţie(D). Pot exista mai multe drumuri de la S la D(drumuri care au S primul nod, D ultimul nod), iar drumul de cost minim de la S la D va fi cel mai ieftin(cu costul cel mai mic) dintre acestea.+===Graf neorientat conex=== 
 +Un graf neorientat este numit **conex** dacă are o singură **componentă conexă**.
  
-<note important>Pot exista mai multe drumuri de cost minim de la S la D.</note>+<note tip>Putem explora toate nodurile dintr-un graf neorientat conex dintr-o singură parcurgere a grafului(DFS sau BFS).</note>
  
-====2.3 Legătura muchii-arce: ==== +===Graf orientat slab conex=== 
-<note tip> +Fie graful neorientat asociat unui graf orientat obţinut prin înlocuirea tuturor **arcelor** cu **muchii**. Atunci un graf orientat este **slab conex** dacă graful neorientat asociat acestuia este conex.
-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. +===Graf orientat tare conex=== 
-</note>+Un graf orientat este **tare conex** dacă există drum între oricare două noduri, atât într-un sens, cât şi în celelalt.
  
 +Se pot defini similar componentele slab conexă şi tare conexă.
  
-===== 3.Drumul de cost minim cu sursă unică ====== +==== 2.2 Arborele văzut ca graf ==== 
-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: +Folosind noţiunile de mai sus, putem spune că un arbore este un graf(pentru simplitate, fie neorientat) **conex** şi cu număr minim de muchii, prin urmare, **aciclic**. 
-  nodul sursă(S) este rădăcina arborelui; +==== 2.3 Arbore vs. pădure de acoperire ==== 
-  * toate nodurile din graf sunt în arbore; +Pentru un graf neorientat, construirea unui arbore de acoperire(nu neapărat de cost minim) presupune construirea unui arbore care să fie **graf parţial**(să **acopere** toate nodurile).
-  * pentru orice nod destinaţie(D), costul drumului din arbore de la rădăcina S la D este drum de cost minim(de la S la D) în graf.+
  
 +Acest lucru este posibil numai dacă graful este **conex**. În caz contrar, se poate construi câte un arbore de acoperire pentru fiecare **componentă conexă** a grafului, spunând că se construieşte o **pădure** de acoperire pentru graf.
  
-==== 3.1 Algoritmul lui Dijkstra ====+==== 2.4 Arbore de cost minim ==== 
 +Dacă fiecare muchie dintr-un arbore are un **cost**(o pondere), atunci **costul arborelui** este dat de **suma costurilor** muchiilor ce formează arborele.
  
-Algoritmul lui Dijkstra se bazează pe un principiu similar cu cel al algoritmului lui Prim: +Dacăpe acelaşi principiufiecare muchie dintr-un graf are un cost, atunci alegerea unui **arbore minim de acoperire** presupune alegerea unui arbore care să acopere toate nodurile şi care să folosească muchiile ce dau suma costurilor minimă. 
-  * iniţial, toate nodurile sunt neexplorate şi vom construi arboreleîncepând de la nodul S; +===== 3Algoritmul lui Kruskal =====
-  * atribuim un posibil cost(o estimare a distanţei) pentru fiecare nod. (iniţialS are costul 0, toate celelalte noduri au costul **infinit**); +
-  * la fiecare pas, alegem cel mai bun candidat dintre nodurile neexplorate, urmând să îl explorăm(să îi evaluăm vecinii), iar acel candidat va rămâne în arbore; +
-  * la fiecare explorare(evaluare a vecinilor), dacă găsim o nouă estimare de cost mai bună decât cea precedentă, folosim, mai departe, noua estimare. Dacă dorim să ţinem evidenţa muchiilor folosite, actualizăm şi nodul părinte al vecinului respectiv.+
  
-Diferenţa apare, în algoritmul lui Dijkstra, la funcţia folosită pentru estimarea costurilor, atunci când evaluăm vecinii unui nod: +Algoritmul lui Kruskal este un algoritm în teoria grafurilor care găsește arborele parțial de cost minim pentru un graf conex ponderat
-  * Dacă C este nodul curent(pe care îl explorăm), atunci: +
-  * pentru fiecare nod vecin(V) al lui C, noul cost posibil va fi costul drumului S-V(de la S la V) care trece prin C, mai exact - suma dintre costul drumului S-C şi costul muchiei (C,V).+
  
-<note tip>Construind astfel algoritmuleste **garantat** că, în momentul în care explorăun nod(C), estimarea pentru costul drumului S-C este chiar **costul minim**.</note>+Cu alte cuvintegăsește submulțimea muchiilor care formează un arbore care include toate vârfurile și care este minimizat din punct de vedere al costului
  
-<note important> +Dacă graful nu este conexatunci algoritmul găsește o pădure parțială de cost minim (un arbore parțial de cost minim pentru fiecare componentă conexă). Algoritmul lui Kruskal este un exemplu de **algoritm greedy**.
-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: +
-<code> +
-1. Declarăm două mulţimi: +
- mulţimea nodurilor neexplorate(MN), iniţial MN conţine toate nodurile; +
- mulţimea nodurilor explorate(ME) ce compun arborele, iniţial ME = vidă; +
-2. Atribuim fiecărui nod o estimare iniţială a costului: +
-pentru nodul sursă(S); +
- infinit pentru toate celelalte; +
-3. Cât timp există noduri în MN +
- 1. Alegem, din MN(nodurile neexplorate), nodul cu cel mai mic cost estimat +
- îl numim C(nodul curent) +
- 2pentru fiecare din vecinii lui C care se află în MN  +
- 3. calculăm noua estimare de cost = cost(drumul S-C) + cost(muchia (C,V)); +
- 4comparăm noua estimare cu vechiul cost(drumul S-V): +
- dacă noul cost e mai bun +
- 1. actualizăm cost(drumul S-V) = noul cost; +
- 2. actualizăm parinte(V) = C; (pentru păstrarea muchiei folosite) +
- altfel păstrăm vechiul cost +
- 5. Marcăm nodul C ca explorat: îl eliminăm din MN şi îl adăugăm în ME. +
- (Nu va mai fi verificat) +
-</code>+
  
-==== 3.2 Algoritmul Bellman-Ford ==== +<note tip> 
-Principii similare pentru algoritmul Bellman-Ford: +Algoritmul funcționează în felul următor:
-  * vom construi arborele, începând de la nodul S; +
-  * atribuim un posibil cost(o estimare a distanţei) pentru fiecare nod. (iniţial, S are costul 0, toate celelalte noduri au costul **infinit**); +
-  * la fiecare evaluare, dacă găsim o nouă estimare de cost mai bună decât cea precedentă, folosim, mai departe, noua estimare. Dacă dorim să ţinem evidenţa muchiilor folosite, actualizăm şi nodul părinte. +
-  * funcţia de estimare a costului este definită la fel ca la algoritmul lui Dijkstra(costul drumului de la S la nodul respectiv)+
  
-<note tip>Rezultatul algoritmului va fi un arbore cu N noduri(unde N = |V|, numărul de noduri din graf). Prin urmare, **lungimea** oricărui drum de la la alt nod va fi **maxim N-1**. (Presupunem că nu se repetă muchii) +  *  creează o pădure F (o mulțime de arbori), unde fiecare vârf din graf este un arbore separat 
-</note> +  *  creează o mulțime S care conține toate muchiile din graf 
- +   atât timp cât S este nevidă 
-Diferenţa apare, în algoritmul Bellman-Ford, la alegerea nodurilor pentru care facem evaluarea: +      elimină o muchie de cost minim din S 
-  Algoritmul nu are preferinţe pentru anumite noduri şi nu extragela fiecare pas, cel mai bun candidat. +      dacă acea muchie conectează doi arbori distincțiatunci adaugă muchia în pădure, combinând cei doi arbori într-unul singur 
-  * În schimb, acest algoritm evaluează **toate muchiile** la un pas. Folosindu-se de principiul de mai sus, (N-1) astfel de paşi vor fi suficienţi.+      altfelignoră muchia
  
-<note important> 
-În cazul grafurilor neorientate, evaluăm fiecare muchie în ambele sensuri. 
 </note> </note>
  
-Paşii algoritmului Bellman-Ford: +{{ :laboratoare:kruskal.gif?900 |}}
-<code> +
-1. Atribuim fiecărui nod o estimare iniţială a costului: +
- 0 pentru nodul sursă(S); +
- infinit pentru toate celelalte; +
-2. Executăm de N-1 ori: +
- 1. Pentru fiecare pereche (u, v) a.i. există muchie de la u la v +
- 1. calculăm noua estimare de cost = cost(drumul S-u) + cost(muchia (u,v)); +
- 2. comparăm noua estimare cu vechiul cost(drumul S-v): +
- dacă noul cost e mai bun +
- 1. actualizăm cost(drumul S-v) = noul cost; +
- 2actualizăm parinte(v) = u; (pentru păstrarea muchiei folosite) +
- altfel păstrăm vechiul cost +
-</code>+
  
-===== 4.Drumul de cost minim între oricare 2 noduri ====== 
-Următorul algoritm caută cel mai scurt drum de la **orice nod sursă(S)** la **fiecare nod destinaţie(D)**. 
  
 +{{ :laboratoare:kruskal2.gif?900 |}}
 +===== 4. Algoritmul lui Prim =====
  
-==== 4.1 Algoritmul Floyd-Warshall ==== +Algoritmul lui Prim este un algoritm din teoria grafurilor care găsește arborele parțial de cost minim al unui graf conex ponderatÎnseamnă că găsește submulțimea muchiilor care formează un arbore care include toate vârfurile și al cărui cost este minimizat
-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-jFie această matrice numită **dist**.+
  
-Pentru simplitate, algoritmul numerotează nodurile de la 1 la N şi foloseşte următoarea construcţie: +<note tip> 
-  * defineşte o funcţie costMinim(i,j,k) = cel mai ieftin drum care: +Algoritmul incrementează mărimea unui arborepornind de la un nod, până când sunt incluse toate nodurile.
-  *    -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))**; +    * Intrare: Un graf conex ponderat cu nodurile V șmuchiile E. 
- +    * InitializareVnou {x}unde x este un nod arbitrar (punct de plecaredin VEnou= {} repetă până când Vnou=V
-<note tip> +        Alege muchia (u,vdin E de cost minim astfel încât u este în Vnou șv nu e (dacă există mai multe astfel de muchii, se alege arbitrar) 
-Observaţii+        * Se adaugă v la Vnou, (u,vla Enou 
-  costMin(i,j,0= costMuchie(i,j) (dacă există muchie de la i la j) sau infinit(altfel); +    Ieșire: Vnou șEnou descriu arborele parțial de cost minim
-  costMin(i,j,N) = drumul de cost minim de la i la j.+
  
 </note> </note>
  
-Paşii algoritmului Floyd-Warshall:+{{ :laboratoare:prim.gif?900 |}}
  
-<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 =====+{{ :laboratoare:prim2.gif?900 |}} 
-<note tip> +===== 5. Exerciții de laborator =====
-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> +1.Vi s-a asignat rolul de nou coordonator al departamentul de rețelistică al companiei Coca Cola (Pepsi petru cei cărora nu le place Cola)Sediul companiei are arondate N-1 sucursaleiar voi trebuie să asigurațu conectivitate între toate locațiile folosind lungime minimă de fibră optică, lucru care duce implicit la reducerea costurilor totale
-<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 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 verificala fiecare pas, dacă avem 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+<file cpp
-<note important> +# explicatii format  
-Pentru algoritmul lui **Dijkstra**, "garanţia" se pierde când există chiar şi **un singur arc cu cost negativ**. +# n=numar varfuri m=numar muchii 
-  * Algoritmul se bazează pe ideea că, odată explorat un noddrumul 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. +# m randuricate unul pentru fiecare muchie: start end cost 
-  * De aceea, algoritmul poate produce răspunsuri **greşite** în acest caz.+8 13   
 +1 2 4  
 +1 3 9 
 +1 4 1 
 +1 6 7 
 +2 3 12 
 +2 4 4 
 +3 8 13 
 +4 5 7 
 +4 6 8 
 +5 6 3 
 +5 7 6 
 +5 8 5 
 +7 8 2 
 +</file>
  
-</note> +====5.1. Exerciții schelet de laborator==== 
-<note tip>În schimb, algoritmii **Bellman-Ford** ş**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**)+Pentru acest laborator putețdescărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab6_arbori_min-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o.  
-</note>+ 
 +=== Linux=== 
 +Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
  
-===== 6.Exiciții laborator ======+  * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab6_arbori_min-skel.zip%%'' 
 +  * ''%%unzip lab6_arbori_min-skel.zip%%''
  
-  - Daţi un exemplu de graf orientat cu un singur arc cu cost negativ pentru care algoritmul lui Dijkstra dă rezultate greşite. +Pentru compilare folositi comanda ''%%make%%''Pentru rulare puteti folosi comanda ''%%make run%%'' sau ''%%./graph%%''.
-  - Daţi un exemplu de graf pentru care algoritmul lui Dijkstra lucrează mult mai uşor decât algoritmul Bellman-Ford. +
-  - 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.+
  
-===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)+==== Extra ==== 
-  - Aceeaşi întrebare dacă înmulţim fiecare cost cu 100. +  - Se dă un graf care coincide cu un arbore minim de acoperireVerificaţi dacă, introducând o nouă muchie în grafcostul arborelui minim de acoperire se schimbă şi, dacă da, găsiţi muchia ce va fi scoasă
-  - Cum găsiţi(mai rapid decât cu cei 3 algoritmi prezentaţi) drumul de cost minim de la 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?+  - Se dă un graf care coincide cu un arbore minim de acoperire şi un vector(V) cu K noduri din grafCare este costul minim al muchiilor pe care trebuie să le eliminaţi din graf pentru ca fiecare nod din vectorul V să se afle în altă componentă conexă. (Să nu existe drum între oricare două noduri din vectorul V). 
 +  Se dă un graf care coincide cu un arbore minim de acoperire şi un nod auxiliar care formează doar două muchii. Verificaţi dacă folosirea nodului auxiliar pentru a conecta nodurile duce la un arbore de acoperire cu un cost mai mic.
  
  
-===== 7.Referințe ====== +===== 6. Referințe ===== 
-    - [[https://en.wikipedia.org/wiki/Dijkstra's_algorithm|Algoritmul lui Dijkstra]] +  - [[https://en.wikipedia.org/wiki/Minimum_spanning_tree|Minimum spanning tree]] 
-    - [[https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm|Algoritmul lui Bellman Ford]] +  - [[https://en.wikipedia.org/wiki/Kruskal%27s_algorithm|Algoritmul lui Kruskal]] 
-    - [[http://www.algorithmist.com/index.php/Floyd-Warshall's_Algorithm|Algoritmul lui Floyd-Warshall]] +  - [[https://en.wikipedia.org/wiki/Prim%27s_algorithm|Algoritmul lui Prim]] 
-    - [[https://profs.info.uaic.ro/~busaco/teach/courses/net/docs/protocoale_rutare.pdf|Protocoale de rutare]] +  - [[http://www.bogdanturcanu.ro/spanning-tree-protocol-stp/|Protocolul STP]] 
-    - [[http://example.com|Link extern]]+  - [[https://en.wikipedia.org/wiki/Image_segmentation|Segmentarea de imagini]]
laboratoare/laborator-07.1491137878.txt.gz · Ultima modificare: 2017/04/02 15:57 de către mihai.iacov