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/04/19 22:49] iulian.matesica [3.3 Insertion 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. | ||
+ | | ||
+ | </ | ||
- | {{ : | + | ==== 3.2 Algoritmul Bellman-Ford ==== |
+ | Principii similare pentru algoritmul Bellman-Ford: | ||
+ | * 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) | ||
- | ===Implementare :=== | + | <note tip>Rezultatul algoritmului va fi un arbore cu N noduri(unde N = |V|, numărul de noduri din graf). Prin urmare, **lungimea** oricărui drum de la S la alt nod va fi **maxim N-1**. (Presupunem că nu se repetă muchii) |
- | <file cpp> | + | </note> |
- | //sortare descrescatoare | + | |
- | void bubble(int a[],int n) | + | |
- | { | + | |
- | int i,schimbat, | + | |
- | 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); | + | |
- | } | + | |
- | </file> | + | |
- | ====3.2 Selection sort==== | + | Diferenţa apare, în algoritmul Bellman-Ford, |
+ | * 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. | ||
- | * timp mediu: O(N^2) | + | <note important> |
- | * timp la limită: O(N^2) | + | În cazul grafurilor neorientate, |
- | * memorie: O(1) | + | </ |
- | * Stabil: DA | + | |
- | ===Descriere | + | Paşii algoritmului Bellman-Ford: |
- | Acest algoritm selectează, la fiecare pas i, cel mai mic element din vectorul nesortat(de la poziţia | + | < |
- | i până la n).Valoarea minimă găsită la pasul i este pusă în vector | + | 1. Atribuim fiecărui nod o estimare iniţială a costului: |
- | intereschimbarea cu poziţia actuală a minimului.Nu este un algoritm indicat pentru vectorii | + | 0 pentru nodul sursă(S); |
- | mari, în majoritatea cazurilor oferind rezultate | + | 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 | ||
+ | </ | ||
- | ===Implementare :=== | + | ===== 4.Drumul de cost minim între oricare 2 noduri |
- | <file cpp> | + | Următorul algoritm caută cel mai scurt drum de la **orice nod sursă(S)** |
- | void selectionSort(int a[],int n) | + | |
- | { | + | |
- | int i, | + | |
- | for(i | + | |
- | { | + | |
- | minPoz | + | |
- | min = a[i]; | + | |
- | for(j | + | |
- | //din vectorul ramas( | + | |
- | { | + | |
- | if(min > a[j]) //sortare crescatoare | + | |
- | { | + | |
- | minPoz = j; //pozitia elementului minim | + | |
- | min = a[j]; | + | |
- | } | + | |
- | } | + | |
- | aux = a[i] ; | + | |
- | a[i] = a[minPoz]; // | + | |
- | a[minPoz] = aux; | + | |
- | } | + | |
- | } | + | |
- | </ | + | |
- | ====3.3 Insertion sort==== | ||
- | * timp mediu: O(N^2) | + | ==== 4.1 Algoritmul Floyd-Warshall ==== |
- | * timp la limită: O(N^2) | + | 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**. |
- | | + | |
- | | + | |
- | ===Descriere :=== | + | Pentru simplitate, algoritmul numerotează nodurile |
- | Spre deosebire | + | * defineşte o funcţie costMinim(i,j,k) = cel mai ieftin drum care: |
- | pentru sortarea tablourilor cu **număr mic de elemente**. De exemplu, poate fi folosit pentru a | + | |
- | îmbunătăţi rutina de sortare rapidă. | + | * |
- | *Sortarea prin inserţie seamană oarecum cu sortarea prin selecţie. Tabloul este împărţit | + | |
- | imaginar | + | |
- | 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. | + | |
- | | + | |
- | {{ :laboratoare: | + | Algoritmul calculează costMinim(i, |
- | ===Implementare :=== | + | <note tip> |
- | <file cpp> | + | Observaţii: |
- | void insertionSort(int a[], int n) | + | * costMin(i,j,0) = costMuchie(i,j) (dacă există muchie de la i la j) sau infinit(altfel); |
- | { | + | * costMin(i,j,N) = drumul de cost minim de la i la j. |
- | int i, j, aux; | + | |
- | for (i = 1; i < n; i++) | + | |
- | { | + | |
- | j = i; | + | |
- | while (j > 0 && a[j - 1] > a[j]) | + | |
- | { //cautam pozitia pe care sa mutam a[i] | + | |
- | aux = a[j]; // | + | |
- | a[j] = a[j - 1]; | + | |
- | a[--j] = aux; | + | |
- | } | + | |
- | } | + | |
- | } | + | |
- | </ | + | |
- | ====3.4 Merge sort==== | + | </ |
- | * timp mediu: O(N log N) | + | Paşii algoritmului Floyd-Warshall: |
- | * timp la limită: O(N log N) | + | |
- | * memorie: O(N) | + | |
- | * Stabil: DA | + | |
- | ===Descriere :=== | + | < |
- | În cazul sortării prin interclasare, | + | 1. Declarăm matricile: |
- | din acelaşi vector. | + | dist, matrice N x N şi o iniţializăm dist[i][j] |
- | Sortarea prin interclasare utilizează metoda **Divide et Impera**: | + | 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] | ||
+ | 3. Pentru fiecare pereche (u,v) a.i. există muchie de la u la v | ||
+ | 1. dist[u][v] | ||
+ | 2. next[u][v] | ||
+ | //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 | ||
+ | </ | ||
- | *se împarte vectorul în secvenţe din ce în ce mai mici, astfel încât fiecare secvenţă să fie | + | Pentru obţinerea nodurilor |
- | ordonată la un moment dat şi interclasată cu o altă secvenţă | + | < |
- | *practic, interclasarea va începe când se ajunge la o secvenţă formată din două elemente. Aceasta, odată ordonată, se va interclasa cu o alta corespunzătoare(cu 2 elemente). Cele două secvenţe vor alcătui un subşir ordonat din vector mai mare(cu 4 elemente) care, la rândul lui, se va interclasa cu un subşir corespunzător(cu 4 elemente) ş.a.m.d. | + | funcţie afişareDrum(u, v) |
+ | 1. dacă u == v | ||
+ | 1. print(v); STOP | ||
+ | 2. print(u); | ||
+ | 3. afişareDrum(next[u][v], v); | ||
+ | </ | ||
- | ===Implementare :=== | + | ===== 5. Observaţii finale |
- | <file cpp> | + | <note tip> |
- | void mergeSort(int a[],int st, int m, int dr) | + | Cei 3 algoritmi funcţionează bine atunci când **toate muchiile** au **cost pozitiv**. |
- | { | + | </note> |
- | int b[100]; | + | <note warning> |
- | int i, j, k; | + | Drumul de cost minim **NU** este bine definit atunci când există **cicluri cu cost negativ**. |
- | i = 0; j = st; | + | * putem ajunge de la un nod la acelaşi nod, folosind acelaşi ciclu de oricâte ori => costMinim |
- | // copiem prima jumatate a vectorului a in b | + | * în aceste cazuri, nu putem pune problema găsirii drumurilor de cost minim. |
- | while (j <= m) | + | |
- | b[i++] | + | |
- | 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++]; | + | |
- | | + | |
- | while (k < j) | + | |
- | | + | |
- | } | + | |
- | void merge(int a[],int st, int dr) | + | |
- | { | + | |
- | if (st < dr) | + | |
- | { | + | |
- | int m = (st+dr)/2; | + | |
- | | + | |
- | merge(a, | + | |
- | mergeSort(a, | + | |
- | } | + | |
- | } | + | |
- | </ | + | |
- | ====3.5 Quick sort==== | + | </ |
+ | <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: | ||
- | | + | </ |
- | * timp la limită: O(N^2) | + | <note important> |
- | | + | Pentru algoritmul lui **Dijkstra**, |
- | * Stabil: NU | + | * Algoritmul se bazează pe ideea că, odată explorat un nod, drumul de cost minim până |
+ | * De aceea, algoritmul poate produce răspunsuri **greşite** în acest caz. | ||
- | ===Descriere :=== | + | </ |
- | Quick Sort este unul dintre cei mai rapizi | + | <note tip>În schimb, algoritmii **Bellman-Ford** |
+ | </ | ||
- | Algoritmul se bazează pe următorii paşi: | + | ===== 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 | ||
+ | - 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. | ||
- | {{ : | + | ====6.1. Exerciții - schelet de laborator==== |
+ | Pentru acest laborator puteți descărca scheletul de cod de [[http:// | ||
- | ===Implementare :=== | + | === Linux=== |
- | <file cpp> | + | Puteti folosi utilitarul '' |
- | 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 ===== | + | * '' |
+ | * '' | ||
- | 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 de **comparaţii** pentru algoritmii A şi B. Comparaţi rezultatele pentru un vector de întregi de lungime n = 20. | + | Pentru compilare folositi comanda '' |
- | E1. Implementaţi un algoritm(dintre Bubble, Insertion şi Selection) pentru sortarea unui vector cu n cuvinte de maxim 4 litere fiecare. | ||
- | 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, | + | ===Extra=== |
- | E3. Se dă un vector | + | - 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. | ||
- | <note tip>Este uşor să verificăm dacă două elemente sunt în ordine atunci când elementele au o structură simplă. Dacă avem o structură mai complicată, | ||
- | Puteţi utiliza următorul model pentru exerciţiile propuse: {{ :laboratoare:scheletsortare.zip |}} | + | ===== 7.Referințe ====== |
+ | - [[https:// | ||
+ | - [[https:// | ||
+ | - [[http:// | ||
+ | - [[https:// | ||