Metode generale de elaborare a algoritmilor (iii)

METODE GENERALE DE ELABORARE A ALGORITMILOR (III)

Continutul lucrarii

In lucrare sunt prezentate metoda programarii dinamice si metodele euristice.

2. Consideratii teoretice

2.1. Metoda programarii dinamice

Metoda programarii dinamice se aplica pentru rezolvarea problemelor de optim, pentru care solutia este rezultatul unui sir de decizii secventiale, dependente de cele luate anterior si care indeplinesc principiul optimalitatii.

Principiul optimalitatii consta in urmatoarele:

Fie starile s₀, s₁, , s_n, in care s₀ este starea initiala si s_n este starea finala, obtinute prin deciziile d₁, d₂, , d_n (fig. 2.1.1).

Daca d_i, d_i+1, , d_j (1 i < j  n) este un sir optim de decizii care transforma starea s_i-1 in starea s_j, trecand prin starile intermediare s_i, s_i+1, , s_j-1 si daca pentru oricare k [i, j-1] rezulta ca d_i, d_i+1, , d_k si d_k+1 d_k+2, , d_j sunt ambele siruri optime de decizii de trecere din starea s_i-1 in starea s_k, respectiv din starea s_k in starea s_i-1, atunci este satisfacut principiul optimalitatii.

Aplicarea metodei programarii dinamice se face astfel:

se verifica principiul optimalitatii;

se scriu relatiile de recurenta obtinute din regulile de trecere dintr-o stare in alta si se rezolva.

Drept exemplu se ia inmultirea optima a unui sir de matrici.

R=A₁*A₂**A_n

in care A_i (i=1,n) este de dimensiunile d_i*d_i+1. Matricea rezultat R va fi de dimensiunile d_i*d_n+1.

Se stie ca la inmultirea matricelor A_i si A_i+1 se efectueaza d_i*d_i+1*d_i+2 operatii de inmultire. Daca matricele au dimensiuni diferite, numarul operatiilor de inmultire necesare obtinerii matricei rezultat R depinde de ordinea efectuarii produselor a cate doua matrice. Se cere gasirea ordinii de asociere pentru care numarul inmultirilor sa fie minim.

Rezolvarea acestei probleme se va face astfel:

Fie C_ij numarul minim de inmultiri de elemente pentru calculul produsului A_i*A_i+1**A_j pentru 1 i < j  n.

Se observa ca:

a)     C_ii=0

b)     C_i,i+1= d_i*d_i+1*d_i+2

c)      C_1n este valoarea minima cautata.

d)     este verificat principiul optimalitatii.

C_ij = min asocierile fiind de forma (A_i* A_i+1* . * A_k) * (A_k+1* A_k+2* . * A_j).

Se calculeaza valorile C_{i, i+d} pentru fiecare nivel d, pana se ajunge la C_1,n. Pentru a construi arborele binar care va descrie ordinea efectuarii operatiilor, se va retine la fiecare pas indicele k care realizeaza minimul, adica modul de asociere a matricelor. Varfurile arborelui vor contine limitele subsirului de matrice care se asociaza; radacina va contine (1,n), iar un subarbore care contine in radacina (i, j) va avea descendenti pe (i, k) si (k+1, j), unde k este valoarea pentru care se realizeaza optimul cerut.

In continuare este prezentat programul comentat de rezolvare a acestei probleme.

#include <stdio.h>

#include <conio.h>

#include <alloc.h>

#define nmax 10

typedef struct tip_nod TIP_NOD;

/*Inmultirea optima a unui sir de matrici A1*A2**An */

/* de dimensiuni d1*d2,d2*d3,,dn*d(n+1) */

void prod_matr(int n,long c[nmax][nmax],int d[nmax+1])

;

};

c[i][j]=min;

c[j][i]=poz;

}

}

Analiza: Documente specifice operatiilor cu numerar Eseu: Forma de contabilitate utilizata la o societate comerciala

TIP_NOD *constr_arbore(TIP_NOD *p,int i,int j,long c[nmax][nmax])

else ;

return p;

}

void postordine(TIP_NOD *p,int nivel)

}

void main(void)

;

prod_matr(n,c,d);

/* Matricea c rezultata in urma calculelor */

printf('nMATRICEA Cn');

for(i=1;i<=n;i++)

printf('nNR.MINIM DE INMULTIRI = %ld',c[1][n]);

getch();

rad=0;

rad=constr_arbore(rad,1,n,c);

printf('nARBORELE IN POSTORDINEn');

postordine(rad,0);

getch();

}

Metode euristice

Prin algoritm euristic se va intelege un algoritm care furnizeaza o solutie aproximativa, nu neaparat optimala, dar care poate fi implementata usor si da rezultate in timp util, de ordin polinomial.

Metodele euristice se aplica pentru rezolvarea unor probleme, la care nu se stie daca admit optim si care accepta drept rezultate nu tocmai optimul.

Una din idei, este descompunerea procesului de determinare a solutiei in mai multe procese succesive, carora li se cauta solutia optimala. Idea nu conduce la obtinerea in final in mod sigur a unei solutii optime, intrucat optimizarea locala nu implica in general optimizarea globala.

In problemele practice se pot cauta mai multe solutii aproximative, din care sa se aleaga cea mai buna.

Drept exemplu se prezinta problema comis - voiajorului: Se da un graf neorientat G =(X, ) in care toate nodurile sunt unite intre ele printr-o muchie, careia i se asociaza un cost strict pozitiv. Se cere determinarea unui ciclu, care sa inceapa dintr-un nod i, sa treaca exact o data prin toate nodurile si sa se intoarca in nodul initial. Se cere ca ciclul gasit sa aiba un cost minim.

Solutia optimala a problemei se gaseste intr-un timp de ordin exponential prin metoda backtracking.

Algoritmul euristic prezentat mai jos bazat pe metoda Greedy necesita un timp polinomial. Rezolvarea consta in urmatoarele:

Daca (v₁, v₂, , v_k) este calea deja construita, atunci:

daca (v₁, v₂, , v_k) = = X, se adauga muchia (v_k, v₁) si ciclul este incheiat;

daca (v₁, v₂, , v_k)  X, se adauga muchia care leaga v_k de un varf apartinand lui x, dar neinclus in cale.

Pentru ca ciclul este o cale inchisa, putem considera ca punct de plecare oricare nod. De aceea se pot alege niste noduri de start, se determina pentru fiecare ciclul corespunzator dupa strategia descrisa si se retine ciclul de cost minim dintre ele.

In continuare este prezentat programul corespunzator.

#include <stdio.h>

#include <conio.h>

#define nmax 10

/*Problema comis_voiajorului */

void comis_voiajor(int n,int c[nmax][nmax],

int i,int ciclu[nmax+1],int *cost)

/* n este nr.nodurilor;c este matricea costurilor;

i este nodul de start;ciclu contine nodurile din ciclu;

cost este costul ciclului */

*cost=*cost+costmin;

ciclu[k+1]=vmin;

p[vmin]=1;

v=vmin;

}

ciclu[n+1]=i;

*cost=*cost+c[v][i];

}

void main(void)

else break;

}

}

i=1;

comis_voiajor(n,c,i,ciclu,&cost_ciclu);

printf('nCOSTUL CICLULUI =%dn',cost_ciclu);

printf('nCICLUL=');

for(i=1;i<=n+1;i++)

printf('%3d',ciclu[i]);

getch();

}

Mersul lucrarii

Se vor rezolva prin metoda programarii dinamice urmatoarele probleme:

Determinarea cailor de cost minim intre oricare doua varfuri ale unui graf orientat prin algoritmul lui Floyd. (problema 3.2 din lucrarea 7).

La un concurs de tir, tinta este alcatuita din cercuri concentrice, numerotate din exterior spre interior. Fiecarui sector determinat de doua cercuri succesive ii este atasata o valoare strict pozitiva, reprezentand punctajul primit de concurent in cazul lovirii acestui sector.

Sa se determine numarul minim de lovituri pe care trebuie sa le execute un concurent pentru a obtine exact k puncte.

Se dau doua numere naturale A si B si un vector v care contine n numere naturale. Sa se determine daca se poate trece din A in B, stiind ca singurele operatii permise sunt:

a)     Adunarea la A a oricate numere din vectorul v;

b)     Scaderea din A a oricate numere din vectorul v;

Fiecare numar poate fi adunat, respectiv scazut de mai multe ori.

Daca raspunsul la intrebare este afirmativ, se cere numarul minim de operatii prin care se poate trece din A in B.

Se dau n segmente aflate pe o dreapta. Sa se determine cardinalul maxim al unei submultimi de segmente care are proprietatile:

a)     oricare doua numere din submultime nu se intersecteaza;

b)     submultimea contine primul element.

Pe o creanga de mar, se afla n mere, fiecare caracterizat prin distanta h_i in cm de la pamant pana la pozitia in care se afla si prin greutatea sa g_i in grame. Un culegator doreste sa culeaga o cantitate exprimata in grame cat mai mare de mere. Dupa ce este cules un mar intreaga creanga devine mai usoara si se ridica in sus cu x cm. Culegatorul ajunge doar la merele aflate la o inaltime mai mica sau egala cu d cm. Sa se determine greutatea maxima de mere care poate fi culeasa si ordinea in care sunt culese merele.

Se citesc: n, x, d si (g_i, h_i) i=1n.

Sa se rezolve prin metode euristice urmatoarele probleme:

Sa se gaseasca maximul unei functii f(x) in intervalul [a, b].

Se da un graf neorientat cu n noduri. Se cere sa se determine numarul minim de culori necesare pentru a colora nodurile grafului dat, astfel incat doua varfuri legate printr-o muchie sa fie colorate cu culori diferite.

Se da un graf neorientat cu n noduri. Se cere sa se determine o submultime maxima de noduri cu proprietatea ca oricare doua noduri din ea nu sunt legate printr-o muchie.