Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

--- laboratoare:laborator-13 [2017/02/15 21:18]
florina_elena.barbu
+++ laboratoare:laborator-13 [2017/02/19 22:31]
mihai.iacov
@@ 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?===
+ *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

Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Diferențe

Unelte pagină