Unelte utilizator

Unelte site


laboratoare:laborator-13

Diferențe

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

Link către această vizualizare comparativă

Both sides previous revision Versiuni anterioare
Urmatoarea versiune
Versiuni anterioare
laboratoare:laborator-13 [2017/02/19 22:29]
mihai.iacov [1.2 Greedy vs. Dijkstra]
laboratoare:laborator-13 [2017/05/15 05:29]
mihai.iacov [1.1 Noţiuni introductive]
Linia 12: Linia 12:
  
  ​*Trebuie să atribuim un "​**potenţial de rezultat**"​ fiecărui candidat, adică să găsim o metodă cu care să decidem dacă un candidat prezintă mai mult interes decât altul, dacă avem aşteptări mai mari de a găsi rezultatul dorit alegând acest candidat.  ​*Trebuie să atribuim un "​**potenţial de rezultat**"​ fiecărui candidat, adică să găsim o metodă cu care să decidem dacă un candidat prezintă mai mult interes decât altul, dacă avem aşteptări mai mari de a găsi rezultatul dorit alegând acest candidat.
- *În multe cazuri, ​funcţia de "​**cost potenţial**"​ ne ajută să descriem **potenţialul de rezultat**. Cu cât este mai mare costul la care ne aşteptăm de la un candidat, cu atât este mai mic  potenţialul lui de a ne duce la rezultatul căutat. Cu alte cuvinte, putem spune că **cel mai bun** candidat este **cel mai puţin costisitor** candidat.+ *În multe cazuri, ​este mai ușor să măsurăm cât de "​rău"​ este un candidat. Funcţia de "​**cost potenţial**"​ ne ajută să descriem **potenţialul de rezultat**. Cu cât este mai mare costul la care ne aşteptăm de la un candidat, cu atât este mai mic  potenţialul lui de a ne duce la rezultatul căutat. Cu alte cuvinte, putem spune că **cel mai bun** candidat este **cel mai puţin costisitor** candidat.
  ​*După ce definim o funcţie de acest fel, putem introduce candidaţii într-o coadă prioritară(**priority queue**) în funcţie de costul aşteptat în aşa fel încât **primul** candidat din coadă să fie **cel mai bun** candidat.  ​*După ce definim o funcţie de acest fel, putem introduce candidaţii într-o coadă prioritară(**priority queue**) în funcţie de costul aşteptat în aşa fel încât **primul** candidat din coadă să fie **cel mai bun** candidat.
  
Linia 79: Linia 79:
  
  
-=====2 Exemple=====+=====2Exemple=====
  
 +====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
laboratoare/laborator-13.txt · Ultima modificare: 2017/05/15 05:29 de către mihai.iacov