Divide and Conquer (informatica)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 4 ianuarie 2021; verificările necesită 22 de modificări .

Divide and conquer în informatică este o  paradigmă de dezvoltare a algoritmului care constă în împărțirea recursiv a problemei de rezolvat în două sau mai multe subsarcini de același tip, dar de dimensiuni mai mici, și combinarea soluțiilor acestora pentru a obține un răspuns la problema inițială; partițiile sunt efectuate până când toate subsarcinile sunt elementare.

Înțelegerea și proiectarea algoritmilor Divide and Conquer este o abilitate complexă care necesită o bună înțelegere a naturii problemei de bază care trebuie rezolvată. Ca și în cazul dovedirii unei teoreme prin inducție matematică , este adesea necesară înlocuirea problemei inițiale cu o problemă mai generală sau complexă pentru a inițializa recursiunea și nu există o metodă sistematică pentru a găsi generalizarea corectă. Astfel de complexități ale metodei Divide and Conquer se văd atunci când se optimizează calculul numărului Fibonacci cu recursivitate dublă eficientă.

Corectitudinea algoritmului după paradigma „Divide and Conquer” este dovedită cel mai adesea prin metoda inducției matematice , iar timpul de rulare este determinat fie prin rezolvarea directă a ecuației recurente corespunzătoare , fie prin aplicarea teoremei relației principale de recurență .

Împărțiți și cuceriți

Paradigma Divide and Conquer este adesea folosită pentru a găsi soluția optimă la o anumită problemă. Ideea sa principală este de a descompune o problemă dată în două sau mai multe subprobleme similare, dar mai simple, de a le rezolva una câte una și de a le compune soluțiile. De exemplu, pentru a sorta o listă dată de n numere naturale, trebuie să o împărțiți în două liste de aproximativ n /2 numere fiecare, să sortați fiecare dintre ele pe rând și să aranjați ambele rezultate în consecință pentru a obține o versiune sortată a acestei liste ( Vezi figura). Această abordare este cunoscută sub numele de algoritm de sortare de îmbinare .

Numele „Divide and Conquer” este uneori aplicat algoritmilor care reduc fiecare problemă la o singură subproblemă, cum ar fi algoritmul de căutare binar pentru găsirea unei intrări într-o listă sortată (sau cazul său special, algoritmul de bisectare pentru găsirea rădăcinilor). [1] Acești algoritmi pot fi implementați mai eficient decât algoritmii generali Divide and Conquer; în special, dacă folosesc recursiunea coadă , pot fi convertite în bucle simple . Cu toate acestea, în conformitate cu această definiție largă, fiecare algoritm care utilizează recursivitate sau bucle poate fi considerat un „algoritm de împărțire și cucerire”. Prin urmare, unii autori consideră că numele „Divide and Conquer” ar trebui folosit doar atunci când fiecare sarcină poate genera două sau mai multe subsarcini. [2] În schimb, numele reduce și cuceri a fost propus pentru clasa problemelor unice. [3]

Exemple

Exemplele timpurii de astfel de algoritmi sunt în primul rând „Reduce and Conquer” - problema inițială este împărțită succesiv în subprobleme separate și, de fapt, poate fi rezolvată iterativ.

Căutarea binară, algoritmul „Reduce and Conquer” în care subproblemele au aproximativ jumătate din dimensiunea inițială, are o istorie lungă. Deși o descriere clară a algoritmului de pe computere a apărut încă din 1946 într-un articol al lui John Mauchly . Ideea de a folosi o listă sortată de articole pentru a ușura căutarea datează cel puțin până în Babilonia , în anul 200 î.Hr. [4] Un alt algoritm antic de reducere și cucerire este algoritmul lui Euclid pentru calcularea celui mai mare divizor comun  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 al algoritmului Divide and Conquer cu subprobleme multiple este descrierea Gaussiană (1805) a ceea ce se numește acum transformata Fourier rapidă Cooley-Tukey [5] .

Un algoritm timpuriu cu două subprobleme Divide and Conquer care a fost conceput special pentru computere și analizat corespunzător este algoritmul de sortare prin îmbinare inventat   de John von Neumann în 1945. [6]

Un exemplu tipic este algoritmul de sortare de îmbinare . Pentru a sorta o matrice de numere în ordine crescătoare, aceasta este împărțită în două părți egale, fiecare este sortată, apoi părțile sortate sunt îmbinate într-una singură. Această procedură se aplică fiecărei părți atâta timp cât partea matricei de sortat conține cel puțin două elemente (astfel încât să poată fi împărțită în două părți). Timpul de rulare al acestui algoritm este reprezentat de operații, în timp ce algoritmii mai simpli necesită timp, unde  este dimensiunea matricei originale.

Un alt exemplu notabil este algoritmul inventat de Anatoly Aleksandrovich Karatsuba în 1960 [7] pentru înmulțirea a două numere din n cifre cu  numărul operației ( notația mare O ). Acest algoritm a infirmat ipoteza lui Andrey Kolmogorov din 1956 conform căreia această sarcină ar necesita operații.

Ca un alt exemplu de algoritm Divide and Conquer care nu a folosit inițial computere. Donald Knuth oferă o metodă folosită în mod obișnuit de oficiul poștal pentru a direcționa corespondența: scrisorile sunt sortate în pachete separate destinate diferitelor zone geografice, fiecare dintre aceste pachete este el însuși sortat în loturi pentru subregiuni mai mici și așa mai departe până când sunt livrate. [4] Acest lucru este legat de sortarea radix , descrisă pentru mașinile de sortat carduri perforate încă din 1929. [patru]

Beneficii

Rezolvarea de probleme complexe

Divide and Conquer este un instrument puternic pentru rezolvarea problemelor complexe din punct de vedere conceptual: tot ceea ce este necesar este să găsiți un caz de împărțire a problemei în subprobleme, rezolvarea cazurilor triviale și combinarea subproblemelor în problema originală. De asemenea, Reduce and Conquer necesită doar reducerea problemei la o problemă mai mică, cum ar fi Turnul clasic din Hanoi , care reduce soluția pentru mutarea unui turn de înălțime n la mutarea unui turn de înălțime n - 1.

Eficiența algoritmului

Paradigma Divide and Conquer ajută adesea la descoperirea algoritmilor eficienți. Aceasta a fost cheia, de exemplu, pentru metoda de înmulțire rapidă a lui Karatsuba, algoritmii de sortare rapidă și mergesort , algoritmul lui Strassen pentru multiplicarea matricelor și transformările rapide Fourier.

În toate aceste exemple, abordarea Divide and Conquer a dus la o îmbunătățire a costului asimptotic al soluției în soluția în sine. De exemplu, dacă (a) cazul de bază are o dimensiune mărginită de o constantă, atunci munca de împărțire a problemei și combinarea soluțiilor parțiale este proporțională cu dimensiunea problemei n și (b) există un număr limitat p de subprobleme de mărimea ~n/p la fiecare etapă, atunci eficiența algoritmului este „Divide and Conquer va fi O( n  log p n ).

Concurență

Algoritmii Divide and Conquer sunt adaptați în mod natural pentru a rula pe mașini cu mai multe procesoare, în special pe sisteme de memorie partajată , în care transferurile de date între procesoare nu trebuie să fie programate din timp, deoarece subsarcinile individuale pot rula pe procesoare diferite.

Acces la memorie

Algoritmii Divide and Conquer tind în mod natural să utilizeze eficient memoria cache . Motivul este că, odată ce o subsarcină este suficient de mică, aceasta și toate subsarcinile sale pot fi, în principiu, rezolvate în cache fără a accesa memoria principală mai lentă. Algoritmul pentru utilizarea cache-ului în acest fel se numește cache-oblivious deoarece nu include dimensiunea cache-ului ca parametru explicit. [8] În plus, algoritmii Divide and Conquer pot fi proiectați pentru algoritmi importanți (de exemplu, sortarea, FFT și multiplicarea matricei) pentru a deveni algoritmi optimi de uitare a memoriei cache - aceștia folosesc memoria cache într-un mod probabil optim, într-un sens asimptotic, indiferent de dimensiunea cache. În schimb, abordarea tradițională a utilizării memoriei cache este blocarea, ca în optimizarea buclei imbricate , în care sarcina este împărțită în mod explicit în bucăți de dimensiune adecvată - aceasta poate folosi și cache-ul în mod optim, dar numai atunci când algoritmul este reglat pentru o anumită dimensiune cache. a unei anumite mașini.

Același avantaj există și pentru alte sisteme de stocare ierarhice, cum ar fi NUMA sau memoria virtuală , și pentru mai multe niveluri de cache: odată ce o subproblemă este suficient de mică, poate fi rezolvată în acel nivel al ierarhiei, fără acces la niveluri mai înalte (mai lent) .

Probleme de aplicare

Recursiune

Algoritmii Divide and Conquer sunt aplicați în mod natural sub formă de metode recursive . În acest caz, subsarcinile private care conduc la cea în curs de rezolvare sunt stocate automat în stiva de apeluri de procedură . O funcție recursivă este o funcție numerică a unui argument numeric care se conține în notația sa.

Stivă explicită

Algoritmii Divide and Conquer pot fi aplicați și de un program nerecursiv care stochează subprobleme private într-o structură de date explicită, cum ar fi o stivă , o coadă sau o coadă de prioritate . Această abordare permite mai multă libertate în alegerea subproblemei care trebuie rezolvată în continuare. O caracteristică care este importantă în unele aplicații - de exemplu, în metoda de ramificare și conectare pentru optimizarea funcțiilor. Această abordare este, de asemenea, standard în limbajele de programare care nu oferă suport pentru proceduri recursive.

Dimensiunea stivei

În implementările recursive ale algoritmilor Divide and Conquer, trebuie să vă asigurați că este alocată suficientă memorie pentru stiva recursive, altfel execuția poate eșua din cauza depășirii stivei . Algoritmii Divide and Conquer care sunt eficienti în timp au adesea adâncimi de recursivitate relativ mici. De exemplu, un algoritm de sortare rapidă poate fi implementat în așa fel încât să nu necesite niciodată mai mult de log2 n apeluri recursive imbricate pentru a sorta n elemente.

Depășirile de stivă pot fi dificil de evitat atunci când se utilizează rutine recursive, deoarece mulți compilatori presupun că stiva de recursivitate este contiguă în memorie, iar unii alocă o cantitate fixă ​​de spațiu pentru aceasta. De asemenea, compilatorii pot stoca mai multe informații pe stiva recursive decât este strict necesar, cum ar fi adresa de retur, parametrii imuați și variabilele interne ale procedurilor. Astfel, riscul de depășire a stivei poate fi redus prin minimizarea parametrilor și variabilelor interne ale procedurii recursive sau prin utilizarea unei structuri explicite a stivei.

Alegerea opțiunilor de bază

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

Alegerea celor mai mici sau mai simple cazuri de bază posibile este mai elegantă și are ca rezultat, de obicei, programe mai simple, deoarece sunt mai puține cazuri de luat în considerare și mai ușor de rezolvat. De exemplu, FFT poate opri recursiunea atunci când intrarea este o singură mostră, iar algoritmul de sortare rapidă pentru o listă se poate opri când intrarea este o listă goală; în ambele exemple există un singur caz de bază de luat în considerare și nu trebuie procesat.

Pe de altă parte, eficiența este adesea îmbunătățită dacă recursiunea se oprește la cazuri de bază relativ mari și acestea sunt rezolvate nerecursiv, rezultând un algoritm hibrid . Această strategie evită suprapunerea apelurilor recursive care lucrează puțin sau deloc și poate permite, de asemenea, utilizarea algoritmilor specializați nerecursivi care, pentru aceste cazuri de bază, sunt mai eficienți decât recursiunea explicită. Procedura generală pentru un algoritm recursiv hibrid simplu este de a scurtcircuita cazul de bază, cunoscut și sub numele de recursivitate la distanță de braț . În acest caz, înainte de a apela funcția, se verifică dacă următorul pas va duce la registrul de bază, evitând un apel inutil de funcție. Deoarece algoritmul Divide and Conquer reduce în cele din urmă fiecare instanță a unei probleme sau subprobleme la un număr mare de instanțe de bază, ele domină adesea eficiența generală a algoritmului, mai ales atunci când suprasarcina de împărțire/unire este scăzută. Mai mult, aceste considerații nu depind de dacă recursiunea este implementată de compilator sau de o stivă explicită.

Astfel, de exemplu, multe aplicații de bibliotecă de sortare rapidă se vor transforma într-un algoritm simplu de sortare prin inserție bazat pe buclă (sau similar) de îndată ce numărul de elemente de sortat este suficient de mic. În plus, dacă o listă goală ar fi singurul caz de bază, atunci sortarea unei liste cu n intrări ar avea ca rezultat un număr maxim de n apeluri de sortare rapidă 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 „nu face nimic” și, mai general, cazul de bază mai mare de 2 este de obicei folosit pentru a reduce proporția de timp petrecut cu lucrările menajere sau manipularea stivei.

Alternativ, pot fi utilizate cazuri de bază mari, care încă folosesc algoritmul Divide and Conquer, dar implementează algoritmul pentru un set predefinit de dimensiuni fixe, unde algoritmul poate fi extins complet în cod care nu are recursivitate, bucle sau convenții (asociate cu metoda de evaluare parțială ). De exemplu, această abordare este utilizată în unele aplicații eficiente FFT, în care cazurile de bază sunt implementări extinse ale algoritmilor FFT Divide and Conquer pentru un set de dimensiuni fixe. [9] Tehnicile de generare a codului sursă pot fi folosite pentru a genera numărul mare de cazuri de bază distincte dorite pentru a implementa eficient această strategie.

O versiune generalizată a acestei idei este cunoscută sub numele de recursivitate „extindere” sau „creștere” și au fost propuse diferite metode pentru a automatiza procedura de extindere a cazului de bază. [9]

Partajarea subsarcinilor recurente

Pentru unele sarcini, recursiunea ramificată poate duce la mai multe evaluări ale aceleiași subsarcini. În astfel de cazuri, ar putea fi utilă identificarea și stocarea soluțiilor la aceste subprobleme suprapuse, o tehnică cunoscută în mod obișnuit sub numele de memorare . Urmând până la limită, acest lucru duce la algoritmi Divide and Conquer de jos în sus, cum ar fi programarea dinamică și analizarea diagramelor .

Vezi și

Note

  1. ↑ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introducere în algoritmi  (neopr.) . - MIT Press , 2009. - ISBN 978-0-262-53305-8 .
  2. ↑ Brassard, G. și Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.
  3. ↑ Anany V. Levitin, Introducere în proiectarea și analiza algoritmilor (Addison Wesley, 2002).
  4. ↑ 1 2 3 Donald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching , ediția a doua (Addison-Wesley, 1998).
  5. ↑ Heideman, MT, DH Johnson și CS Burrus, „ Gauss and the history of the fast Fourier transform Arhivat la 31 iulie 2020 la Wayback Machine ”, IEEE ASSP Magazine, 1, (4), 14–21 (1984).
  6. ↑ Donald Knuth . Arta programarii computerelor : Volumul 3 Sortarea si cautarea  . - 1998. - P. 159. - ISBN 0-201-89685-0 .
  7. ↑ Karatsuba, Anatolii A. ; Yuri P. Ofman . Înmulțirea numerelor cu mai multe valori pe automate  (neopr.)  // Rapoarte ale Academiei de Științe . - 1962. - T. 146 . - S. 293-294 . Tradus în Înmulțirea numerelor cu mai multe cifre pe automate   // Fizica sovietică Doklady : jurnal. - 1963. - Vol. 7 . - P. 595-596 .
  8. ↑ M. Frigo; CE Leiserson; H. Prokop. Algoritmi cache-oblivious  (neopr.)  // Proc. Al 40-lea Symp. pe bazele informaticii. — 1999.
  9. ↑ 1 2 Frigo, M.; Johnson, SG  Proiectarea și implementarea FFTW3  // Proceedings of IEEE : jurnal. - 2005. - Februarie ( vol. 93 , nr. 2 ). - P. 216-231 . - doi : 10.1109/JPROC.2004.840301 .

Literatură

Link -uri