Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

--- laboratoare:laborator-13 [2017/02/20 00:29]
mihai.iacov [1.2 Greedy vs. Dijkstra]
+++ laboratoare:laborator-13 [2017/02/20 01:13]
mihai.iacov [2 Exemple]
@@ Linia 79: / Linia 79: @@
-=====2 Exemple=====
+=====2. Exemple=====
+====Problema taxiului====
+Presupunem următoarul caz:
+ *într-un oraş, oricare două străzi sunt **paralele** sau **perpendiculare** între ele;
+ *orice zonă mărginită de străzi are formă pătrată de latură = Lat(metri), iar pe colţurile **pătratului** sunt **intersecţii**;
+ *unele intersecţii sunt **blocate** şi ştim care sunt acestea
+ *se dau intersecţiile S şi D
+===Cerinţa===
+Dacă putem reduce orice intersecţie la un **punct**, găsiţi drumul cel mai scurt pe care poate merge un taxi din S în D(fără a trece prin intersecţiile blocate)
+===Rezolvare===
+ *Putem reprezenta intersecţiile cu o matrice.
+ *Ne putem deplasa doar pe **orizontală** sau pe **verticală**, deci, în cel mai bun caz, lungimea drumului minim de la un punct oarecare N la D poate fi exprimată in funcţie de coordonatele intersecţiilor
+ *Fie (Nx, Ny) = poziţia lui N, fie (Dx, Dy) = poziţia lui D şi fie dMin(N, D) = lungimea drumului minim de la N la D.
+ *Atunci, **în cel mai bun caz**, **dMin(N, D) = |Nx - Dx| + |Ny - Dy|**
+ *Putem defini h(N) = dMin(N, D) ca funcţie euristică pentru acest caz

Structuri de Date și Algoritmi (seria 1AB)