Metode generale de elaborare a algoritmilor (ii)

METODE GENERALE DE ELABORARE A ALGORITMILOR (II)

1. Continutul lucrarii

In 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 inrudita 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 in 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 in starea s_i+1. Se introduc restrictii ca sa nu existe mai multe noduri in graf cu aceeasi stare, deci graful sa nu fie infinit. Astfel graful se reduce la un arbore. Arborele se genereaza pana la prima aparitie a nodului final.

Exista posibilitatea parcurgerii grafului in adancime sau in latime, insa timpul de ajungere la rezultat este mare. O strategie superioara din punct de vedere al timpului de calcul se obtine alegand dintre descendentii varfului 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 varfurilor din arbore. Avand valorile acestei functii, vom alege dintre varfurile descendente ale varfului 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 varf la varful final este:

rezultat;

daca x este varf terminalvarful rezultat

daca x nu este varf rezultat

Functia c definita mai sus nu este aplicabila, intrucat calculul ei presupune parcurgerea tuturor varfurilor arborelui, de fapt urmarindu-se tocmai evitarea acestui lucru.

Se observa ca daca totusi functia c este calculata, atunci coborarea in arbore la varful rezultat se face pe un drum deja format din varfurile x ce au atasata o valoare c(x) egala cu c(radacina).

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

a)   nivelul varfului 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, in 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 varfurile care memoreaza configuratia starilor. Pentru varful i luat in considerare se memoreaza tatal sau in vectorul TATA, permitand ca odata ajunsi in varful rezultat sa se poata reface drumul de la radacina la varful rezultat.

RAD este pointerul la varful 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:

LISTAVIDA(L) - initializeaza lista L ca fiind vida;

ESTEVIDA(L) -- returneaza 1 daca lista L este vida sau 0 in caz contrar;

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

ADAUG(j, L) --- adauga nodul j la lista L. Din descrierea functiei se observa ca atunci cand un varf i din lista L devine varf curent, sunt generati toti descendentii sai, acestia fiind pusi in lista L. Unul din acesti descendenti va deveni la randul sau pe baza costului varf curent, pana cand se ajunge la varful rezultat (cel ce contine starea finala).

Metoda "Divide et Impera"

Metoda "Divide et Impera" consta in impartirea repetata a unei probleme in doua sau mai multe probleme de acelasi tip si apoi combinarea subproblemelor rezolvate, in final obtinandu-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 incat exista un incat prelucrarea secventei se poate face prelucrand 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 */

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

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 in care secventa a_p, a_p+1, ,a_q este impartita in doua subsecvente de functia DIVIDE;

beta si gama - reprezinta rezultatele intermediare obtinute in 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 - imparte secventa (a_p, a_p+1, ,a_q) in doua subsecvente (a_p, a_p+1, ,a_m) si

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

COMBINA - combina rezultatele beta si gama ale prelucrarii subsecventelor returnate de procedura DIVIDE, obtinand 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 NESORTATn');

afisare(n);

divide_impera(0,n-1);

printf('nVECTORUL SORTATn');

afisare(n);

getch();

}

Mersul lucrarii

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

Jocul PERSPICO. 15 placute patrate sunt incadrate intr-un cadru de dimensiune 4x4, o pozitie fiind libera. Orice placuta vecina cu aceasta pozitie libera poate fi mutata in locul ei. Cele 15 placute sunt numerotate de la 1 la 15. Se incepe dintr-o stare initiala, care corespunde unei distributii oarecare a celor 15 placute si a locului liber in cele 16 pozitii posibile. Problema consta in a trece, folosind mutari posibile, din starea initiala in 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 langa altul, numerotate cu valori distincte din multimea 1n. O macara poate lua k vagoane de pe linie si le poate aseza in partea dreapta, la sfarsitul sirului de vagoane, care apoi prin impingere ajung din nou unul langa altul, in noua ordine creata dupa operatia respectiva.

Dandu-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 in final vagoanele sa se afle in ordine crescatoare 1, 2, , n .

Pe malul unui rau se afla 2n bastinasi din care n sunt canibali. Acestia doresc sa traverseze raul utilizand o barca care poate transporta cel mult k persoane. Daca pe un mal sau in barca sunt mai multi canibali decat ceilalti, atunci canibalii ii vor manca. Cum vor reusi sa treaca toti pe malul opus fara sa se manance 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, insa fiecare capra poate sari peste o singura capra din grupul opus si desigur poate avansa daca in 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 intreg ordonate crescator, sa se scrie o functie de cautare a unui element dat in vector, returnandu-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, utilizand tija a treia ca intermediar, cu conditia mutarii a cate unui singur disc si fara a pune un disc de diametru mai mare peste unul cu diametru mai mic.