Algoritmi exaci i algoritmi euristiciProiect realizat deEleva cls.a 11-a BMirela Grosu

Definiii Un algoritm este exact atunci cand el gasete solutiile optime ale problemelor pentru rezolvarea crora a fost conceput i necesit demonstraie matematic Un algoritm este euristic atunci cand el gsete slouii bune,dar nu neaprat optime.Nu necesit demonstraie matematic

Algoritmii exaci sunt bazai pe metoda trierii,deoarece n procesul examinrii soluiilor, neaprat va fi gsit i soluia optim Algoritmii exaci sau euristici bazai pe celelalte tehnici de programare, natura soluiilor permit trierea tuturor soluiilor posibile

Problema drumului minim Se consider n orae legate printr-o reeade drumuri.Cunoscnd distaneledintre orae vecine,determinai cel mai scurt drum din oraul a n oraul b

Scriem datele iniiale a problemei cu ajutorul matricei cu n linii si n coloane,denumit matricea distanelorPrin definiie d=0, i=1,2,...,n.

Gsirea drumului minim prin metoda trieriiDrumul minim ce leag oraele a=1,b=6 are lungimea 7 i include localitile 1,3,5,6.X=(a,i,j,...,k,b), i,j,...k- q orae

Metoda reluriiUtilizm aceast metod pentru a reduce din calculAceasta metod are la baz regula intuitiv, la fiecare pas vom examina vecinii nevizitai are se afl ct mai aproape de orau curentDrumul n construcie ia forma unui vector X=(a,x2,...,xk-1,xk,..,xb)

Pentru a sistematiza calculele,vom memora vecinii nevizitai ai oraului n mulimea A1A1=(2,3,4)A2=(2)A3=(1,4,5)A4=(3,5,6)A5=(6,3,4)A6=(5)