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-08 [2017/02/23 13:38] mihai.iacov [3.2 Merge sort] |
laboratoare:laborator-08 [2018/04/23 22:48] (curent) mihai.iacov [7.Referințe] |
||
---|---|---|---|
Linia 1: | Linia 1: | ||
- | ====== Laborator 08: Algoritmi | + | ====== Laborator 08: Drumuri |
- | =====1. | + | ===== 1.Obiective laborator |
+ | * Înțelegerea ideii de cost și de drum minim într-un graf | ||
+ | * Prezentarea algoritmilor care calculează drumul de cost minim | ||
+ | * Înțelegerea aplicațiilor practice prezente în: | ||
+ | * găsirea drumului minim între 2 locații (ex: GPS) | ||
+ | * rutarea în cazul rețelelor de calculatoare (ex: protocolul RIP) | ||
- | Propunem studierea următorilor algoritmi de sortare: | + | {{ :laboratoare: |
- | * Bubble Sort | + | ===== 2.Considerente teoretice ====== |
- | * Selection Sort | + | |
- | * Insertion Sort | + | |
- | * Merge Sort | + | |
- | * Quick Sort | + | |
- | =====2. Introducere===== | ||
- | ====2.1 | + | ==== 2.1 Costul unei muchii |
+ | La fel ca la arbori de acoperire, presupunem că fiecare muchie are un **cost de parcurgere**. | ||
- | Numim **sortare** | + | ==== 2.2 Costul unui drum; drumul de cost minim ==== |
+ | Într-un graf, orice drum este definit de o succesiune de muchii | ||
- | Pentru a exista o **ordine completă**, | + | Costul unui drum va fi definit ca **suma costurilor** muchiilor ce compun acel drum. |
- | Exemplu: dacă alegem drept cheie un atribut **număr întreg** | + | Fie un nod sursă(S) şi un nod destinaţie(D). Pot exista |
- | Vom descrie un algoritm | + | <note important> |
- | *timp mediu - timpul | + | |
- | | + | |
- | | + | |
- | | + | |
- | Folosim notaţia O(n) pentru a indica: | + | ====2.3 Legătura muchii-arce: ==== |
- | | + | <note tip> |
- | *o dimensiune de ordinul n pentru memoria alocată. În acest caz, spunem că avem "**complexitate | + | Orice graf **neorientat** este echivalent cu un graf **orientat** dacă înlocuim fiecare |
+ | Algoritmii următori pot fi folosiţi(în limita observaţiilor finale) pe grafuri orientate la fel ca pe grafuri neorientate. | ||
+ | </ | ||
- | ====2.2 Metodele de sortare folosite==== | ||
- | Fiecare algoritm se bazează pe o metodă de sortare: | + | ===== 3.Drumul de cost minim cu sursă unică ====== |
- | *Bubble sort - interschimbare | + | 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: |
- | *Selection sort - selecţie | + | * nodul sursă(S) este rădăcina arborelui; |
- | *Insertion sort - inserare | + | * toate nodurile din graf sunt în arbore; |
- | *Merge sort - interclasare | + | * 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. |
- | *Quick sort - partiţionare | + | |
- | =====3. | + | ==== 3.1 Algoritmul lui Dijkstra |
- | ====3.1 Bubble sort==== | + | Algoritmul lui Dijkstra se bazează pe un principiu similar cu cel al algoritmului lui Prim: |
+ | * 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ă, | ||
- | * timp mediu: O(N^2) | + | Diferenţa apare, în algoritmul lui Dijkstra, la funcţia folosită pentru estimarea costurilor, atunci când evaluăm vecinii unui nod: |
- | * timp la limită: O(N^2) | + | * Dacă C este nodul curent(pe care îl explorăm), atunci: |
- | * memorie: O(1) | + | * 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). |
- | * Stabil: DA | + | |
- | ===Descriere :=== | + | <note tip> |
- | Sortarea prin metoda bulelor se consideră drept una din cele mai puţin efective metode de | + | |
- | sortare, dar cu un algoritm mai simplu. | + | |
- | | + | <note important> |
- | fiind comparate elementele alăturate **a[i] si a[i+1]**. Dacă vor fi găsite 2 elemente neordonate, | + | Pentru grafuri orientate, ne referim la vecinii la care putem ajunge printr-un arc ce pleacă din C: (C,V). |
- | valorile lor vor fi interschimbate. | + | </ |
- | *Parcurgerea tabloului de la stânga spre dreapta se va repeta atât timp cât vor fi întâlnite | + | Paşii algoritmului lui Dijkstra: |
- | elemente neordonate. | + | < |
+ | 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 | ||
+ | 1. Alegem, din MN(nodurile neexplorate), nodul cu cel mai mic cost estimat | ||
+ | îl numim C(nodul curent) | ||
+ | 2. pentru 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)); | ||
+ | 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) | ||
+ | | ||
+ | 5. Marcăm nodul C ca explorat: îl eliminăm din MN şi îl adăugăm în ME. | ||
+ | | ||
+ | </ | ||
- | ===Implementare :=== | + | ==== 3.2 Algoritmul Bellman-Ford ==== |
- | <file cpp> | + | Principii similare pentru algoritmul Bellman-Ford: |
- | //sortare descrescatoare | + | * vom construi arborele, începând de la nodul S; |
- | void bubble(int a[],int n) | + | * atribuim un posibil cost(o estimare |
- | { | + | * la fiecare evaluare, dacă găsim o nouă estimare de cost mai bună decât |
- | int i,schimbat,aux; | + | * funcţia de estimare |
- | do | + | |
- | { | + | |
- | schimbat = 0; | + | |
- | for(i = 0; i < n-1; i++) //parcurgem vectorul | + | |
- | if(a[i] < a[i+1]) //daca valoarea i din vectorul a este | + | |
- | //mai mica decat cea de pe pozitia i+1 | + | |
- | { // | + | |
- | aux = a[i]; | + | |
- | a[i] = a[i+1]; | + | |
- | a[i+1] = aux; | + | |
- | schimbat = 1; | + | |
- | } | + | |
- | }while(schimbat); | + | |
- | } | + | |
- | </ | + | |
- | ====3.2 Selection sort==== | + | <note tip> |
+ | </ | ||
- | * timp mediu: O(N^2) | + | Diferenţa apare, în algoritmul Bellman-Ford, |
- | * timp la limită: O(N^2) | + | * Algoritmul nu are preferinţe pentru anumite noduri şi nu extrage, |
- | * memorie: O(1) | + | * Î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. |
- | * Stabil: DA | + | |
- | ===Descriere :=== | + | <note important> |
- | Acest algoritm selectează, la fiecare | + | În cazul grafurilor neorientate, |
- | i până la n).Valoarea minimă găsită la pasul i este pusă în vector la poziţia i, | + | </ |
- | intereschimbarea cu poziţia actuală a minimului.Nu este un algoritm indicat pentru vectorii | + | |
- | mari, în majoritatea cazurilor oferind rezultate mai slabe decât **insertion sort** şi **bubble sort**. | + | |
- | ===Implementare | + | Paşii algoritmului Bellman-Ford: |
- | <file cpp> | + | <code> |
- | void selectionSort(int a[],int n) | + | 1. Atribuim fiecărui nod o estimare iniţială a costului: |
- | { | + | 0 pentru nodul sursă(S); |
- | int i, | + | infinit pentru toate celelalte; |
- | for(i = 0; i < n - 1;i++) | + | 2. Executăm de N-1 ori: |
- | { | + | 1. Pentru fiecare pereche (u, v) a.i. există muchie de la u la v |
- | minPoz = i; | + | 1. calculăm noua estimare de cost = cost(drumul S-u) + cost(muchia (u,v)); |
- | min = a[i]; | + | 2. comparăm noua estimare cu vechiul cost(drumul S-v): |
- | for(j = i + 1;j < n;j++) //selectam minimul | + | dacă noul cost e mai bun |
- | //din vectorul ramas( de la i+1 la n) | + | 1. actualizăm cost(drumul S-v) = noul cost; |
- | { | + | 2. actualizăm parinte(v) |
- | if(min > a[j]) //sortare crescatoare | + | altfel păstrăm vechiul cost |
- | { | + | </code> |
- | minPoz | + | |
- | min = a[j]; | + | |
- | } | + | |
- | } | + | |
- | aux = a[i] ; | + | |
- | a[i] = a[minPoz]; // | + | |
- | a[minPoz] = aux; | + | |
- | } | + | |
- | } | + | |
- | </file> | + | |
- | ====3.3 Insertion sort==== | + | ===== 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)**. | ||
- | * timp mediu: O(N^2) | ||
- | * timp la limită: O(N^2) | ||
- | * memorie: O(1) | ||
- | * Stabil: DA | ||
- | ===Descriere :=== | + | ==== 4.1 Algoritmul Floyd-Warshall ==== |
- | Spre deosebire de alţi algoritmi de sortare, sortarea prin inserţie este folosită destul de des | + | 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 |
- | pentru sortarea tablourilor cu **număr mic de elemente**. De exemplu, poate fi folosit | + | |
- | îmbunătăţi rutina de sortare rapidă. | + | |
- | | + | |
- | imaginar în două părţi - o parte sortată şi o parte nesortată. La început, partea sortată conţine | + | |
- | primul element al tabloului şi partea nesortată conţine restul tabloului. | + | |
- | *La fiecare pas, algoritmul ia primul element din partea nesortată şi il inserează în locul potrivit al părţii sortate. | + | |
- | *Când partea nesortată nu mai are nici un element, algoritmul se opreste. | + | |
- | ===Implementare | + | Pentru simplitate, algoritmul numerotează nodurile de la 1 la N şi foloseşte următoarea construcţie: |
- | <file cpp> | + | * defineşte o funcţie costMinim(i,j,k) = cel mai ieftin drum care: |
- | void insertionSort(int a[], int n) | + | |
- | { | + | |
- | int i, j, aux; | + | |
- | | + | |
- | | + | |
- | | + | |
- | while (j > 0 && a[j - 1] > a[j]) | + | |
- | | + | |
- | aux = a[j]; // | + | |
- | a[j] = a[j - 1]; | + | |
- | a[j--] = aux; | + | |
- | | + | |
- | } | + | |
- | } | + | |
- | </ | + | |
- | ====3.4 Merge sort==== | + | Algoritmul calculează costMinim(i, |
- | * timp mediu: O(N log N) | + | <note tip> |
- | * timp la limită: O(N log N) | + | Observaţii: |
- | * memorie: O(N) | + | * costMin(i, |
- | * Stabil: DA | + | * costMin(i,j,N) = drumul de cost minim de la i la j. |
- | Descriere : | + | </note> |
- | In cazul sortarii prin interclasare vectorii care se interclaseaza sunt doua secvente ordonate | + | |
- | din acelasi vector. | + | |
- | Sortarea prin interclasare utilizeaza metoda Divide et Impera: | + | |
- | - se imparte vectorul in secvente din ce in ce mai mici., astfel incat fiecare secventa sa fie | + | |
- | ordonata la un moment dat si interclasata cu o alta secventa din vector corespunzatoare. | + | |
- | - practic interclasarea va incepe cand se ajunge la o secventa formata din doua elemente. | + | |
- | Aceasta odata ordonata se va interclasa cu o alta corespunzatoare. Cele doua secvente vor | + | |
- | alcatui in subsir ordonat din vector mai mare care la randul lui se va interclasa cu subsirul | + | |
- | corespunzator s.a.m.d. | + | |
- | Implementare : | + | |
- | <file cpp> | + | |
- | void mergeSort(int a[],int st, int m, int dr) | + | |
- | { | + | |
- | int b[100]; | + | |
- | int i, j, k; | + | |
- | i = 0; j = st; | + | |
- | | + | |
- | while (j <= m) | + | |
- | b[i++] = a[j++]; | + | |
- | i = 0; k = st; | + | |
- | // copiem inapoi cel mai mare element la fiecare pas | + | |
- | while (k < j && j <= dr) | + | |
- | if (b[i] <= a[j]) | + | |
- | a[k++] = b[i++]; | + | |
- | else | + | |
- | a[k++] = a[j++]; | + | |
- | // copiem elementele ramase daca mai exista | + | |
- | while (k < j) | + | |
- | a[k++] = b[i++]; | + | |
- | } | + | |
- | void merge(int a[],int st, int dr) | + | |
- | { | + | |
- | if (st < dr) | + | |
- | { | + | |
- | int m = (st+dr)/ | + | |
- | merge(a,st, m); | + | |
- | merge(a, | + | |
- | mergeSort(a, | + | |
- | } | + | |
- | } | + | |
- | </file> | + | |
- | ====3.1 Quick sort==== | + | Paşii algoritmului Floyd-Warshall: |
- | * timp mediu: O(N log N) | + | < |
- | * timp la limită: O(N^2) | + | 1. Declarăm matricile: |
- | * memorie: | + | dist, matrice N x N şi o iniţializăm dist[i][j] = infinit, pentru orice i şi j |
- | * Stabil: NU | + | 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 | ||
+ | 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, v) | ||
+ | 1. dacă u == v | ||
+ | 1. print(v); STOP | ||
+ | 2. print(u); | ||
+ | 3. afişareDrum(next[u][v], | ||
+ | </ | ||
+ | |||
+ | ===== 5. Observaţii finale ====== | ||
+ | <note tip> | ||
+ | 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. | ||
+ | |||
+ | </ | ||
+ | <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: | ||
+ | |||
+ | </ | ||
+ | <note important> | ||
+ | Pentru algoritmul lui **Dijkstra**, | ||
+ | * 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 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**). | ||
+ | </ | ||
+ | |||
+ | ===== 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/ | ||
+ | - 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:// | ||
+ | |||
+ | === Linux=== | ||
+ | Puteti folosi utilitarul '' | ||
+ | |||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | Pentru compilare folositi comanda '' | ||
+ | |||
+ | |||
+ | ===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. | ||
+ | |||
+ | |||
+ | ===== 7.Referințe ====== | ||
+ | - [[https:// | ||
+ | - [[https:// | ||
+ | - [[http:// | ||
+ | - [[https:// | ||