Structuri de Date și Algoritmi (seria 1AB)

Această pagină poate fi doar citită. Poți vedea sursa, dar nu poți modifica pagina. Consultă administratorul dacă ești de părere că ceva este în neregulă.
====== Laborator 13: Best-first search și A* ======

=====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?===

 *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===

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>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)

===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

Unelte pagină
