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 23:30]
mihai.iacov [1.2 Greedy vs. Dijkstra]
@@ 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===
+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.
+f = g + h

Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Diferențe

Unelte pagină