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/27 21:46] mihai.iacov [3.5 Quick 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 lui 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 :=== | + | </ |
- | În cazul sortării prin interclasare, | + | |
- | din acelaşi vector. | + | |
- | Sortarea prin interclasare utilizează metoda **Divide et Impera**: | + | |
- | *se împarte vectorul în secvenţe din ce în ce mai mici, astfel încât fiecare secvenţă să fie | + | Paşii algoritmului Floyd-Warshall: |
- | ordonată la un moment dat şi interclasată cu o altă secvenţă din vector corespunzătoare. | + | |
- | | + | |
- | ===Implementare :=== | + | <code> |
- | <file cpp> | + | 1. Declarăm matricile: |
- | void mergeSort(int a[],int st, int m, int dr) | + | 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 |
- | int b[100]; | + | //next este necesar doar în cazul în care ne interesează muchiile folosite |
- | int i, j, k; | + | //pasul k = 0 |
- | | + | 2. Pentru fiecare nod v |
- | // copiem prima jumatate a vectorului a in b | + | 1. dist[v][v] = 0; |
- | while (j <= m) | + | 3. Pentru fiecare pereche (u,v) a.i. există muchie de la u la v |
- | b[i++] = a[j++]; | + | 1. dist[u][v] |
- | i = 0; k = st; | + | 2. next[u][v] |
- | // copiem inapoi cel mai mare element la fiecare pas | + | //am terminat pasul k = 0 |
- | | + | 4. Pentru |
- | if (b[i] <= a[j]) | + | 1. Pentru fiecare nod i (de la 1 la N) |
- | a[k++] = b[i++]; | + | 1. Pentru fiecare nod j (de la 1 la N) |
- | | + | 1. calculăm costul nou = dist[i][k] + dist[k][j]; |
- | a[k++] = a[j++]; | + | 2. comparăm costul nou cu costul vechi = dist[i][j] |
- | // copiem elementele ramase daca mai exista | + | dacă e mai bun costul nou: |
- | while (k < j) | + | 1. dist[i][j] = costul nou; |
- | a[k++] = b[i++]; | + | 2. next[i][j] = next[i][k]; //pentru urmărirea muchiilor |
- | } | + | altfel păstrăm costul vechi |
- | void merge(int a[],int st, int dr) | + | </code> |
- | { | + | |
- | if (st < dr) | + | |
- | { | + | |
- | int m = (st+dr)/2; | + | |
- | | + | |
- | merge(a, | + | |
- | mergeSort(a, | + | |
- | } | + | |
- | } | + | |
- | </file> | + | |
- | ====3.5 Quick sort==== | + | 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 ====== |
- | * timp la limită: O(N^2) | + | <note tip> |
- | * memorie: O(log N) | + | Cei 3 algoritmi funcţionează bine atunci când **toate muchiile** au **cost pozitiv**. |
- | * Stabil: NU | + | </ |
+ | <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. | ||
- | ===Descriere :=== | + | </ |
- | Quick Sort este unul dintre cei mai rapizi | + | <note warning> |
+ | O **muchie cu cost negativ** | ||
+ | </ | ||
+ | <note tip> | ||
+ | Algoritmii **Bellman-Ford** şi **Floyd-Warshall** pot detecta dacă un graf conţine | ||
+ | * Bellman-Ford: | ||
+ | * Floyd-Warshall: | ||
- | Algoritmul | + | </ |
- | *alegerea unui element pe post de **pivot** | + | <note important> |
- | *parcurgerea vectorului din două părţi(de la stânga la pivot, de la dreapta la pivot, ambele în acelaşi timp) | + | Pentru algoritmul lui **Dijkstra**, |
- | | + | * Algoritmul se bazează pe ideea că, odată explorat un nod, drumul |
- | | + | * De aceea, algoritmul poate produce răspunsuri |
- | < | + | </note> |
+ | <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**). | ||
+ | </ | ||
- | ===Implementare :=== | + | ===== 6. Exerciții laborator |
- | <file cpp> | + | |
- | void qSort(int a[],int st,int dr) | + | |
- | { | + | |
- | int temp, | + | |
- | mijl = a[st+(dr-st)/ | + | |
- | min = st; max = dr; | + | |
- | do | + | |
- | { | + | |
- | while(a[min] < mijl) min++; | + | |
- | while(a[max] > mijl) max--; | + | |
- | if(min <= max) // | + | |
- | { | + | |
- | temp = a[min]; | + | |
- | a[min++] = a[max]; | + | |
- | a[max--] = temp; | + | |
- | } | + | |
- | }while(min <= max); //la fiecare pas sortam "mai bine" intervalul st-dr | + | |
- | //cand numai avem ce face schimbam intervalul | + | |
- | if(st < max) qSort(a, | + | |
- | if(dr > min) qSort(a, | + | |
- | } | + | |
- | </ | + | |
- | ===== 4. Exerciţii ===== | + | - 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. | ||
- | E0. Alegeţi un algoritm A(dintre Bubble, Insertion şi Selection) şi un algoritm B(dintre Merge şi Quick). Introduceţi nişte variabile globale cu care să contorizaţi numărul | + | ====6.1. Exerciții - schelet de laborator==== |
+ | Pentru acest laborator puteți descărca scheletul | ||
- | E1. Implementaţi un algoritm(dintre Bubble, Insertion şi Selection) | + | === Linux=== |
+ | Puteti folosi utilitarul '' | ||
- | E2. Implementaţi un algoritm(dintre Merge şi Quick) pentru sortarea unui vector de structuri, unde fiecare structură reprezintă un moment de timp(int ora, | + | * '' |
+ | * '' | ||
- | E3. Se dă un vector | + | Pentru compilare folositi comanda '' |
+ | |||
+ | |||
+ | ===Extra=== | ||
+ | |||
+ | - Se dă un graf pentru care se cunoaşte drumul | ||
+ | - 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:// | ||