METODE GENERALE DE ELABORARE A ALGORITMILOR (II)

METODE GENERALE DE ELABORARE A ALGORITMILOR (II)

1. Continutul lucrarii

În lucrare se prezinta esenta metodelor "Branch and Bound" (ramifica si margineste) si a metodei "Divide et Impera".

2. Consideratii teoretice

2.1. Metoda "Branch and Bound"

Metoda "Branch and Bound" este înrudita cu metoda backtracking, diferind ordinea de parcurgere a spatiului starilor si a modului de eliminare a subarborilor ce nu pot conduce la rezultat.

Metoda "Branch and Bound" se aplica urmatoarelor tipuri de probleme: Se cunoaste starea initiala s₀ si starea finala s_f (starea rezultat). Din starea s₀ se ajunge în starea s_f printr-o serie de decizii. Ne intereseaza ca numarul starilor intermediare sa fie minim.

Presupunem ca starile reprezinta nodurile unui graf, iar arcele indica faptul ca o decizie a transformat starea s_i în starea s_i+1. Se introduc restrictii ca sa nu existe mai multe noduri în graf cu aceeasi stare, deci graful sa nu fie infinit. Astfel graful se reduce la un arbore. Arborele se genereaza pâna la prima aparitie a nodului final.

Exista posibilitatea parcurgerii grafului în adâncime sau în latime, însa timpul de ajungere la rezultat este mare. O strategie superioara din punct de vedere al timpului de calcul se obt 444d38e ine alegând dintre descendentii vârfului curent pe cel mai aproape de starea finala. Pentru a putea aprecia departarea fata de starea finala, se va folosi o functie de cost c definita pe multimea vârfurilor din arbore. Având valorile acestei functii, vom alege dintre vârfurile descendente ale vârfului curent pe cel cu cost minim. O astfel de parcurgere a grafului se numeste "Least Cost" sau prescurtat "LC".

Functia c ideala pentru a masura distanta de la vârf la vârful final este:

rezultat;

daca x este vârf terminalvârful rezultat

daca x nu este vârf rezultat

Functia c definita mai sus nu este aplicabila, întrucât calculul ei presupune parcurgerea tuturor vârfurilor arborelui, de fapt urmarindu-se tocmai evitarea acestui lucru.

Se observa ca daca totusi functia c este calculata, atunci coborârea în arbore la vârful rezultat se face pe un drum deja format din vârfurile x ce au atasata o valoare c(x) egala cu c(radacina).

Neputând lucra cu functia c, atunci se defineste o aproximare a sa cu una din urmatoarele doua variante:

a)    nivelul vârfului x + distanta dintre starea curenta si starea finala;

b)   costul starii parinte + distanta dintre starea curenta si starea finala.

Nivelul este numarul deciziilor prin care s-a ajuns la configuratia curenta.

Stabilirea functiei "distanta" este specifica fiecarei probleme. De exemplu, în cazul jocului perspico (problema 3.1. din lucrare), distanta este numarul de placute care nu sunt la locul potrivit.

Functia care descrie metoda "Branch and Bound" este data mai jos. Lista L contine vârfurile care memoreaza configuratia starilor. Pentru vârful i luat în considerare se memoreaza tatal sau în vectorul TATA, permitând ca odata ajunsi în vârful rezultat sa se poata reface drumul de la radacina la vârful rezultat.

RAD este pointerul la vârful ce contine starea initiala.

TIP_NOD *RAD;

RAD=(TIP_NOD *)malloc(sizeof(TIP_NOD));

/* se depune configuratia initiala la adresa RAD */

void Branch_and_Bound()

else ;

if(ESTE_VIDA(L))

else i=ELEMENT(L);

Functiile apelate au urmatoarea semnificatie:

LISTAVIDĂ(L) - initializeaza lista L ca fiind vida;

ESTEVIDĂ(L) -- returneaza 1 daca lista L este vida sau 0 în caz contrar;

ELEMENT(L) -- este functia ce returneaza un element al listei care are cel mai mic cost , pentru a ne afla în cazul pacurgerii LC a arborelui starilor;

ADAUG(j, L) --- adauga nodul j la lista L. Din descrierea functiei se observa ca atunci când un vârf i din lista L devine vârf curent, sunt generati toti descendentii sai, acestia fiind pusi în lista L. Unul din acesti descendenti va deveni la rândul sau pe baza costului vârf curent, pâna când se ajunge la vârful rezultat (cel ce contine starea finala).

Metoda "Divide et Impera"

Metoda "Divide et Impera" consta în împartirea repetata a unei probleme în doua sau mai multe probleme de acelasi tip si apoi combinarea subproblemelor rezolvate, în final obtinându-se solutia problemei initiale.

Astfel, fie vectorul A =(a₁, a₂, ..., a_n), a carui elemente se prelucreaza. Metoda "Divide et Impera" este aplicabila daca pentru orice p, q, naturali, astfel încât exista un încât prelucrarea secventei se poate face prelucrând secventele si si apoi prin combinarea rezultatelor se obtine prelucrarea dorita.

Metoda "Divide et Impera" poate fi descrisa astfel:

void DIVIDE_IMPERA(int p,int q,rezultat:alfa)

/* p, q reprezinta indicii secventei care se prelucreaza;

alfa reprezinta rezultatul */

Apelul functiei "Divide et Impera" se face astfel:

DIVIDE_IMPERA(1, n, alfa);

Variabilele si functiile din functia divide_Impera au urmatoarele semnificatii:

eps - este lungimea maxima a unei secvente a_p, a_p+1, ...,a_q pentru care prelucrarea se poate face direct;

m - este indicele intermediar în care secventa a_p, a_p+1, ...,a_q este împartita în doua subsecvente de functia DIVIDE;

beta si gama - reprezinta rezultatele intermediare obtinute în urma prelucrarii subsecventelor (a_p, a_p+1, ...,a_m) si respectiv (a_m+1, a_m+2, ...,a_q);

alfa - reprezinta rezultatul combinarii rezultatelor intermediare beta si gama;

DIVIDE - împarte secventa (a_p, a_p+1, ...,a_q) în doua subsecvente (a_p, a_p+1, ...,a_m) si

(a_m+1, a_m+2, ...,a_q);

COMBINĂ - combina rezultatele beta si gama ale prelucrarii subsecventelor returnate de procedura DIVIDE, obtinând rezultatul alfa a prelucrarii secventei initiale.

Exemplu. Sortarea prin interclasare a unui vector de n elemente:

/*Program de sortare prin metoda divide et impera */

#include <stdio.h>

#include <conio.h>

#define nmax 100

int a[nmax]; /* vectorul de sortat */

void afisare(int n)

/* afisarea vectorului */

printf("\n");

}

void comb(int inf,int med,int sup)

else

k++;

}

for(l=i;l<=med;l++)

for(l=j;l<=sup;l++)

/* secventa intre inf si sup este sortata */

for(l=inf;l<=sup;l++) a[l]=b[l];

void divide_impera(int inf,int sup)

}

void main(void)

printf("\nVECTORUL NESORTAT\n");

afisare(n);

divide_impera(0,n-1);

printf("\nVECTORUL SORTAT\n");

afisare(n);

getch();

}

Mersul lucrarii

Se vor rezolva urmatoarele probleme prin metoda "Branch and Bound":

Jocul PERSPICO. 15 placute patrate sunt încadrate într-un cadru de dimensiune 4x4, o pozitie fiind libera. Orice placuta vecina cu aceasta pozitie libera poate fi mutata în locul ei. Cele 15 placute sunt numerotate de la 1 la 15. Se începe dintr-o stare initiala, care corespunde unei distributii oarecare a celor 15 placute si a locului liber în cele 16 pozitii posibile. Problema consta în a trece, folosind mutari posibile, din starea initiala în starea finala (fig. 3.1.1).

Exemplu de configuratie initiala Configuratie finala

Figura 3.1.

Exista urmatorul joc: pe o linie de cale ferata se afla n vagoane unul lânga altul, numerotate cu valori distincte din multimea 1...n. O macara poate lua k vagoane de pe linie si le poate aseza în partea dreapta, la sfârsitul sirului de vagoane, care apoi prin împingere ajung din nou unul lânga altul, în noua ordine creata dupa operatia respectiva.

Dându-se ordinea initiala a vagoanelor, se cere sa se determine (daca este posibil) numarul minim de operatii pe care trebuie sa le efectueze macaraua pentru ca în final vagoanele sa se afle în ordine crescatoare 1, 2, ..., n .

Pe malul unui râu se afla 2n bastinasi din care n sunt canibali. Acestia doresc sa traverseze râul utilizând o barca care poate transporta cel mult k persoane. Daca pe un mal sau în barca sunt mai multi canibali decât ceilalti, atunci canibalii îi vor mânca. Cum vor reusi sa treaca toti pe malul opus fara sa se manânce si fara a apela la alte persoane.

Pe un pod se afla n capre care vin dintr-un sens, cu n capre care vin din sens opus. Acestea nu se pot ocoli, însa fiecare capra poate sari peste o singura capra din grupul opus si desigur poate avansa daca în fata sa este un spatiu liber.

Cum reusesc aceste capre sa traverseze podul doar prin cele doua miscari posibile (avans si saritura).

Se vor rezolva urmatoarele probleme prin metoda "Divide et Impera":

Fiind dat un vector ce contine elemente de tip întreg ordonate crescator, sa se scrie o functie de cautare a unui element dat în vector, returnându-se pozitia sa.

Problema turnurilor din Hanoi. Se dau trei tije. Pe una dintre ele sunt asezate n discuri de marimi diferite, discurile de diametre mai mici fiind asezate peste discurile cu diametre mai mari. Se cere sa se mute aceste discuri pe o alta tija, utilizând tija a treia ca intermediar, cu conditia mutarii a câte unui singur disc si fara a pune un disc de diametru mai mare peste unul cu diametru mai mic.

Lucrarea de laborator nr. 11.

METODE GENERALE DE ELABORARE A ALGORITMILOR (III)

Continutul lucrarii

În 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 îndeplinesc principiul optimalitatii.

Principiul optimalitatii consta în urmatoarele:

Fie starile s₀, s₁, ..., s_n, în 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 în starea s_j, trecând 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 în starea s_k, respectiv din starea s_k în 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 în alta si se rezolva.

Drept exemplu se ia înmultirea optima a unui sir de matrici.

R=A₁*A₂*...*A_n

în 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 înmultirea matricelor A_i si A_i+1 se efectueaza d_i*d_i+1*d_i+2 operatii de înmultire. Daca matricele au dimensiuni diferite, numarul operatiilor de înmultire necesare obtinerii matricei rezultat R depinde de ordinea efectuarii produselor a câte doua matrice. Se cere gasirea ordinii de asociere pentru care numarul înmultirilor sa fie minim.

Rezolvarea acestei probleme se va face astfel:

Fie C_ij numarul minim de înmultiri 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, pâna 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. Vârfurile arborelui vor contine limitele subsirului de matrice care se asociaza; radacina va contine (1,n), iar un subarbore care contine în radacina (i, j) va avea descendenti pe (i, k) si (k+1, j), unde k este valoarea pentru care se realizeaza optimul cerut.

În 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;

}

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 C\n");

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 POSTORDINE\n");

postordine(rad,0);

getch();

Metode euristice

Prin algoritm euristic se va întelege un algoritm care furnizeaza o solutie aproximativa, nu neaparat optimala, dar care poate fi implementata usor si da rezultate în 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 în mai multe procese succesive, carora li se cauta solutia optimala. Idea nu conduce la obtinerea în final în mod sigur a unei solutii optime, întrucât optimizarea locala nu implica în general optimizarea globala.

În 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, G) în care toate nodurile sunt unite între ele printr-o muchie, careia i se asociaza un cost strict pozitiv. Se cere determinarea unui ciclu, care sa înceapa dintr-un nod i, sa treaca exact o data prin toate nodurile si sa se întoarca în nodul initial. Se cere ca ciclul gasit sa aiba un cost minim.

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

Algoritmul euristic prezentat mai jos bazat pe metoda Greedy necesita un timp polinomial. Rezolvarea consta în 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 încheiat;

daca (v₁, v₂, ..., v_k) X, se adauga muchia care leaga v_k de un vârf apartinând lui x, dar neinclus în cale.

Pentru ca ciclul este o cale închisa, 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.

În 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 =%d\n",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 între oricare doua vârfuri 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 îi este atasata o valoare strict pozitiva, reprezentând punctajul primit de concurent în 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 în B, stiind ca singurele operatii permise sunt:

a)      Adunarea la A a oricâte numere din vectorul v;

b)      Scaderea din A a oricâte numere din vectorul v;

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

Daca raspunsul la întrebare este afirmativ, se cere numarul minim de operatii prin care se poate trece din A în 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 în cm de la pamânt pâna la pozitia în care se afla si prin greutatea sa g_i în grame. Un culegator doreste sa culeaga o cantitate exprimata în grame cât mai mare de mere. Dupa ce este cules un mar întreaga creanga devine mai usoara si se ridica în sus cu x cm. Culegatorul ajunge doar la merele aflate la o înaltime mai mica sau egala cu d cm. Sa se determine greutatea maxima de mere care poate fi culeasa si ordinea în care sunt culese merele.

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

Sa se rezolve prin metode euristice urmatoarele probleme:

Sa se gaseasca maximul unei functii f(x) în 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 încât doua vârfuri 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.