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 cost în aşa fel încât primul candidat din coadă să fie cel mai bun candidat.

1.2 Greedy vs. Dijkstra

Greedy

funcţia de cost

posibilul cost din punctul curent până în punctul final

Dijkstra

funcţia de cost

costul din punctul iniţial până în punctul curent

f = g + h

laboratoare/laborator-13.1487532235.txt.gz · Ultima modificare: 2017/02/19 21:23 de către mihai.iacov