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 16:18] mihai.iacov [3.1 Algoritmul lui Dijkstra] |
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 | + | * Î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 şi îl includem în arbore, urmând să îl explorăm(să îi evaluăm vecinii); | + | |
- | * 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 şi care să folosească muchiile ce dau suma costurilor minimă. |
- | ===== 4.Drumul de cost minim între oricare 2 noduri | + | ===== 3. Algoritmul lui Kruskal |
- | Următorul algoritm caută cel mai scurt drum de la **orice nod sursă(S)** la **fiecare nod destinaţie(D)**. | + | |
+ | Algoritmul lui Kruskal este un algoritm în teoria grafurilor care găsește arborele parțial de cost minim pentru un graf conex ponderat. | ||
- | ==== 4.1 Algoritmul Floyd-Warshall ==== | + | Cu alte cuvinte, găsește submulțimea muchiilor care formează un arbore care include toate vârfurile și care este minimizat din punct de vedere al costului. |
- | ===== 5.Exiciții laborator ====== | + | |
- | ===== 6.Referințe | + | 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 fiecare componentă conexă). Algoritmul lui Kruskal este un exemplu de **algoritm greedy**. |
- | - [[https:// | + | |
- | - [[https:// | + | <note tip> |
- | - [[http://www.algorithmist.com/index.php/Floyd-Warshall' | + | Algoritmul funcționează în felul următor: |
- | - [[https://profs.info.uaic.ro/~busaco/teach/ | + | |
- | - [[http://example.com|Link extern]] | + | * creează o pădure F (o mulțime de arbori), unde fiecare vârf din graf este un arbore separat |
+ | * creează o mulțime S care conține toate muchiile din graf | ||
+ | * atât timp cât S este nevidă | ||
+ | * elimină o muchie de cost minim din S | ||
+ | * dacă acea muchie conectează doi arbori distincți, atunci adaugă muchia în pădure, combinând cei doi arbori într-unul singur | ||
+ | * altfel, ignoră muchia | ||
+ | |||
+ | </ | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | |||
+ | {{ : | ||
+ | ===== 4. Algoritmul lui Prim ===== | ||
+ | |||
+ | 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. | ||
+ | |||
+ | <note tip> | ||
+ | Algoritmul incrementează mărimea unui arbore, pornind de la un nod, până când sunt incluse toate nodurile. | ||
+ | |||
+ | * Intrare: Un graf conex ponderat cu nodurile V și muchiile E. | ||
+ | * Initializare: | ||
+ | * Alege muchia (u,v) din E de cost minim astfel încât u este în Vnou și v nu e (dacă există mai multe astfel de muchii, se alege arbitrar) | ||
+ | * Se adaugă v la Vnou, (u,v) la Enou | ||
+ | * Ieșire: Vnou și Enou descriu arborele parțial de cost minim | ||
+ | |||
+ | </ | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | |||
+ | |||
+ | {{ : | ||
+ | ===== 5. Exerciții de laborator ===== | ||
+ | |||
+ | 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 o lungime minimă de fibră optică, lucru care duce implicit la reducerea costurilor totale. | ||
+ | |||
+ | <file cpp> | ||
+ | # explicatii format | ||
+ | # n=numar varfuri m=numar muchii | ||
+ | # 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 - schelet de laborator==== | ||
+ | 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ă şi, dacă da, găsiţi muchia ce va fi scoasă. | ||
+ | - Se dă un graf care coincide cu un arbore minim de acoperire şi un vector(V) cu K noduri din graf. Care 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. | ||
+ | |||
+ | |||
+ | ===== 6. Referințe ===== | ||
+ | - [[https:// | ||
+ | - [[https:// | ||
+ | - [[https://en.wikipedia.org/wiki/Prim%27s_algorithm|Algoritmul lui Prim]] | ||
+ | - [[http://www.bogdanturcanu.ro/spanning-tree-protocol-stp/|Protocolul STP]] | ||
+ | - [[https://en.wikipedia.org/ |