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 09:09]
mihai.iacov [1.1 Greedy vs. Dijkstra]
laboratoare:laborator-13 [2017/05/15 05:29] (curent)
mihai.iacov [1.1 Noţiuni introductive]
Linia 1: Linia 1:
-====== Laborator 13: A* ======+====== Laborator 13: Best-first search și A* ======
  
 =====1. Introducere - Best-First Search===== =====1. Introducere - Best-First Search=====
  
-====1.1 Greedy vs. Dijkstra====+====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?​=== 
 + 
 + ​*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, 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. 
 + 
 +====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. 
 + 
 + ​*Candidaţii = nodurile din graf care urmează să fie incluse în soluţie 
 + *Un candidat face parte din soluţie dacă drumul căutat trece prin el 
 + ​*Nodurile S şi D au **costul potenţial = 0**, dar considerăm nodul D "​nedescoperit"​ iniţial şi plecăm din nodul S 
 + ​*Toate celelalte noduri au iniţial **costul potenţial infinit** 
 + ​*Presupunem că ne aflăm la nodul curent(C) extras de la începutul cozii şi evaluăm nodurile vecine ale acestuia
  
 ===Greedy=== ===Greedy===
  
-funcţia de "cost" ​= posibilul cost din punctul ​curent până ​în punctul final+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=== ===Dijkstra===
  
-funcţia de "cost" ​= costul din punctul iniţial până în punctul ​curent+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>​Algoritmul lui Dijkstra actualizează costul minim al drumului de la S la fiecare punct pe măsură ce explorează graful. Presupunem că actualizăm,​ în acelaşi timp, şi **costul potenţial**.</​note>​ 
 + 
 +===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ă. 
 + ​*Metoda Greedy poate duce la funcţia g(N) = 0 pentru noduri care par bune pe moment, dar nu se poate ajunge la D fără revenirea în nodul C(căutarea unui nou optim local după ce acesta a eşuat complet). 
 + *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>​Costul potenţial are rol doar în etapa de explorare a grafului. Pentru extragerea nodurilor ce formează drumul de cost minim, **nu** interpretăm costul potenţial. Este mult mai uşor să reţinem, într-un **vector de părinţi**,​ nodul "curent" din care am ajuns la nodul "​următor",​ în momentul în care actualizăm costul potenţial al nodului următor.</​note>​ 
 + 
 +===Performanţe=== 
 + 
 + ​*Metoda Greedy obţine **foarte repede** un rezultat(un drum de la S la D), dar, în multe cazuri, acesta **nu este cel mai scurt**(de cost minim). 
 + ​*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===== 
 + 
 +====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)
  
-+ h+===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.1487495387.txt.gz · Ultima modificare: 2017/02/19 09:09 de către mihai.iacov