Unelte utilizator

Unelte site


laboratoare:laborator-13

Aceasta e o versiune anterioară a paginii.


Laborator 13: Best-first search și A*

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

funcţia de cost potenţial g(N) = costul minim al drumului din punctul iniţial până în nodul curent(N)

f = g + h

laboratoare/laborator-13.1487536266.txt.gz · Ultima modificare: 2017/02/19 20:31 de către mihai.iacov