Unelte utilizator

Unelte site


laboratoare:laborator-07

Aceasta e o versiune anterioară a paginii.


Laborator 07: Parcurgerea grafurilor

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)

 RIP protocol

2.Considerente teoretice

2.1 Costul unei muchii

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

Într-un graf, orice drum este definit de o succesiune de muchii (cu proprietatea că, pentru oricare două muchii consecutive din succesiune, nodul destinaţie/de sosire al primei muchii este acelaşi cu nodul sursa/de plecare al celei de-a doua muchii).

Costul unui drum va fi definit ca suma costurilor muchiilor ce compun acel drum.

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.

Pot exista mai multe drumuri de cost minim de la S la D.

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), costul drumului din arbore de la rădăcina S la D este drum de cost minim(de la S la D) în graf.

3.1 Algoritmul lui Dijkstra

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, urmând să îl explorăm(să îi evaluăm vecinii), iar acel candidat va rămâne în arbore;
  • la fiecare explorare(evaluare a vecinilor), dacă găsim o nouă estimare de cost mai bună decât cea precedentă, folosim, mai departe, noua estimare. Dacă dorim să ţinem evidenţa muchiilor folosite, actualizăm şi nodul părinte al vecinului respectiv.

Diferenţa apare, în algoritmul lui Dijkstra, la funcţia folosită pentru estimarea costurilor, atunci când evaluăm vecinii unui nod:

  • Dacă C este nodul curent(pe care îl explorăm), atunci:
  • 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).
Construind astfel algoritmul, este garantat că, în momentul în care explorăm un nod(C), estimarea pentru costul drumului S-C este chiar costul minim.

Paşii algoritmului lui Dijkstra:

1. Declarăm două mulţimi:
	mulţimea nodurilor neexplorate(MN), iniţial MN = V(includem toate nodurile);
	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), 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)
	 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

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.1 Algoritmul Floyd-Warshall

5.Exiciții laborator

6.Referințe

laboratoare/laborator-07.1491052833.txt.gz · Ultima modificare: 2017/04/01 16:20 de către mihai.iacov