Diferențe

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

Link către această vizualizare comparativă

--- laboratoare:laborator-13 [2017/02/19 23:30]
mihai.iacov [1.2 Greedy vs. Dijkstra]
+++ laboratoare:laborator-13 [2017/05/15 08:29] (curent)
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.
- *Î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.
@@ Linia 52: / Linia 52: @@
  *Algoritmul lui Dijkstra cu coadă prioritară are nevoie de **mai mult timp** pentru a obţine un rezultat, dar este **garantat** că, în momentul în care descoperă nodul D, a **găsit cel mai scurt drum** şi algoritmul se poate opri.
+===Propunere===
-f = g + h
+ *Putem găsi o cale de mijloc care să fie mai rapidă decât algoritmul lui Dijkstra şi care să ducă la soluţia dorită?
+ *Când putem defini o funcţie f(N) care să fie o combinaţie a funcţiilor g(N) şi h(N)) care să ducă la un algoritm mai bun?
+====1.3 Algoritmul A*====
+Algoritmul A* este definit, în sens general, ca fiind un algoritm de căutare de tip BFS(Best-First) ce foloseşte funcţia de **cost potenţial**
+	f(N) = g(N) + h(N), unde
+	g(N) = costul minim pentru un drum de la S la N
+	h(N) = estimarea pentru costului minim pentru un drum de la N la D
+Definirea funcţiei g nu ridică probleme(putem folosi aceeaşi funcţie ca la algoritmul lui Dijkstra), dar, din punct de vedere al funcţiei h, numită funcţie **euristică**, distingem câteva cazuri:
+ *dacă funcţia h(N) = 0 peste tot, algoritmul coincide cu Dijkstra cu coadă prioritară -> soluţie optimă garantată, dar lent
+ *dacă funcţia h(N) < costul minim al drumului de la N la D, oricare ar fi N -> soluţie optimă garantată, mai rapid
+ *dacă funcţia **h(N) = costul minim al drumului de la N la D**, oricare ar fi N -> **cel mai rapid algoritm cu soluţia optimă garantată**
+ *dacă funcţia h(N) > costul minim al drumului de la N la D(**chiar şi pentru câteva** noduri N) -> optimul **nu** e garantat, dar e şi mai rapid
+ *dacă funcţia h(N) domină, atunci g(N) nu mai are efect, iar algoritmul A* devine Greedy Best-First Search.
+===Concluzie===
+O estimare iniţială bună creşte performanţa algoritmului şi păstrează rezultatul optim.
+<note tip>Este uşor să alegem o funcţie euristică bună atunci când avem **informaţii suplimentare** despre graf. Dacă ştim că există nişte **proprietăţi particulare**, ne putem folosi de ele.</note>
+=====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)

Unelte utilizator

Unelte site

Diferențe

Unelte pagină