Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
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: | ||
| | ||
+ | ===Propunere=== | ||
+ | |||
+ | | ||
+ | | ||
+ | |||
+ | ====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ă**, | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | ===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**, | ||
+ | |||
+ | |||
+ | =====2 Exemple===== | ||
- | f = g + h |