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-13 [2017/02/20 00:29] mihai.iacov [1.2 Greedy vs. Dijkstra] |
laboratoare:laborator-13 [2017/05/15 08:29] mihai.iacov [1.1 Noţiuni introductive] |
||
---|---|---|---|
Linia 12: | Linia 12: | ||
| | ||
- | *În multe cazuri, | + | *În multe cazuri, |
| | ||
Linia 79: | Linia 79: | ||
- | =====2 Exemple===== | + | =====2. Exemple===== |
+ | ====Problema taxiului==== | ||
+ | |||
+ | Presupunem următoarul caz: | ||
+ | | ||
+ | | ||
+ | | ||
+ | *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=== | ||
+ | | ||
+ | *Ne putem deplasa doar pe **orizontală** sau pe **verticală**, | ||
+ | *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. | ||
+ | | ||
+ | |