Metoda Divide et impera
Metoda Divide et Impera (Imparte si Stapaneste) este o metoda de
programare care se aplica problemelor care pot fi descompuse in subprobleme
independente, similare problemei initiale, de dimensiuni mai mici si care pot
fi rezolvate foarte usor. Procesul se
reia pana cand (in urma descompunerilor repetate) se ajunge la probleme care
admit rezolvare imediata.
Metoda presupune:
Descompunerea problemei Pb curente in subprobleme independente SubPbi.
In cazul in care subproblemele SubPbi. admit o rezolvare imediata se
compun solutiile si se rezolva problema Pb.
Altfel se descompun in mod similar si subproblemele SubPbi.
Evident, nu toate problemele pot fi rezolvate prin utilizarea acestei
tehnici. Majoritatea algoritmilor de Divide et Impera presupun prelucrari pe
tablouri (dar nu obligatoriu).
Aceasta metoda (tehnica) se poate implementa atat iterativ dar si
recursiv. Dat fiind ca problemele se impart impart in subprobleme in mod
recursiv, de obicei impartirea se
realizeaza pana cand sirul obtinut este de lungime 1, caz in care rezolvarea
subproblemei este foarte usoara, chiar banala.
Spre exemplu fie un vector X=[x1, x2, x3, …xi … xp… xj, …xn] asupra caruia
se aplica o prelucrare. Pentru orice secventa din vector delimitata de
indecsii i si j, i<j exista o valoare p astfel incat prin
prelucrarea secventelor :
xi, xi+1,
xi+2, xi+3, …xp si xp+1, xp+2, xp+3, …xj
se obtin solutiile corespunzatoare
celor doua subsiruri care prin compunere conduc la obtinerea solutiei
prelucrarii secventei:
xi, xi+1, xi+2, xi+3, …xj
Divide et impera se bazează pe principiul descompunerii
problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar
soluția pentru problema inițială se obține combinând soluțiile subproblemelor.
De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se
poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când
(în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare
imediată.
Nu toate problemele pot fi rezolvate prin utilizarea
acestei tehnici. Se poate afirma că numărul celor rezolvabile prin "divide
et impera" este relativ mic, tocmai datorită cerinței ca problema să
admită o descompunere repetată.
Divide et impera este o tehnică ce admite o implementare
recursivă. Principiul general prin care se elaborează algoritmi recursivi este:
"ce se întâmplă la un nivel, se întâmplă la orice nivel" (având grijă
să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera
se elaborează astfel: la un anumit nivel avem două posibilități:
s-a ajuns la o problemă care admite o rezolvare imediată
(condiția de terminare), caz în care se rezolvă și se revine din apel;
nu s-a ajuns în situația de la punctul 1, caz în care
problema curentă este descompusă în (două sau mai multe) subprobleme, pentru
fiecare din ele urmează un apel recursiv al funcției, după care combinarea
rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea
revenirii din apel.
Notiuni introductive
Dictonul latin, care se traduce prin " dezbina si stapaneste
", sintetizeaza modalitatea prin care romanii au ajuns stapanii lumii
antice. Ca tehnica, metoda de programare DIVIDE ET IMPERA consta in impartirea
problemei initiale de dimensiuni [n] in doua sau mai multe probleme de
dimensiuni reduse .In general se executa impartirea in doua subprobleme de dimensiuni aproximativ egale si anume [n/2] . Impartirea in subprobleme
are loc pana cand dimensiunea acestora devine suficient de mica pentru a fi
rezolvate in mod direct(cazul de baza).Dupa rezolvarea celor doua subprobleme
se executa faza de combinare a rezultatelor 222i87c in vederea rezolvarii
intregii probleme .
Metoda DIVIDE ET IMPERA se poate aplica in rezolvarea unei probleme care indeplineste
urmatoarele conditii :
4 se poate descompune in ( doua sau mai multe) suprobleme
;
4aceste suprobleme sunt independente una fata de alta (o
subproblema nu se rezolva pe baza alteia si
nu se foloseste rezultatele celeilalte);
4aceste subprobleme sunt similare cu problema initiala;
4 la randul lor subproblemele se pot descompune (daca
este necesar) in alte subprobleme mai simple;
4aceste subprobleme simple se pot solutiona imediat prin
algoritmul simplificat.
Etapele rezolvarii unei probleme (numita problema
initiala) in DIVIDE ET IMPERA sunt :
4 descompunerea problemei initiale in subprobleme
independente ,similare problemei de baza ,de dimensiuni mai mici ;
4descompunerea treptata a subproblemelor in alte
subprobleme din ce in ce mai simple ,pana cand se pot rezolva imediat ,prin
algoritmul simplificat ;
4rezolvarea subproblemelor simple ;
4combinarea solutiilor gasite pentru construirea
solutiilor subproblemelor de dimensiuni din ce in ce mai mari ;
4 combinarea ultimelor solutii determina obtinerea
solutiei problemei initiale .
Metoda DIVIDE ET IMPERA admite o implementare recursiva,
deoarece subproblemele sunt similare
problemei initiale, dar de
dimensiuni mai mici .
Principiul fundamental al recursivitatii este
autoapelarea unui subprogram cand acesta este activ; ceea ce se intampla la un
nivel ,se intampla la orice nivel ,avand grija sa asiguram conditia de
terminare ale apelurilor repetate .Asemanator se intampla si in cazul metodei
DIVIDE ET IMPERA ; la un anumit nivel
sunt doua posibilitati :
· s-a ajuns
la o (sub)problema simpla ce admite o rezolvare imediata caz in care se rezolva
(sub)problema si se revine din apel (la subproblema anterioara,de dimensiuni
mai mari);
· s-a ajuns
la o (sub)problema care nu admite o
rezolvare imediata, caz in care o descompunem in doua sau mai multe subprobleme
si pentru fiecare din ele se continua apelurile recursive(ale procedurii sau
functiei).·
In etapa finala a metodei DIVIDE ET IMPERA se produce combinarea subproblemelor
(rezolvate deja) prin secventele de revenire din apelurile recursive.
Etapele metodei
DIVIDE ET IMPERA (prezentate anterior)se pot reprezenta prin urmatorul
subprogram Ieneral (procedura sau functie) recursiv exprimat in limbaj natural:
Subprogram DIVIMP (PROB);
Daca PROBLEMA PROB este simpla
Atunci se rezolva si se obtine solutia SOL
Altfel pentru i=1,k executa DIVIMP(PROB) si se obtine
SOL1;
Se combina solutiile SOL 1, ,SOL K si se obtine SOL;
Sfarsit _subprogram;
Deci ,subprogramul DIVIMP se apeleaza pentru problema
initiala PROB; aceasta admite descompunerea in K subprobleme simple ;pentru
acestea se reapeleaza recursiv subprogramul ;in final se combina solutiile
acestor K subprobleme.
De obicei problema initiala se descompune in doua
subprobleme mai simple ; in acest caz etapele generale ale metodei DIVIDE ET
IMPERA se pot reprezenta concret,in limbaj pseudocod ,printr-o procedura
recursiva astfel :
Procedura
DIVIMP(li,ls,sol);
Daca ((ls-li)<=eps)
Atunci REZOLVA (li,ls,sol);
Altfel
DIVIDE (li,m,ls);
DIVIMP(li,msol1);
DIVIMP(m,ls,sol2);
COMBINA(sol1,sol2,sol);
Sfarsit_ procedura;
