Metoda divide et impera

Metoda divide et impera este o metodă de programare care rezolvă o problemă prin descompunerea ei în subprobleme independente, de același tip cu problema inițială și de dimensiuni mai mici. Subproblemele se rezolvă separat, iar din soluțiile lor se obține soluția problemei inițiale.

Denumirea vine din limba latină și înseamnă „împarte și stăpânește”: prima parte numește descompunerea, a doua rezolvarea subproblemelor obținute.

Descrierea metodei

Metoda presupune:

• descompunerea problemei inițiale în două sau mai multe subprobleme independente — etapa divide;
• rezolvarea separată a fiecărei subprobleme — etapa impera;
• construirea rezultatului, prin compunerea soluțiilor subproblemelor de dimensiuni mici.

Descompunerea se repetă: fiecare subproblemă se descompune la rândul ei, până se ajunge la subprobleme care admit rezolvare imediată. Când se prelucrează un șir de valori, descompunerea continuă de obicei până la subșiruri cu un singur element, pentru care soluția se obține direct.

Fiindcă subproblemele sunt de același tip cu problema inițială, metoda admite o implementare recursivă: ce se face la un nivel se face la fel la orice nivel, iar subproblema elementară este condiția de oprire a autoapelurilor. La orice nivel, subprogramul întâlnește unul din cazurile următoare:

• subproblema admite rezolvare imediată: se rezolvă, iar apelul se încheie;
• subproblema nu admite rezolvare imediată: se descompune, subprogramul se autoapelează pentru fiecare parte, iar la revenire soluțiile parțiale se combină.

Metoda se poate implementa și iterativ, dar atunci subproblemele trebuie ținute într-o structură proprie. La sortarea prin interclasare, de pildă, se pornește de la subșiruri de un element și se interclasează de jos în sus, întâi câte două, apoi câte patru, fără niciun autoapel.

Pașii algoritmului

1. Problema se descompune în subprobleme de același tip, de dimensiuni mai mici, care prelucrează mulțimi de date disjuncte, deci niciuna nu are nevoie de rezultatul alteia.
2. Dacă subproblema este cazul de bază, soluția ei se obține direct; dacă nu, se reia pasul 1 pentru ea.
3. Soluțiile parțiale se combină, două câte două, până la obținerea soluției problemei inițiale.

Oportunitatea utilizării metodei

Metoda este oportună atunci când problema se descompune firesc în subprobleme independente de același tip, iar combinarea soluțiilor parțiale este simplă. Se recomandă în situațiile următoare:

• metoda dă un algoritm mai eficient decât varianta iterativă — căutarea binară într-un vector ordonat, sortarea prin interclasare și sortarea rapidă;
• rezolvarea prin divizare este mai simplă decât cea iterativă — problema turnurilor din Hanoi, la care algoritmul iterativ este greu de scris, iar cel recursiv are cinci rânduri.

Folosirea ei aduce avantaje, dar are și limite:

Metoda nu caută un optim: ea nu compară mai multe soluții între ele, cum fac metoda greedy sau programarea dinamică, ci calculează un rezultat unic, determinat de datele de intrare.

Când subproblemele nu sunt independente

Termenul n al șirului lui Fibonacci se descompune, aparent, în exact două subprobleme de același tip: termenul n − 1 și termenul n − 2. Descompunerea continuă până la f1 și f2, a căror valoare este cunoscută. Condiția de independență nu este însă îndeplinită: în calculul lui fn-1 reapare calculul lui fn-2, iar în calculul amândurora reapare fn-3, așa încât aceeași subproblemă se rezolvă de mai multe ori, iar numărul apelurilor crește exponențial.

Pentru asemenea probleme se folosește algoritmul iterativ, care calculează pe rând termenii f3, f4, …, fn, sau programarea dinamică, în care rezultatul fiecărei subprobleme se reține și se refolosește.

Independența subproblemelor este, așadar, condiția care desparte cele două metode: la divide et impera subproblemele nu se suprapun, la programarea dinamică se suprapun.

Aplicabilitate

Metoda se poate aplica unei probleme care îndeplinește toate condițiile următoare:

• admite o descompunere în cel puțin două subprobleme;
• subproblemele sunt de același tip cu problema inițială, deci se rezolvă prin aceeași metodă;
• subproblemele sunt independente: niciuna nu se rezolvă pe baza rezultatului alteia, iar mulțimile de date de intrare pe care le prelucrează sunt disjuncte;
• subproblemele se pot descompune, la rândul lor, în subprobleme mai simple;
• subproblemele simple admit rezolvare imediată, printr-un algoritm elementar.

Puține probleme le îndeplinesc pe toate, iar de aceea metoda se aplică mai rar decât celelalte metode de programare.

Metoda se potrivește cel mai bine problemelor în care datele de intrare formează un tablou unidimensional. Șirul (x1, x2, …, xn) se împarte în subșirurile (x1, …, xm) și (xm+1, …, xn), fiecare dintre ele se prelucrează la fel, iar din cele două rezultate se obține rezultatul pentru șirul întreg.

Generalizare

Fie P(n) problema inițială, în care se prelucrează n elemente. Dimensiunea unei probleme este, prin definiție, câte elemente are de prelucrat.

Etapa I, divide (împarte). Problema P(n) se descompune în subproblemele P1(n1), P2(n2), …, Pk(nk), de același tip, independente, fiecare de dimensiune mai mică decât n.

Etapa II, impera (stăpânește).

• se rezolvă subproblemele P1, P2, …, Pk și se obțin soluțiile parțiale S1, S2, …, Sk;
• soluțiile parțiale se combină și se obține soluția S a problemei inițiale.

Observații:

• o subproblemă obținută se rezolvă direct dacă dimensiunea ei o permite; altfel se descompune la rândul ei;
• descompunerea se oprește la subproblema care admite rezolvare imediată; ea se numește caz de bază sau problemă elementară.

Funcționarea metodei

Etapele rezolvării se parcurg în ordinea următoare:

• problema inițială se descompune în subprobleme independente, de același tip, de dimensiuni mai mici;
• fiecare subproblemă obținută se descompune la fel, iar descompunerile se opresc la subproblemele care admit rezolvare imediată;
• subproblemele elementare se rezolvă;
• la revenire, fiecare pereche de soluții parțiale se combină și dă soluția subproblemei din care cele două au ieșit;
• ultima combinare dă soluția problemei inițiale.

Prima jumătate a acestui parcurs este analitică: problema se reduce, prin divizări repetate, până la problema elementară. A doua jumătate este de sinteză: soluțiile parțiale urcă până la soluția finală.

În execuție, cele două jumătăți se văd în stiva apelurilor. Apelurile coboară până la cazul de bază și nu calculează pe drum decât împărțirile; combinările se fac abia la revenirea din apeluri, în ordine inversă celei în care s-au făcut descompunerile.

Algoritmul metodei

Descompunerea repetată a unei probleme în subprobleme de același tip, fiecare rezolvată pe un interval de indici mai scurt decât cel dinainte, este un procedeu recursiv; el se oprește la subproblemele elementare.

Fie șirul X = (x1, x2, …, xn), asupra căruia se face prelucrarea cerută de problema P. Se poate arăta că, pentru orice doi indici p și u cu p < u, există între ei un indice poz cu însușirea următoare: prelucrând subșirurile (xp, …, xpoz) și (xpoz+1, …, xu) se obțin soluțiile lor, iar din aceste două soluții se obține soluția prelucrării secvenței (xp, …, xu). Indicele poz se numește și pivot; de cele mai multe ori el este indicele din mijlocul intervalului [p, u], adică al elementului median. În programele de mai jos, același indice se numește m.

Subprogramul recursiv are doi parametri de intrare, p și u, capetele secvenței pe care se lucrează; primul apel se face cu p = 1 și u = n. Soluția obținută la fiecare nivel se transmite prin parametrul de ieșire sol.

algoritm divideEtImpera(p, u, sol)
    dacă p < u atunci
        imparte(p, u, poz)                // se află poziția pivotului
        divideEtImpera(p, poz, sol1)      // se aplică algoritmul
        divideEtImpera(poz + 1, u, sol2)  // pentru fiecare subproblemă
        sol ← combina(sol1, sol2)         // formarea soluției
    altfel
        rezolva(p, u, sol)                // subproblema elementară
    sfdacă
stop algoritm divideEtImpera

Cele trei subprograme numite înăuntru corespund celor trei etape:

• imparte stabilește pivotul după care se face descompunerea;
• rezolva dă soluția subproblemei elementare;
• combina obține soluția dintr-o pereche de soluții parțiale.

La problemele simple ele nu se scriu separat: împărțirea se reduce la o atribuire, iar combinarea la o comparație sau la o adunare. La sortarea prin interclasare, în schimb, combina este chiar algoritmul de interclasare, iar la sortarea rapidă imparte este subprogramul care așază pivotul pe locul lui.

Problemele rezolvate prin această metodă

• problema turnurilor din Hanoi;
• sortarea prin interclasare (mergesort);
• sortarea rapidă (quicksort);
• căutarea binară.

Primele trei sunt trecute anume în programa de examen, ca aplicații specifice ale metodei. Toate patru sunt scrise mai jos.

Implementarea metodei

Implementarea depinde de limbaj și de problemă. Partea recursivă stă în subprogramul care formează nucleul programului. Acesta are, în orice limbaj, cei doi parametri p și u, capetele domeniului pe care se rezolvă problema la momentul respectiv. Când subprogramul este funcție, soluția se întoarce prin numele funcției, deci parametrul de ieșire nu mai este necesar.

Minimul dintr-un șir

La determinarea celei mai mici valori dintr-un șir, divizarea împarte șirul în două subșiruri de lungimi apropiate. Cazul de bază este subșirul cu un singur element, care este chiar minimul lui. Combinarea celor două soluții parțiale înseamnă compararea lor: minimul este cel mai mic dintre min1 și min2.

minim(p, u):
    dacă p = u atunci
        returnează x[p]
    altfel
        m ← [(p + u) / 2]
        min1 ← minim(p, m)
        min2 ← minim(m + 1, u)
        dacă min1 < min2 atunci
            returnează min1
        altfel
            returnează min2
        sfdacă
    sfdacă

/* Intoarce cea mai mica valoare din subsirul x[p..u]. */
int minim(int p, int u) {
    if (p == u)                 // problema elementara
        return x[p];
    int m = (p + u) / 2;        // divide
    int min1 = minim(p, m);     // stanga
    int min2 = minim(m + 1, u); // dreapta
    if (min1 < min2)            // combina
        return min1;
    return min2;
}

# Intoarce cea mai mica valoare din subsirul x[p..u].
def minim(x, p, u):
    if p == u:                  # problema elementara
        return x[p]
    m = (p + u) // 2            # divide
    min1 = minim(x, p, m)       # stanga
    min2 = minim(x, m + 1, u)   # dreapta
    if min1 < min2:             # combina
        return min1
    return min2

Pentru șirul 4 9 −2 7 1, apelul minim(1, 5) împarte la m = 3 și cere minimul din (4, 9, −2) și din (7, 1). Descompunerea continuă până la subșiruri cu un element, iar la revenirea din apeluri se compară perechile: min(4, 9) = 4, apoi min(4, −2) = −2 în stânga, min(7, 1) = 1 în dreapta și, în cele din urmă, min(−2, 1) = −2.

Ordinul de complexitate rămâne O(n), ca al parcurgerii obișnuite: fiecare element este citit o dată.

Complexitatea metodei

Un algoritm care conține un apel recursiv are timpul de execuție dat de o formulă recurentă: timpul pentru dimensiunea n se exprimă prin timpii pentru dimensiuni mai mici. Dacă problema se descompune în a subprobleme, fiecare de dimensiune n/b, iar D(n) este timpul descompunerii și C(n) timpul combinării, atunci

T(n) = a · T(n/b) + D(n) + C(n),    T(1) = Θ(1)

Din această formulă se obțin ordinele de complexitate ale aplicațiilor metodei:

Ultimul rând arată deosebirea care hotărăște ordinul: la primele patru probleme dimensiunea se împarte la 2, deci numărul nivelurilor de descompunere este log₂ n; la turnurile din Hanoi ea scade cu 1, deci nivelurile sunt n, iar numărul apelurilor se dublează de la un nivel la altul.

Pe lângă timp se ia în seamă și memoria: apelurile recursive nerevenite se păstrează pe stivă, deci consumul suplimentar este proporțional cu adâncimea descompunerii: O(log₂ n) când secvența se împarte în două părți egale.

Problema turnurilor din Hanoi

Enunțul problemei

Se dau trei tije verticale, numerotate 1, 2 și 3, și n discuri perforate central, cu diametre diferite două câte două. La început toate discurile se află pe tija 1, cel mai mare dedesubt și cel mai mic deasupra. Se cer mutările prin care discurile ajung, în aceeași ordine, pe tija 2, folosind tija 3 ca tijă auxiliară. Regulile jocului sunt:

• se mută câte un disc, și anume cel de deasupra unei tije;
• niciun disc nu se așază peste unul cu diametrul mai mic decât al său.

Date de intrare. Numărul natural nenul n de discuri, n ≤ 10.

Date de ieșire. Mutările efectuate, pe linii distincte. O mutare se scrie i -> j, cu înțelesul „discul de pe tija i se mută pe tija j”.

Ideea de rezolvare

Discul cel mai mare se poate duce de pe tija i pe tija j numai dacă pe tija j nu se află niciun disc mai mic decât el și dacă cele n − 1 discuri de deasupra lui au fost mutate pe tija rămasă. Tijele sunt numerotate 1, 2 și 3, deci suma numerelor lor este 6, iar tija auxiliară se află din calculul 6 − i − j.

Mutarea a n discuri de pe tija i pe tija j se descompune astfel:

• cele n − 1 discuri de deasupra ajung pe tija auxiliară;
• discul cel mai mare trece de pe tija i pe tija j;
• cele n − 1 discuri revin de pe tija auxiliară pe tija j.

S-au obținut două subprobleme de același tip, fiecare cu un disc mai puțin. Ele sunt independente: după ce discul mare a ajuns pe tija j, el nu mai încurcă nicio mutare, fiindcă are diametrul cel mai mare și orice disc poate fi așezat peste el. Descompunerea se oprește la n = 1, caz în care discul se mută direct.

Notând cu hanoi(n, i, j) șirul mutărilor, definiția recursivă este

hanoi(n, i, j) = i → j,                                       dacă n = 1
hanoi(n, i, j) = hanoi(n−1, i, 6−i−j), i → j, hanoi(n−1, 6−i−j, j),  dacă n > 1

Exemplul pentru n = 3

Pentru trei discuri mutate de pe tija 1 pe tija 2 se execută șapte mutări:

Primele trei mutări duc discurile mici pe tija auxiliară, a patra este mutarea discului mare, iar ultimele trei aduc discurile mici peste el.

Numărul mutărilor

Din descompunere rezultă că numărul mutărilor M(n) respectă recurența

M(1) = 1
M(n) = 2 · M(n − 1) + 1,    pentru n > 1

Adunând 1 în ambii membri se obține M(n) + 1 = 2 · (M(n − 1) + 1), deci șirul M(n) + 1 este o progresie geometrică cu rația 2 și primul termen 2. De aici M(n) + 1 = 2ⁿ, adică

M(n) = 2ⁿ − 1

Pentru n = 3 se obțin cele 7 mutări din tabelul de mai sus, pentru n = 10 sunt 1023, iar pentru n = 64 numărul lor depășește cu mult ce se poate calcula în timp util. Numărul mutărilor este minim: fiecare mutare din algoritm este necesară, fiindcă discul de diametru maxim nu poate fi mutat mai devreme.

Programul

hanoi(n, i, j):
    dacă n = 1 atunci
        scrie i, " -> ", j
    altfel
        hanoi(n − 1, i, 6 − i − j)
        scrie i, " -> ", j
        hanoi(n − 1, 6 − i − j, j)
    sfdacă

citește n
hanoi(n, 1, 2)

#include <iostream>
using namespace std;

int n, mutari;

/* Muta n discuri de pe tija i pe tija j. Tijele sunt numerotate
   1, 2 si 3, iar suma numerelor lor este 6, deci tija auxiliara
   este 6 - i - j. */
void hanoi(int n, int i, int j) {
    if (n == 1) {                   // problema elementara
        cout << i << " -> " << j << "\n";
        mutari++;
    } else {
        hanoi(n - 1, i, 6 - i - j); // discurile mici, pe tija auxiliara
        cout << i << " -> " << j << "\n";   // discul mare, direct pe tija j
        mutari++;
        hanoi(n - 1, 6 - i - j, j); // discurile mici, peste discul mare
    }
}

int main() {
    cin >> n;
    hanoi(n, 1, 2);
    cout << "Total: " << mutari << " mutari";
    return 0;
}

mutari = 0


# Muta n discuri de pe tija i pe tija j. Tijele sunt numerotate
# 1, 2 si 3, iar suma numerelor lor este 6, deci tija auxiliara
# este 6 - i - j.
def hanoi(n, i, j):
    global mutari
    if n == 1:                      # problema elementara
        print(i, "->", j)
        mutari += 1
    else:
        hanoi(n - 1, i, 6 - i - j)  # discurile mici, pe tija auxiliara
        print(i, "->", j)           # discul mare, direct pe tija j
        mutari += 1
        hanoi(n - 1, 6 - i - j, j)  # discurile mici, peste discul mare


n = int(input())
hanoi(n, 1, 2)
print("Total:", mutari, "mutari")

Subprogramul nu are parametru de ieșire și nici valoare întoarsă: soluția problemei este chiar șirul mutărilor afișate, în ordinea în care se execută apelurile. Combinarea soluțiilor parțiale se face, aici, prin însăși ordinea celor trei instrucțiuni: mutările subproblemei din stânga, mutarea discului mare, mutările subproblemei din dreapta.

Sortarea prin interclasare

Enunțul problemei

Se consideră un șir x cu n elemente întregi. Să se ordoneze crescător prin metoda interclasării.

Date de intrare. Pe prima linie numărul n, pe a doua cele n valori, separate prin câte un spațiu.

Date de ieșire. Cele n valori, în ordine crescătoare.

Ideea de rezolvare

Interclasarea ia două șiruri ordonate crescător și dă un al treilea șir, ordonat crescător, cu toate valorile lor. Ea parcurge cele două șiruri cu câte un indice și efectuează cel mult a + b − 1 comparații, dacă șirurile au a și b elemente.

De aici vine descompunerea: șirul se împarte în două subșiruri, fiecare se ordonează prin aceeași metodă, iar cele două subșiruri ordonate se interclasează. Cazul de bază este subșirul cu un singur element, care este deja ordonat.

Cele trei etape se recunosc ușor:

• divide — se calculează m = (p + u) / 2;
• impera — se ordonează, prin autoapel, subșirurile x[p..m] și x[m+1..u];
• combina — se interclasează cele două subșiruri ordonate.