Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
Ambele părți revizuirea anterioară Versiuni anterioare Urmatoarea versiune | Versiuni anterioare | ||
laboratoare:laborator-07 [2017/04/01 19:13] mihai.iacov [5. Observaţii finale] |
laboratoare:laborator-07 [2018/02/25 22:45] mihai.iacov |
||
---|---|---|---|
Linia 1: | Linia 1: | ||
- | ====== Laborator 07: Parcurgerea grafurilor | + | ====== Laborator 07: Arbori minimi de acoperire |
- | ===== 1.Obiective laborator | + | ===== 1. Obiective laborator===== |
- | * Înțelegerea | + | * Înțelegerea |
- | * Prezentarea | + | * Înțelegerea implementării |
- | * Înțelegerea | + | * Înțelegere |
- | * găsirea drumului minim între 2 locații (ex: GPS) | + | * rețele de calculatoare: |
- | * rutarea în cazul rețelelor | + | * prelucrarea |
+ | * în clustere: determinarea unei topologii de comunicare, în cazul în care topologia nu era una regulată(arbore, | ||
- | {{ : | + | {{ : |
- | ===== 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 | + | O componentă conexă a unui graf **neorientat** |
+ | - oricare două noduri | ||
+ | - orice nod din acest subgraf **NU este conectat** | ||
- | Costul unui drum va fi definit ca **suma costurilor** muchiilor ce compun acel drum. | + | <note important> |
- | 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ă**. | ||
- | < | + | < |
- | ===== 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: | + | |
- | * nodul sursă(S) este rădăcina arborelui; | + | |
- | * toate nodurile din graf sunt în arbore; | + | |
- | * pentru orice nod destinaţie(D), | + | |
+ | ===Graf orientat slab conex=== | ||
+ | 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. | ||
- | ==== 3.1 Algoritmul lui Dijkstra ==== | + | ===Graf orientat tare conex=== |
+ | Un graf orientat este **tare conex** dacă există drum între oricare două noduri, atât într-un sens, cât şi în celelalt. | ||
- | Algoritmul lui Dijkstra se bazează pe un principiu | + | Se pot defini |
- | * iniţial, toate nodurile sunt neexplorate şi 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 pas, alegem cel mai bun candidat dintre nodurile neexplorate, | + | |
- | * la fiecare explorare(evaluare a vecinilor), dacă găsim o nouă estimare de cost mai bună decât cea precedentă, | + | |
- | Diferenţa apare, în algoritmul lui Dijkstra, la funcţia folosită pentru | + | ==== 2.2 Arborele văzut ca graf ==== |
- | | + | Folosind noţiunile de mai sus, putem spune că un arbore este un graf(pentru |
- | | + | ==== 2.3 Arbore vs. pădure de acoperire ==== |
+ | Pentru un graf neorientat, construirea unui arbore de acoperire(nu neapărat | ||
- | <note tip> | + | Acest lucru este posibil numai dacă graful |
- | Paşii algoritmului lui Dijkstra: | + | ==== 2.4 Arbore |
- | < | + | Dacă fiecare muchie dintr-un arbore are un **cost**(o pondere), atunci **costul arborelui** este dat de **suma costurilor** muchiilor ce formează arborele. |
- | 1. Declarăm două mulţimi: | + | |
- | mulţimea nodurilor neexplorate(MN), | + | |
- | mulţimea nodurilor explorate(ME) ce compun arborele, iniţial ME = vidă; | + | |
- | 2. Atribuim fiecărui nod o estimare iniţială a costului: | + | |
- | 0 pentru nodul sursă(S); | + | |
- | infinit pentru toate celelalte; | + | |
- | 3. Cât timp există noduri în MN | + | |
- | 1. Alegem, din MN(nodurile neexplorate), | + | |
- | îl numim C(nodul curent) | + | |
- | 2. pentru fiecare din vecinii lui C care se află în MN | + | |
- | 3. calculăm noua estimare | + | |
- | 4. comparăm noua estimare cu vechiul cost(drumul S-V): | + | |
- | dacă noul cost e mai bun | + | |
- | 1. actualizăm | + | |
- | 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) | + | |
- | </ | + | |
- | ==== 3.2 Algoritmul Bellman-Ford ==== | + | Dacă, pe acelaşi principiu, fiecare muchie dintr-un graf are un cost, atunci alegerea unui **arbore minim de acoperire** presupune alegerea unui arbore care să acopere toate nodurile |
- | Principii similare pentru algoritmul Bellman-Ford: | + | ===== 3. Algoritmul |
- | * vom construi arborele, începând de la nodul S; | + | |
- | * atribuim | + | |
- | * la fiecare evaluare, dacă găsim o nouă estimare de cost mai bună decât cea precedentă, | + | |
- | * funcţia de estimare a costului este definită la fel ca la algoritmul | + | |
- | <note tip> | + | Algoritmul lui Kruskal este un algoritm în teoria grafurilor care găsește arborele parțial |
- | </ | + | |
- | Diferenţa apare, în algoritmul Bellman-Ford, | + | Cu alte cuvinte, găsește submulțimea muchiilor |
- | * Algoritmul nu are preferinţe pentru anumite noduri şi nu extrage, la fiecare pas, cel mai bun candidat. | + | |
- | * În schimb, acest algoritm evaluează **toate muchiile** la un pas. Folosindu-se | + | |
- | <note important> | + | Dacă graful nu este conex, atunci algoritmul găsește o pădure parțială de cost minim (un arbore parțial de cost minim pentru |
- | În cazul grafurilor neorientate, evaluăm fiecare | + | |
- | </ | + | |
- | Paşii algoritmului Bellman-Ford: | + | <note tip> |
- | <code> | + | Algoritmul funcționează în felul următor: |
- | 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; | + | |
- | 2. actualizăm parinte(v) = u; (pentru păstrarea muchiei folosite) | + | |
- | altfel păstrăm vechiul cost | + | |
- | </ | + | |
- | ===== 4.Drumul de cost minim între oricare 2 noduri ====== | + | * creează o pădure F (o mulțime |
- | Următorul algoritm caută cel mai scurt drum de la **orice nod sursă(S)** la **fiecare nod destinaţie(D)**. | + | |
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | </ | ||
- | ==== 4.1 Algoritmul Floyd-Warshall ==== | + | {{ : |
- | 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, | ||
- | * -pleacă din i | ||
- | * -ajunge în j | ||
- | * -în afară de primul şi de ultimul nod, conţine numai noduri din {1, | ||
- | Algoritmul | + | {{ : |
+ | ===== 4. Algoritmul lui Prim ===== | ||
+ | |||
+ | Algoritmul | ||
<note tip> | <note tip> | ||
- | Observaţii: | + | Algoritmul incrementează mărimea unui arbore, pornind de la un nod, până când sunt incluse toate nodurile. |
- | * costMin(i,j,0) = costMuchie(i,j) (dacă există | + | |
- | * costMin(i,j,N) = drumul | + | |
+ | * Initializare: | ||
+ | * Alege muchia | ||
+ | * Se adaugă v la Vnou, (u,v) la Enou | ||
+ | * Ieșire: Vnou și Enou descriu arborele parțial | ||
</ | </ | ||
- | Paşii algoritmului Floyd-Warshall: | + | {{ :laboratoare: |
- | < | ||
- | 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, | ||
- | 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 | ||
- | </ | ||
- | Pentru obţinerea nodurilor ce formează drumul de cost minim de la u la v, putem folosi următoarea secvenţă: | ||
- | < | ||
- | funcţie afişareDrum(u, | ||
- | 1. dacă u == v | ||
- | 1. print(v); STOP | ||
- | 2. print(u); | ||
- | 3. afişareDrum(next[u][v], | ||
- | </ | ||
- | ===== 5. Observaţii finale | + | {{ : |
- | <note tip> | + | ===== 5. Exerciții de laborator |
- | Cei 3 algoritmi funcţionează bine atunci când **toate muchiile** au **cost pozitiv**. | + | |
- | </ | + | |
- | <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. | + | |
- | </ | + | 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 sucursale, iar voi trebuie să asigurațu conectivitate între toate locațiile folosind |
- | <note tip> | + | |
- | Algoritmii **Bellman-Ford** şi **Floyd-Warshall** pot detecta dacă un graf conţine **cicluri cu cost negativ**: | + | |
- | * Bellman-Ford: | + | |
- | * 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> | + | <file cpp> |
- | <note important> | + | # explicatii format |
- | Pentru algoritmul lui **Dijkstra**, | + | # n=numar varfuri m=numar muchii |
- | * 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. | + | # m randuri, cate unul pentru fiecare muchie: start end cost |
- | | + | 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 | ||
+ | </ | ||
- | </note> | + | ====5.1. Exerciții - schelet de laborator==== |
- | <note tip>În schimb, algoritmii **Bellman-Ford** şi **Floyd-Warshall** funcţionează pe grafurile | + | Pentru acest laborator puteți descărca scheletul de cod de [[http:// |
- | </ | + | |
+ | === Linux=== | ||
+ | Puteti folosi utilitarul '' | ||
+ | |||
+ | | ||
+ | | ||
+ | |||
+ | Pentru compilare folositi comanda '' | ||
+ | |||
+ | |||
+ | ==== Extra ==== | ||
+ | - Se dă un graf care coincide cu un arbore minim de acoperire. Verificaţi dacă, introducând o nouă muchie în graf, costul arborelui minim de acoperire se schimbă | ||
+ | - Se dă un graf care coincide | ||
+ | - 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. | ||
- | ===== 6.Exiciții laborator ====== | ||
- | ===== 7.Referințe | + | ===== 6. Referințe ===== |
- | - [[https:// | + | - [[https:// |
- | - [[https:// | + | - [[https:// |
- | - [[http://www.algorithmist.com/index.php/Floyd-Warshall' | + | - [[https://en.wikipedia.org/wiki/Prim%27s_algorithm|Algoritmul lui Prim]] |
- | - [[https://profs.info.uaic.ro/~busaco/teach/ | + | - [[http://www.bogdanturcanu.ro/spanning-tree-protocol-stp/|Protocolul STP]] |
- | - [[http://example.com|Link extern]] | + | - [[https://en.wikipedia.org/ |