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 Ultima versiune Ambele părți următoarea reviziune | ||
laboratoare:laborator-13 [2017/02/15 21:18] florina_elena.barbu |
laboratoare:laborator-13 [2017/02/20 01:13] mihai.iacov [2 Exemple] |
||
---|---|---|---|
Linia 1: | Linia 1: | ||
- | ====== Laborator 13: TODO ====== | + | ====== Laborator 13: Best-first search și A* ====== |
- | TODOD | + | =====1. Introducere - Best-First Search===== |
+ | ====1.1 Noţiuni introductive==== | ||
+ | |||
+ | ===Definiţie BFS(Best First)=== | ||
+ | |||
+ | În sensul cel mai general, putem spune că un algoritm de căutare este de tipul Best-First dacă păstrează o evidenţă cu **candidaţii** şi alege să verifice mereu candidaţii cu potenţial mai mare înainte de a-i verifica pe cei cu potenţial mai mic(cu alte cuvinte, **verifică întâi candidatul cel mai bun - cu cel mai mare potenţial**). | ||
+ | |||
+ | ===Cum definim potenţialul? | ||
+ | |||
+ | | ||
+ | *În multe cazuri, funcţia de " | ||
+ | | ||
+ | |||
+ | ====1.2 Greedy vs. Dijkstra==== | ||
+ | |||
+ | Folosind noţiunile de mai sus, încercăm să identificăm funcţiile de cost potenţial pentru următoarea problemă: găsirea unui drum de cost minim de la un nod sursă(S) la un nod destinaţie(D) într-un graf. | ||
+ | |||
+ | | ||
+ | *Un candidat face parte din soluţie dacă drumul căutat trece prin el | ||
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | ===Greedy=== | ||
+ | |||
+ | Definim funcţia de **cost potenţial** h(N) = posibilul cost din nodul curent(C), prin nodul vecin(N), până la nodul destinaţie(D) | ||
+ | |||
+ | Metoda Greedy construieşte soluţia alegând mereu **optimul local**, cu alte cuvinte | ||
+ | *h(C) = 0, pentru că deja am inclus nodul C în soluţia parţială | ||
+ | *h(N) = costul muchiei (C,N), pentru orice nod N care **nu este deja** în soluţia parţială | ||
+ | |||
+ | ===Dijkstra=== | ||
+ | |||
+ | Definim funcţia de **cost potenţial** g(N) = costul minim al drumului din punctul iniţial(S) până în nodul N | ||
+ | |||
+ | <note important> | ||
+ | |||
+ | ===Observaţii=== | ||
+ | |||
+ | *În general, nu este **necesar** şi nici **suficient** ca funcţia de cost potenţial a unui nod să fie 0 pentru ca acel nod să facă parte din soluţia finală. | ||
+ | | ||
+ | *La algoritmul lui Dijkstra, în afară de nodurile S şi D, celelalte noduri au cost potenţial nenul(excepţie dacă există muchii de cost 0). | ||
+ | |||
+ | <note warning> | ||
+ | |||
+ | ===Performanţe=== | ||
+ | |||
+ | | ||
+ | | ||
+ | |||
+ | ===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===== | ||
+ | |||
+ | ====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. | ||
+ | | ||
+ | |