INGINERIE ELECTRICĂ ȘI ELECTRONICĂ Str. Științei Nr. 2, cod poștal 800146, Galați, România, tel/fax: +0236 4 70 905, e-mail: aciee@ugal.ro, web:… [609454]

UNIVERSITATEA „DUNĂREA DE JOS” DIN GALAȚI
FACULTATEA DE AUTOMATICĂ, CALCULATOARE,
INGINERIE ELECTRICĂ ȘI ELECTRONICĂ

Str. Științei Nr. 2, cod poștal 800146, Galați, România, tel/fax: +0236 4 70 905, e-mail: [anonimizat], web: www.aciee.ugal.ro
SPECIALIZAREA: INGINERIA SISTEMELOR

IMPLEMENTAREA UNEI PROBLEME DE
CONDUCERE OPTIMALĂ FOLOSIND
PROGRAMAREA DINAMICĂ

Coordonator științific,
Prof . Dr. Ing. Viorel MÎNZU
Absolvent: [anonimizat] 2 019

CUPRINS
Introducere…………………………………………………………………………………………………… ………………………………….. 1
Capitolul 1. Programarea dinamică…….. ……………………………………….. ……………………………………………..2

INTRODUCERE

1 CAPITOLUL 1 . PROGRAMAREA DINAMI CĂ
Programarea dinamică este folosită împreună cu algoritmii divide și stăpânește
pentru rezolvarea problemelor de control optimal, combinând soluțiile unor subprobleme.
Acești algorit mi împart problema în mai multe subprobleme individuale și le rezolvă pe rând.
Soluțiile sunt apoi combinate pentru rezolvarea problemei in ițiale. Aceast ă metodă este
pretabilă atunci când rezolvarea problemei întregi ar necesita mai multe calcule decât
soluționarea prin subprobleme.
De obicei, metoda programării dinamice este folosită în problemele de optimizare,
unde pot fi mai multe soluț ii posibile. În acest caz, trebuie găsită soluția a cărei valoare este
optimă (minimă sau maximă).
Rezolvarea problemei folosind programarea dinamică poate fi divizată în patru pași:
• Stabilirea structurii soluției optime;
• Determinarea iterativă a valoril or optime;
• Aflarea soluției prin metoda „bottom -up”;
• Definirea unei soluții în baza calculelor.
Pașii 1 -3 sunt folosiți atunci când se utilizează programarea dinamică, iar pasul 4 se
poate ignora dacă se dorește determinarea unei singure soluții optime. În aplicarea pas ului
4, se folosește informația obținută la pasul anterior, pentru a putea determina mai ușor
optimul.
1.1 Triangularea optimă a poligoanelor
Pentru o înțelegere mai bună a conceptului, am ales să abordez problema triangulării
optime a unui poligon convex folosind programarea dinamică.
Un poligon este o figură geometrică inchisă, ce are capătul inițial comun cu cel final,
și este formată dintr -o serie de drepte. În exemplul ales, vom lua în considerare un poligon
simplu, adică nu se intersec tează. Un poli gon este convex dacă, oricare ar fi o latură a sa, toate
vârfurile ce nu sunt situate pe latura respectivă se află pe aceeași parte a laturii considerate.
Reprezentarea poligoanelor convexe se face prin precizarea vârfurilor în sensul
acelor de ceasornic, adică 𝑃={𝑣0,𝑣1,…,𝑣𝑛−1}, de unde se deduce faptul că laturile
poligonului sunt 𝑣0𝑣1̅̅̅̅̅̅,𝑣1𝑣2̅̅̅̅̅̅,…,𝑣𝑛−1𝑣𝑛 ̅̅̅̅̅̅̅̅̅ , de unde rezultă că 𝑣𝑛=𝑣0.
Considerând două vârfuri neadiacente 𝑣𝑖 și 𝑣𝑗, dreapta 𝑣𝑖𝑣𝑗̅̅̅̅̅, se numește coardă a
poligonului. Triangularea poligonului este o mulțime M de coarde ce împart poligonul în
triunghiuri disjuncte. Un poligon convex cu n laturi, prin triangulare se obțin n-3 coarde și
secționează poligonul în n-2 triunghiuri.
1.1.1 Realizarea triangulării optime
Fie un poligon având n+1 vârfuri 𝑃={𝑣𝑜,𝑣1,…,𝑣𝑛} cu o triangulare optim ă T format
din triunghiuri ∆𝑣𝑜𝑣𝑘𝑣𝑛 pentru un k cu 1≤𝑘≤𝑛−1. Ponderea atribuită lui T este compusă
din ponderi le triunghiului ∆𝑣𝑜𝑣𝑘𝑣𝑛, și a triunghiurilor asociate triangulării celor două
subpoligoane {𝑣0,𝑣1,…,𝑣𝑘} și {𝑣𝑘,𝑣𝑘+1,…,𝑣𝑛}. Triangularea acestor subpoligoane trebuie

1 să fie optimă, deoarece, dacă pentru unul din s ubpoligoane se va obține o pondere mai mică,
nu s -ar mai respecta minimalitatea ponderii lui T.
Pondere triangulării optime o vom nota t[i, j], pentru 1≤𝑖<𝑗≤𝑛 și vom considera
că ponderea poligonului degenerat {𝑣𝑖−1,𝑣𝑖} este 0. Pasul următor este definirea recursivă
a lui 𝑡[𝑖,𝑗]=0 pentru 𝑖=1,2,…,𝑛. Dacă 𝑗−𝑖≥1, atunci poligonul {𝑣𝑖−1,𝑣𝑖,…,𝑣𝑗} are cel
puțin trei vârfuri. Pentru aceasta, trebuie să minimizăm suma dintre ponderea triunghiului
∆𝑣𝑖−1𝑣𝑘𝑣𝑗 și ponderile sub poligoanelor {𝑣0,𝑣1,…,𝑣𝑘} și {𝑣𝑘,𝑣𝑘+1,…,𝑣𝑛} în urma
triangulării. Astfel , se obține funcția recur sivă :

𝑡[𝑖,𝑗]={0, 𝑑𝑎𝑐ă 𝑖=𝑗
min
𝑖≤𝑘≤𝑗−1{ 𝑡[𝑖,𝑘]+𝑡[𝑘+𝑖,𝑗]+𝜔(∆𝑣𝑖−1𝑣𝑘𝑣𝑗)}, 𝑑𝑎𝑐ă 𝑖<𝑗

1.1.2 Problemă de triangulare optimă
Să se împartă un poligon convex în triunghiuri, prin coarde de lungime totală
minim ă. Se dau vârfuri le consec utive 𝑣𝑖,…,𝑣𝑘 cu 0≤𝑖<𝑘<𝑛 și 𝑣𝑗(𝑖<𝑗<𝑘) vârful
triunghiului ce conține laturile 𝑣𝑖𝑣𝑘, și costul de triangulare fiind 𝑐𝑖𝑘.
Atunci :
𝑐𝑖𝑘=min
𝑖<𝑗<𝑘(𝜔(𝑖,𝑗,𝑘)+𝑐𝑖𝑗+𝑐𝑗𝑘), 𝑐𝑖,𝑖+1=0
Implementare în C++ :

1 double c[N][N];
2 unsigned v [N][N];
3 for (l = 2; l < N; ++l)
4 for (k = N – 1; I = k – l; i >= 0; –k; –i) {
5 c[i][k]=DBL_MAX;
6 for (j = k; –j > I;){
7 double m = w( i,j,k) + c[i][j] + c[j][k];
8 if (m < c[i][ k] {c[i][k] = m; v[i] [k] = j; }
9 }
10 }

1