Algorisme divideix i venceràs

En el camp de les ciències de la computació, el terme divideix i venceràs (DiV) fa referència a un dels paradigmes més importants de disseny algorítmic. El mètode es basa en la resolució recursiva d'un problema dividint-lo en dos o més subproblemes d'igual tipus o similar. El procés continua fins que els subproblemes arriben a ser prou senzills perquè es resolguin directament. Al final, les solucions de cadascun dels subproblemes es combinen per donar la solució del problema original.

La denominació s'inspira amb la locució llatina divide et impera, una estratègia política popular des de l'edat antiga: qui vol vèncer un poble enemic o un adversari fort ha de dedicar-se a dividir-lo.

Aquesta tècnica és la base dels algorismes eficients per gairebé qualsevol tipus de problema com, per exemple, algorismes d'ordenació (quicksort, mergesort, entre molts altres), multiplicació nombres grans (Karatsuba), anàlisis sintàctiques (anàlisi sintàctica top-down), la transformada discreta de Fourier etc.

D'altra banda, analitzar i dissenyar algorismes de DIV es una tasca que porta temps dominar-la. De la mateixa forma que en la inducció, a vegades és necessari substituir el problema original per un de més complex per aconseguir realitzar la recursió, i no hi ha un mètode sistemàtic general.

El nom divideix i venceràs també s'aplica de vegades a algorismes que redueixen cada problema a un únic subproblema, com la cerca binària per trobar un element en una llista ordenada (o el seu equivalent en computació numèrica, l'algorisme de bisecció per a la cerca d'arrels). Aquests algorismes poden ser implementats més eficientment que els algorismes generals de “divideix i venceràs”; en particular, si s'utilitza una sèrie de recursions que converteixen l'algorisme en simples bucles. Sota aquesta àmplia definició però, cada algorisme que utilitza recursió o bucles es pot prendre com un algorisme de “divideix i venceràs”. El nom decrementa i venceràs ha estat proposat per a la subclasse simple de problemes.

La correcció d'un algorisme de “divideix i venceràs”, es demostra habitualment per mitjà de l'inducció matemàtica, i el seu cost computacional es determina resolent relacions de recurrència.

Precedents històrics La cerca binària, un tipic algorisme de divideix i venceràs en el qual el problema original és parteix successivament en subproblemes més simples de més o menys la meitat de la grandària, té una llarga història. La idea d'utilitzar una llista ordenada d'objectes per facilitar la seva cerca data de l'antiga Babilònia al 200 a. C., mentre que una descripció de l'algorisme en ordinadors va aparèixer al 1946 en un article de John Mauchly. Un altre algorisme de “divideix i venceràs” amb un únic subproblema és l'algorisme d'Euclides per computar el màxim comú divisor de dos nombres (mitjançant reducció de nombres a problemes equivalents cada vegada més petits), que data de molts segles abans de Crist.

Un exemple antic d'algorisme de “divideix i venceràs” amb múltiples subproblemes és la descripció realitzada per Gauss el 1805 d'un algorisme que ara s'anomena algorisme de la ràpida transformació de FourierCooley-Tukey (FFT), encara que Gauss no va analitzar el seu conjunt d'operacions quantitativament i els FFT no es van difondre fins que es van redescobrir gairebé un segle després.

Un altre problema antic de “divideix i venceràs” de 2 subdivisions que va ser específicament desenvolupat per a ordinadors i analitzat adequadament és l'algorisme de merge-sort, inventat per John von Neumann el 1945.

Un altre exemple notable és l'algorisme inventat per A. Karatsuba al 1960 que pot multiplicar dos nombres de n dígits en . L'algorisme va refutar la conjectura d'Andrei Kolmogórov de 1956 que deia que aquesta tasca requeria Ω(n2) operacions. Un altre exemple d'algorisme de divideix i venceràs que originalment no s'utilitzava en ordinador, es un mètode elaborat per Knuth, el qual habitualment s'utilitza en les oficines de correus per dirigir les cartes: les cartes s'ordenen en diferents boses en funció de la seva àrea geogràfica, cadascuna d'aquestes boses al seu torn s'ordena en diferents lots per subregiones més petites, i així successivament fins que són repartides. Aquest mètode està relacionat amb l'ordenació Radix, descrit per a les màquines d'ordenació de targetes perforades .

Disseny i implementació La resolució d'un problema mitjançant aquesta tècnica consta fonamentalment dels següents passos:

En primer lloc ha de plantejar-se el problema de forma que aquest es pugui descompondre en k subproblemes del mateix tipus, però de menor grandària. És a dir, si la grandària de l'entrada és n, hem d'aconseguir dividir el problema en k subproblemes (on 1 ≤ k ≤ n), cadascun amb una entrada de grandària n/k i on 0 ≤ n/k < n. A aquesta tasca se la coneix com a divisió. En segon lloc han de resoldre's independentment tots els subproblemes, ja sigui directament si són elementals o bé de forma recursiva. El fet que la grandària dels subproblemes sigui estrictament menor que la grandària original del problema ens garanteix la convergència cap als casos elementals, també anomenats casos base. Finalment, s'han de combinar les solucions obtingudes al pas anterior per construir la solució del problema original.

Els algorismes divideix i venceràs (o divide and conquer, en anglès), es dissenyen com a procediments generalment recursivos. AlgorismeDiV (p: TipusProblema): TipusSolucio

if esCasBase(p) return resol(p)

else subproblemes: array of TipusProblema subproblemes = divideixEnSubproblemes(p) solucions_parcials: array of TipusSolucio

for each sp in subproblemes solucions_parcials.push_back(AlgorismeDiV(sp)) endFor

return mescla(solucions_parcials)

endIf

fiAlgorismeDiV Pel fet d'utilitzar un disseny recursiu, els algorismes dissenyats mitjançant la tècnica de Divideix i Venceràs heretaran els avantatges i inconvenients que la recursión planteja:

D'una banda el disseny que s'obté sol ser simple, clar, robust i elegant, la qual cosa equival a una major llegibilitat, facilitat de depuració i manteniment del codi obtingut. D'altra banda, els dissenys recursivos comporten normalment un major temps d'execució que els iteratius, a més de la complexitat espacial que pot representar l'ús de la pila de recursió.

Tot i així, aquest tipus d'algorismes també poden ser implementa com un algorisme no recursivo que emmagatzemi les solucions parcials en una estructura de dades explícita, com pot ser una pila, cua, o cua de prioritat. Aquesta aproximació permet una major llibertat al dissenyador, de forma que es pugui escollir quin subproblema és el que es resoldrà a continuació, la qual cosa pot ser important en el cas d'utililitzar tècniques com a Ramificació i acotació o d'optimització.

Recursió Els algorismes de “divideix i venceràs” s'implementen de manera natural, com a processos recursius. En aquest cas, els subproblemes parcials encapçalats per aquells que ja han estat resolts s'emmagatzemen a la pila de crides de procediments.

Pila explícita Els algorismes de divideix i venceràs també poden ser implementats mitjançant un programa no recursiu que emmagatzemi els subproblemes parcials en alguna estructura de dades explícita, tal com una pila, una cua, o una cua de prioritat. Aquest enfocament permet més llibertat a l'hora de triar els subproblemes a resoldre després, una característica que és important en algunes aplicacions, per exemple en la cerca en amplada i en el mètode de ramificació i poda per a optimització de subproblemes. Aquest enfocament és també la solució estàndard en llenguatges de programació que no permeten procediments recursius.

Grandària de la pila En implementacions recursives d'algorismes de DiV, ha d'assegurar-se que hi ha suficient memòria lliure per la pila de recursió, sinó l'execució pot fallar per desbordament de la pila. Afortunadament, els algorismes DiV que són eficients temporalment tenen una profunditat recursiva relativament petita. Per exempe, l'algorisme quicksort pot ser implementat de forma que mai requereix més de crides recursives per ordenar n elements.

Els desbordaments de pila podrien ser difícils d'evitar quan utilitzem procediments recursius, on molts compiladors assumeixen que la pila de recursió és una zona contigua de memòria, i alguns assignen una quantitat d'espai determinada per a tal fi. Els compiladors poden també desar a la pila de recursió, més informació que l'estrictament necessària, tal com l'adreça de tornada, paràmetres invariables, i les variables internes del procediment. Així, el risc de desbordament de pila pot ser reduït mitjançant la minimització de paràmetres i variables internes dels procediments recursivos, o utilitzant una estructura de pila explícita.

Triar els casos base En qualsevol algorisme recursiu, hi ha una llibertat considerable per triar els casos base, que són els subproblemes petits que són resolts directament per acabar amb la recursió.

Triar els casos base més petits i simples possibles és més elegant i normalment permet obtenir programes més simples, perquè hi ha menys casos a considerar i són més fàcils de resoldre. Per exemple, un algorisme FFT podria parar la recursió quan l'entrada és una mostra simple, i l'algorisme quicksort d'ordenació podria parar quan l'entrada és una llista buida. En tots dos casos, només cal considerar un cas base, i no requereix processament.

D'altra banda, l'eficiència normalment millora si la recursió s'atura en casos relativament grans, i aquests són resolts no recursivament. Aquesta estratègia evita la sobrecàrrega de crides recursivas que fan poc o cap treball, i poden també permetre l'ús d'algorismes especialitzats no recursius que, en el cas d'aquests casos base, són més eficients que la recursió explícita. Ja que un algorisme de DiV redueix cada instància del problema o subproblema a un gran nombre d'instàncies base, aquestes habitualment dominen el cost general de l'algorisme, especialment quan la sobrecàrrega de separació/unió és baixa. Vegeu que aquestes consideracions no depenen de si la recursió està implementada per compilador o per pila explícita.

Compartir subproblemes repetits En alguns problemes, la recursió ramificada podria acabar avaluant el mateix subproblema moltes vegades. En aquests casos valdria la pena identificar i desar les solucions d'aquests subproblemes solapats, una tècnica comunament coneguda com a memoització. Aquesta tècnica portada al límit, ens porta a algorismes de “divideix i venceràs” de bottom-up tals com la programació dinàmica i anàlisi gràfica. EDF

Avantatges Resolució de problemes complexos Aquest model algorítmic és una eina potent per solucionar problemes complexos, tals com el clàssic joc de les Torres de Hanoi. Tot el que necessita aquest algorisme és dividir el problema en subproblemes més senzills, i aquests en uns altres de més senzills fins a arribar a uns subproblemes senzills que s'anomenen casos base. Una vegada aquí, es resolen i es combinen els subproblemes en ordre invers al seu inici. Com dividir els problemes és, sovint, la part més complexa de l'algorisme. Per això, en molts problemes, el model només ofereix la solució més senzilla, no la millor.

Eficiència de l'algorisme