Algoritm de împărțire și cucerire - Divide-and-conquer algorithm

În informatică , divizarea și cucerirea este o paradigmă de proiectare a algoritmilor . Un algoritm de împărțire și cucerire descompune recursiv o problemă în două sau mai multe subprobleme de același tip sau tip conex, până când acestea devin suficient de simple pentru a fi rezolvate direct. Soluțiile la problemele secundare sunt apoi combinate pentru a oferi o soluție la problema inițială.

Tehnica de împărțire și cucerire stă la baza algoritmilor eficienți pentru multe probleme, cum ar fi sortarea (de ex., Rapid , sortarea fuzionării ), înmulțirea numerelor mari (de exemplu, algoritmul Karatsuba ), găsirea celei mai apropiate perechi de puncte , analiza sintactică ( de exemplu, analizori de sus în jos ) și calcularea transformatei Fourier discrete ( FFT ).

Proiectarea algoritmilor eficienți de divizare și cucerire poate fi dificilă. La fel ca în inducția matematică , este adesea necesară generalizarea problemei pentru a o face supusă unei soluții recursive. Corectitudinea unui algoritm de divizare și cucerire este de obicei dovedită prin inducție matematică, iar costul său de calcul este adesea determinat prin rezolvarea relațiilor de recurență .

Diviza și cuceri

Împărțiți și cuceriți abordarea pentru a sorta lista (38, 27, 43, 3, 9, 82, 10) în ordine crescătoare. Jumătatea superioară: împărțirea în subliste; mijloc: o listă cu un singur element este sortată banal; jumătate inferioară: compunerea sublistelor sortate.

Paradigma divizează și cucerește este adesea utilizată pentru a găsi o soluție optimă a unei probleme. Ideea sa de bază este de a descompune o problemă dată în două sau mai multe subprobleme similare, dar mai simple, pentru a le rezolva pe rând și a compune soluțiile lor pentru a rezolva problema dată. Problemele cu o simplitate suficientă sunt rezolvate direct. De exemplu, pentru a sorta o listă dată de n numere naturale, împărțiți-o în două liste de aproximativ n / 2 numere fiecare, sortați fiecare pe rând și intercalați ambele rezultate în mod corespunzător pentru a obține versiunea sortată a listei date (consultați imagine). Această abordare este cunoscută sub numele de algoritm de sortare a îmbinării .

Numele „divide și cucerește” este uneori aplicat algoritmilor care reduc fiecare problemă la o singură subproblemă, cum ar fi algoritmul de căutare binară pentru găsirea unei înregistrări într-o listă sortată (sau analogul său în calcul numeric , algoritmul de bisecție pentru rădăcină constatare ). Acești algoritmi pot fi implementați mai eficient decât algoritmii generali de divizare și cucerire; în special, dacă utilizează recursivitatea cozii , pot fi transformate în bucle simple . Conform acestei definiții largi, totuși, fiecare algoritm care folosește recursivitate sau bucle ar putea fi considerat ca un „algoritm de împărțire și cucerire”. Prin urmare, unii autori consideră că numele „divizează și cucerește” ar trebui utilizat numai atunci când fiecare problemă poate genera două sau mai multe subprobleme. Numele de scădere și cucerire a fost propus în schimb pentru clasa cu o singură subproblemă.

O aplicație importantă de divizare și cucerire este în optimizare, în cazul în care spațiul de căutare este redus („tăiat”) de un factor constant la fiecare pas, algoritmul general are aceeași complexitate asimptotică ca și pasul de tăiere, cu constanta în funcție de factorul de tăiere (prin însumarea seriei geometrice ); acest lucru este cunoscut sub numele de prune și căutare .

Exemple istorice timpurii

Primele exemple ale acestor algoritmi sunt în primul rând scăzute și cucerite - problema inițială este împărțită succesiv în subprobleme unice și într-adevăr poate fi rezolvată iterativ.

Căutarea binară, un algoritm de scădere și cucerire în care subproblemele au aproximativ jumătate din dimensiunea inițială, are o istorie lungă. În timp ce o descriere clară a algoritmului de pe computere a apărut în 1946 într-un articol de John Mauchly , ideea de a folosi o listă sortată de articole pentru a facilita căutarea datează cel puțin până în Babilonia în 200 î.Hr. Un alt algoritm antic de scădere și cucerire este algoritmul euclidian pentru a calcula cel mai mare divizor comun al a două numere prin reducerea numerelor la subprobleme echivalente din ce în ce mai mici, care datează de câteva secole î.Hr.

Un exemplu timpuriu de algoritm de divizare și cucerire cu mai multe subprobleme este descrierea lui Gauss din 1805 a ceea ce se numește acum algoritmul de transformare Fourier rapidă Cooley – Tukey (FFT), deși nu a analizat cantitatea de funcționare a acestuia , iar FFT-urile au făcut-o nu s-au răspândit până nu au fost redescoperite peste un secol mai târziu.

Un algoritm D&C timpuriu cu două subprobleme, care a fost dezvoltat special pentru computere și analizat în mod corespunzător este algoritmul sort sort , inventat de John von Neumann în 1945.

Un alt exemplu notabil este algoritmul inventat de Anatolii A. Karatsuba în 1960 care ar putea multiplica două numere n- cifre în operații (în notația Big O ). Acest algoritm a respins conjectura lui Andrey Kolmogorov din 1956 conform căreia operațiile ar fi necesare pentru această sarcină. ${\ displaystyle O (n ^ {\ log _ {2} 3})}$ ${\ displaystyle \ Omega (n ^ {2})}$

Ca un alt exemplu de algoritm de împărțire și cucerire care nu implica inițial computerele, Donald Knuth oferă metoda pe care o poștă o folosește de obicei pentru a direcționa corespondența: scrisorile sunt sortate în pungi separate pentru diferite zone geografice, fiecare dintre aceste pungi este ea însăși sortată în loturi pentru subregiuni mai mici și așa mai departe până când sunt livrate. Acest lucru este legat de o sortare radix , descrisă pentru mașinile de sortat cartele perforate încă din 1929.

Avantaje

Rezolvarea problemelor dificile

Împărțiți și cuceriți este un instrument puternic pentru rezolvarea problemelor dificile din punct de vedere conceptual: tot ce necesită este un mod de a împărți problema în subprobleme, de a rezolva cazurile banale și de a combina subproblemele cu problema inițială. În mod similar, scăderea și cucerirea necesită doar reducerea problemei la o singură problemă mai mică, cum ar fi puzzle-ul clasic Turnul din Hanoi , care reduce mutarea unui turn de înălțime pentru a muta un turn de înălțime . ${\ displaystyle n}$ ${\ displaystyle n-1}$

Eficiența algoritmului

Paradigma divizează și cucerește ajută adesea la descoperirea algoritmilor eficienți. A fost cheia, de exemplu, a metodei de înmulțire rapidă a lui Karatsuba, algoritmii quicksort și mergesort, algoritmul Strassen pentru multiplicarea matricei și transformatele Fourier rapide.

În toate aceste exemple, abordarea D&C a condus la o îmbunătățire a costului asimptotic al soluției. De exemplu, dacă (a) cazurile de bază au mărime constantă, munca de divizare a problemei și combinarea soluțiilor parțiale este proporțională cu dimensiunea problemei și (b) există un număr limitat de subprobleme de dimensiune ~ în fiecare etapă, atunci costul algoritmului de divizare și cucerire va fi . ${\ displaystyle n}$ ${\ displaystyle p}$ ${\ displaystyle n / p}$ ${\ displaystyle O (n \ log _ {p} n)}$

Paralelism

Algoritmii de împărțire și cucerire sunt adaptați în mod natural pentru execuția în mașini cu mai multe procesoare, în special sisteme de memorie partajată în care comunicarea datelor între procesoare nu trebuie să fie planificată în prealabil, deoarece subproblemele distincte pot fi executate pe diferite procesoare.

Acces la memorie

Algoritmii de împărțire și cucerire tind, în mod natural, să utilizeze eficient cache-urile de memorie . Motivul este că, odată ce o sub-problemă este suficient de mică, aceasta și toate problemele sale secundare pot fi, în principiu, rezolvate în memoria cache, fără a accesa memoria principală mai lentă. Un algoritm conceput pentru a exploata cache-ul în acest mod este numit cache-oblivious , deoarece nu conține dimensiunea cache-ului ca parametru explicit. Mai mult, algoritmii D&C pot fi proiectați pentru algoritmi importanți (de exemplu, sortare, FFT-uri și multiplicarea matricei) pentru a fi algoritmi optimi care nu conțin cache - utilizează cache-ul într-un mod probabil optim, într-un sens asimptotic, indiferent de dimensiunea cache-ului. În schimb, abordarea tradițională a exploatării cache-ului se blochează , ca și în optimizarea cuiburilor , unde problema este împărțită în mod explicit în bucăți de dimensiunea adecvată - aceasta poate folosi cache-ul în mod optim, dar numai atunci când algoritmul este reglat pentru specificul dimensiunile cache ale unei anumite mașini.

Același avantaj există în ceea ce privește alte sisteme de stocare ierarhice, cum ar fi NUMA sau memoria virtuală , precum și pentru mai multe niveluri de cache: odată ce o sub-problemă este suficient de mică, poate fi rezolvată într-un anumit nivel al ierarhiei, fără accesarea nivelurilor superioare (mai lente).

Control rotund

În calculele cu aritmetică rotunjită, de exemplu, cu numere în virgulă mobilă , un algoritm de divizare și cucerire poate produce rezultate mai precise decât o metodă iterativă echivalentă superficial. De exemplu, se pot adăuga N numere fie printr-o buclă simplă care adaugă fiecare datum la o singură variabilă, fie printr-un algoritm D&C numit sumă pereche care împarte setul de date în două jumătăți, calculează recursiv suma fiecărei jumătăți și apoi adaugă cele două sume. În timp ce a doua metodă efectuează același număr de adăugiri ca prima și plătește cheltuielile generale pentru apelurile recursive, de obicei este mai precisă.

Probleme de implementare

Recursivitate

Algoritmii de împărțire și cucerire sunt implementați în mod natural ca proceduri recursive . În acest caz, subproblemele parțiale care duc la rezolvarea curentă sunt stocate automat în stiva de apeluri de procedură . O funcție recursivă este o funcție care se numește în definiția sa.

Stivă explicită

Algoritmii de împărțire și cucerire pot fi de asemenea implementați de un program nerecursiv care stochează subproblemele parțiale într-o anumită structură de date explicită, cum ar fi o stivă , o coadă sau o coadă prioritară . Această abordare permite mai multă libertate în alegerea subproblemei care urmează a fi rezolvată în continuare, o caracteristică care este importantă în unele aplicații - de exemplu, în lățimea primului recursiv și metoda ramificată și legată pentru optimizarea funcției. Această abordare este, de asemenea, soluția standard în limbaje de programare care nu oferă suport pentru procedurile recursive.

Dimensiunea stivei

În implementările recursive ale algoritmilor D&C, trebuie să vă asigurați că există suficientă memorie alocată pentru stiva de recursie, altfel, execuția poate eșua din cauza depășirii stivei . Algoritmii D&C care sunt eficienți în timp au adesea o adâncime de recursiune relativ mică. De exemplu, algoritmul quicksort poate fi implementat astfel încât să nu necesite niciodată mai mult decât apeluri recursive imbricate pentru a sorta elementele. ${\ displaystyle \ log _ {2} n}$ ${\ displaystyle n}$

Debordarea stivei poate fi dificil de evitat atunci când se utilizează proceduri recursive, deoarece mulți compilatori presupun că stiva recursivă este o zonă contiguă de memorie, iar unii alocă o cantitate fixă de spațiu pentru aceasta. Compilatoarele pot, de asemenea, salva mai multe informații în stiva de recursie decât este strict necesar, cum ar fi adresa de returnare, parametrii neschimbabili și variabilele interne ale procedurii. Astfel, riscul de revărsare a stivei poate fi redus prin minimizarea parametrilor și variabilelor interne ale procedurii recursive sau prin utilizarea unei structuri de stivă explicite.

Alegerea cazurilor de bază

În orice algoritm recursiv, există o libertate considerabilă în alegerea cazurilor de bază , subproblemele mici care sunt rezolvate direct pentru a termina recursiunea.

Alegerea celor mai mici sau mai simple cazuri de bază este mai elegantă și de obicei duce la programe mai simple, deoarece există mai puține cazuri de luat în considerare și sunt mai ușor de rezolvat. De exemplu, un algoritm FFT ar putea opri recursivitatea atunci când intrarea este un singur eșantion, iar algoritmul de sortare a listelor rapide se poate opri atunci când intrarea este lista goală; în ambele exemple, există un singur caz de bază de luat în considerare și nu necesită prelucrare.

Pe de altă parte, eficiența se îmbunătățește adesea dacă recurența este oprită în cazuri de bază relativ mari, iar acestea sunt rezolvate non-recursiv, rezultând un algoritm hibrid . Această strategie evită cheltuielile generale cu apeluri recursive care funcționează puțin sau deloc și pot permite, de asemenea, utilizarea unor algoritmi specializați non-recursivi care, pentru acele cazuri de bază, sunt mai eficiente decât recursivitatea explicită. O procedură generală pentru un algoritm recursiv hibrid simplu este scurtcircuitarea cazului de bază , cunoscută și sub denumirea de recursivitate la distanță . În acest caz, dacă pasul următor va rezulta în cazul de bază este verificat înainte de apelul de funcție, evitând un apel de funcție inutil. De exemplu, într-un copac, mai degrabă decât recurent la un nod copil și apoi verificând dacă este nul, verificând nul înainte de recurs; evită jumătate din apelurile de funcții din unele algoritmi pe copaci binari. Deoarece un algoritm D&C reduce în cele din urmă fiecare instanță de problemă sau subproblemă la un număr mare de instanțe de bază, acestea domină adesea costul general al algoritmului, mai ales atunci când împărțirea / îmbinarea cheltuielilor generale este scăzută. Rețineți că aceste considerații nu depind de faptul dacă recursivitatea este implementată de compilator sau de o stivă explicită.

Astfel, de exemplu, multe implementări de bibliotecă ale quicksort-ului vor trece la un algoritm simplu de sortare pe bază de buclă (sau similar) odată ce numărul de elemente care trebuie sortate este suficient de mic. Rețineți că, dacă lista goală ar fi singurul caz de bază, sortarea unei liste cu intrări ar atrage apeluri rapide rapide care nu ar face altceva decât să revină imediat. Mărirea cazurilor de bază la liste de dimensiunea 2 sau mai mică va elimina majoritatea acestor apeluri fără nimic și, în general, o carcasă de bază mai mare de 2 este de obicei utilizată pentru a reduce fracțiunea de timp petrecut în funcționarea apelurilor generale sau a manipulării stivei. ${\ displaystyle n}$ ${\ displaystyle n}$

Alternativ, se pot utiliza cazuri de bază mari care încă folosesc un algoritm de divizare și cucerire, dar implementează algoritmul pentru un set predeterminat de dimensiuni fixe, în care algoritmul poate fi complet derulat în cod care nu are recursivitate, bucle sau condiționare (legate de tehnica evaluării parțiale ). De exemplu, această abordare este utilizată în unele implementări FFT eficiente, unde cazurile de bază sunt implementări derulate de algoritmi FFT divizați și cuceriți pentru un set de dimensiuni fixe. Metodele de generare a codului sursă pot fi utilizate pentru a produce un număr mare de cazuri de bază separate dorite pentru a implementa eficient această strategie.

Versiunea generalizată a acestei idei este cunoscută sub numele de recursivitate „derulare” sau „grosiere” și au fost propuse diverse tehnici pentru automatizarea procedurii de extindere a cazului de bază.

Partajarea subproblemelor repetate

Pentru unele probleme, recursiunea ramificată poate ajunge să evalueze aceeași subproblemă de multe ori. În astfel de cazuri, ar merita identificarea și salvarea soluțiilor la aceste subprobleme suprapuse, o tehnică este cunoscută în mod obișnuit ca memoizare . Urmărit până la limită, acesta duce la algoritmi de dividere și cucerire de jos în sus , cum ar fi programarea dinamică și analiza graficelor .

Languages

In other projects