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ă

Ambele părți revizuirea anterioară Versiuni anterioare
Urmatoarea versiune Ambele părți următoarea reviziune
laboratoare:laborator-13 [2017/02/19 23:30]
mihai.iacov [1.2 Greedy vs. Dijkstra]
laboratoare:laborator-13 [2017/02/20 00:29]
mihai.iacov [1.2 Greedy vs. Dijkstra]
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.  *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===
 +
 + *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=====
  
-f = g + h 
laboratoare/laborator-13.txt · Ultima modificare: 2017/05/15 08:29 de către mihai.iacov