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/05 20:56] mihai.iacov |
laboratoare:laborator-07 [2018/02/25 22:45] (curent) mihai.iacov |
||
---|---|---|---|
Linia 1: | Linia 1: | ||
- | ====== Laborator 07: Drumuri | + | ====== Laborator 07: Arbori minimi |
- | ===== 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ă**. | ||
- | < | + | < |
- | ====2.3 Legătura muchii-arce: | + | ===Graf orientat slab conex=== |
- | <note tip> | + | Fie graful neorientat asociat unui graf orientat obţinut prin înlocuirea tuturor |
- | Orice graf **neorientat** este echivalent | + | |
- | 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=== |
- | </ | + | 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 | + | 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**. |
- | | + | ==== 2.3 Arbore vs. pădure de acoperire ==== |
- | | + | Pentru |
- | * 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 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 şi care să folosească muchiile ce dau suma costurilor minimă. |
- | * iniţial, toate nodurile sunt neexplorate | + | ===== 3. Algoritmul lui Kruskal ===== |
- | * atribuim | + | |
- | * 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 | + | Algoritmul |
- | * Dacă C este nodul curent(pe | + | |
- | * pentru | + | |
- | <note tip> | + | Cu alte cuvinte, găsește submulțimea muchiilor |
- | <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 |
- | Pentru grafuri orientate, ne referim la vecinii la care putem ajunge printr-un arc ce pleacă din C: (C,V). | + | |
- | </ | + | |
- | Paşii algoritmului lui Dijkstra: | + | |
- | < | + | |
- | 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 | + | |
- | 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) | + | |
- | 2. pentru fiecare din vecinii | + | |
- | 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 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) | + | |
- | </ | + | |
- | ==== 3.2 Algoritmul | + | <note tip> |
- | Principii similare pentru algoritmul Bellman-Ford: | + | Algoritmul |
- | * 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ă, | + | |
- | * 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> | + | * creează o pădure F (o mulțime de arbori), unde fiecare vârf din graf este un arbore |
- | </ | + | * creează o mulțime S care conține toate muchiile |
- | + | | |
- | Diferenţa apare, în algoritmul Bellman-Ford, la alegerea nodurilor pentru care facem evaluarea: | + | |
- | * 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 de principiul de mai sus, (N-1) astfel de paşi vor fi suficienţi. | + | * altfel, ignoră muchia |
- | <note important> | ||
- | În cazul grafurilor neorientate, | ||
</ | </ | ||
- | Paşii algoritmului Bellman-Ford: | + | {{ :laboratoare:kruskal.gif?900 |}} |
- | < | + | |
- | 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 ====== | ||
- | Următorul algoritm caută cel mai scurt drum de la **orice nod sursă(S)** la **fiecare nod destinaţie(D)**. | ||
+ | {{ : | ||
+ | ===== 4. Algoritmul lui Prim ===== | ||
- | ==== 4.1 Algoritmul | + | Algoritmul |
- | Rezultatul algoritmului | + | |
- | 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 arbore, pornind |
- | * -pleacă din i | + | |
- | * -ajunge în j | + | |
- | * -în afară | + | |
- | Algoritmul calculează costMinim(i,j,k) pentru toate perechile (i,j,k), folosind formula: **costMin(i, | + | * Intrare: Un graf conex ponderat cu nodurile V și muchiile E. |
- | + | * Initializare: Vnou = {x}, unde x este un nod arbitrar | |
- | <note tip> | + | * Alege muchia |
- | Observaţii: | + | * Se adaugă v la Vnou, (u,v) la Enou |
- | * costMin(i,j,0) = costMuchie(i,j) (dacă există | + | * Ieșire: Vnou și Enou descriu arborele parțial |
- | * costMin(i,j,N) = drumul | + | |
</ | </ | ||
- | 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 warning> | + | |
- | O **muchie cu cost negativ** este echivalentă cu **2 arce cu cost negativ** şi implică existenţa unui ciclu cu cost negativ. | + | |
- | </ | + | |
- | <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 | ||
+ | </ | ||
- | </ | + | ====5.1. Exerciții |
- | <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 | + | Pentru acest laborator puteți descărca scheletul |
- | </ | + | |
+ | === Linux=== | ||
+ | Puteti folosi utilitarul '' | ||
- | ===== 6.Exiciț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. | + | Pentru compilare folositi comanda '' |
- | - Cum putem folosi | + | |
- | - 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=== | ||
- | | + | ==== Extra ==== |
- | - Aceeaşi întrebare dacă înmulţim fiecare | + | |
- | - Cum găsiţi(mai rapid decât | + | - Se dă un graf care coincide cu un arbore minim de acoperire |
- | - Daţi un exemplu în care folosirea | + | - Se dă un graf care coincide |
- | ===== 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/ |