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 $O(n^{\log _{2}3})$notable és l'algorisme inventat per A. Karatsuba al 1960 que pot multiplicar dos nombres de n dígits en $O(n^{\log _{2}3})$$O(n^{\log _{2}3})$$O(n^{\log _{2}3})$.$O(n^{\log _{2}3})$ 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:

1. 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ó.
2. 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.
3. 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 exemp$log_{2}n$e, l'algo$log_{2}n$risme quicksort pot ser implementat de forma que mai requereix més de $log_{2}n$${\textstyle log_{2}n}$ crides recursives per ordenar n elements.$log_{2}n$

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

Normalment, aquesta tècnica proporciona una forma natural de dissenyar algorismes eficients. Per exemple, si el treball de dividir el problema i de combinar les solucions parcials és proporcional a la grandària del problema (n); a més, hi ha un nombre limitat p de subproblemes de grandària aproximadament igual a n/p en cada etapa; i finalment, els casos base requereixen un temps constant (O(1)); llavors l'algorisme divideix i venceràs té per cota superior asimptòtica a O(nlogn). Aquesta cota és la que tenen els algorismes divideix i venceràs que solucionen problemes tals com ordenar i la transformada discreta de fourier. Tots dos procediments redueixen la seva complexitat, anteriorment definida per O(n2). Per acabar, cal destacar que existeixen altres enfocaments i mètodes que milloren aquestes cotes.

Quan s'efectua una anàlisi de l'eficiència d'aquest mètode, es troba que la decisió de com es divideixi el problema afecta l''ordre' O de la implementació. Si es divideix un problema de grandària n en p parts de grandària n/c cadascuna i considerant que hi ha un cost fix b depenent de n alhora de processar al final la unió de solucions, es té que el nombre d'operacions o temps de processament per a l'algorisme es pot expressar com a p vegades el temps que pren resoldre cada subproblema de grandària n/c més el corresponent cost fix b:

(1)${\begin{array}{l}T(n)=pT({\frac {n}{c}})+bn\\T(1)=b\end{array}}$

es considera un k tal que $n=c^{k}\Rightarrow$

(2)$T(n)=R(k)\Rightarrow {\begin{cases}R(k)=pR(k-1)+bc^{k}\\R(0)=b\end{cases}}$

substituint $S(k)={\frac {R(k)}{p^{k}}}$ s'obté...

(3)$\Rightarrow {\begin{cases}S(k)=S(k-1)+b({\frac {c}{p}})^{k}\\S(0)=b\end{cases}}$

$S(k)-S(k-1)=b({\frac {c}{p}})^{k}$

Aplicant un sumatori de 1 a k a tots dos costats...

$\sum _{i=1}^{k}{S(i)-S(i-1)}=\sum _{i=1}^{k}{b({\frac {c}{p}})^{i}}$

$S(k)-S(0)=S(k)-b=\sum _{i=1}^{k}{b({\frac {c}{p}})^{i}}$

$S(k)=b+\sum _{i=1}^{k}{b({\frac {c}{p}})^{i}}$

(3.1)$S(k)=\sum _{i=0}^{k}{b({\frac {c}{p}})^{i}}\Rightarrow$

$R(k)=p^{k}b\sum _{i=0}^{k}{({\frac {c}{p}})^{i}}={\frac {p^{k}}{c^{k}}}bc^{k}\sum _{i=0}^{k}{({\frac {c}{p}})^{i}}=bc^{k}\sum _{i=0}^{k}{({\frac {c}{p}})^{k-i}}=bc^{k}\sum _{i=0}^{k}{({\frac {c}{p}})^{i}}$

(4)$R(k)=bc^{k}\sum _{i=0}^{k}{({\frac {c}{p}})^{i}}$

Segons la relació entre c i p s'obtenen diferents 'ordres' per a l'algorisme:

Cas p < c: És a dir, si el problema es divideix en poques parts de gran mida cada una, llavors el sumatori (4) es O(1), ja que es pot aplicar directament la fórmula $\sum _{i=0}^{n-1}{a^{i}}={\frac {1-a^{n}}{1-a}}$ si a>1.

(5.1)$R(k)\approx O(bc^{k})\Rightarrow T(n)=O(n)$

Cas en que p == c:

(5.2)$R(k)=bkc^{k}\Rightarrow T(n)=O(n\log n)$

Cas p > c: En el qual el problema es divideix en moltes parts de mida 'relativament' petita, implica que el sumatori (4) es...

$\sum _{i=0}^{k}{({\frac {c}{p}})^{i}}={\frac {{({\frac {p}{c}})^{k+1}}-1}{({\frac {p}{c}})-1}}=O(({\frac {p}{c}})^{k})$

$R(k)={\frac {bc^{k}p^{k}}{c^{k}}}=bp^{k}$

(5.3)$T(n)=bp^{\log _{c}n}=bn^{\log _{c}p}\Rightarrow T(n)=O(n)$

En efecte, els algorismes de tipus Divideix i Vencerás están acotados per $O(n\log n)$ per a casos molt particulars en què p i c són similars, mentre que en general es pot considerar que són $O(n)$

Paral·lelisme

Aquest tipus d'algorismes s'adapta de manera natural a l'execució en entorns multiprocessador, especialment en sistemes de memòria compartida on la comunicació de dades entre els processadors no necessita ser planejada per endavant, per la qual cosa subproblemes diferents es poden executar en processadors diferents.

Accés a memòria

Els algorismes que segueixen el paradigma Divideix i venceràs, tendeixen naturalment a fer un ús eficient de les memòries cau. La raó és que una vegada que un subproblema és prou petit, ell i tots els seus subproblemes es poden, en principi, solucionar dins d'aquesta caché, sense necessitat d'accedir a la memòria principal, que és de l'ordre de desenes de vegades més lenta. Un algorisme dissenyat per aprofitar la memòria caché d'aquesta forma es diu model caché-oblidadissa, oblidadissa perquè no conté la grandària de la memòria com a paràmetre explícit. D'altra banda, aquests algorismes es poden dissenyar per a molts problemes importants, tals com ordenació, la multiplicació de matrius, de forma que es faci un ús òptim de la caché. En contrast, l'acostament tradicional per explotar la caché és fer blocs, d'aquesta forma, el problema es divideix explícitament en parts de grandàries apropiades perquè es pugui utilitzar al caché de forma òptima, però només quan l'algorisme és millorat per tal d'aprofitar la grandària específica de la caché d'una màquina particular. El mateix avantatge existeix pel que fa a altres sistemes jeràrquics de memòria, per exemple NUMA o memòria virtual, així com per a nivells múltiples de caché: una vegada que un subproblema és suficientment petit, pot ser solucionat dins d'un nivell cocret de la jerarquia, sense haver d'accedir al nivell més alt (més lent).

Tot i així, la classe d'optimalitat asimptòtica descrita aquí, anàloga a notació O majúscula, no fa cas de factors constants, i afegir millores addicionals específiques de la màquina i caché no és un requeriment per aconseguir l'òptim en un sentit absolut.

Control de l'arrodoniment

En computacions amb aritmètica arrodonida, per exemple amb els nombres en aritmètica flotant, un algorisme de divideix i venceràs podria donar resultats més exactes que un problema iteratiu equivalent. Per exemple, es poden sumar N nombres tant amb un bucle simple que suma cada dada a una variable simple, o mitjançant un algorisme de DiV que trenca el conjunt de dades en dues meitats, recursivamente computa cada suma i després uneix les 2 sumes. Mentre que el segon mètode realitza les mateixes sumes que el primer, i és més costós per les crides recursives, normalment és més exacte.

Desavantatges

El principal desavantatge d'aquest mètode és la seva lentitud en la repetició del procés recursiu: les despeses indirectes de les crides recursives per a la resolució dels subproblemes, juntament amb el fet d'haver d'emmagatzemar la pila de crides (l'estat en cada punt en la repetició), poden empitjorar qualsevol millora fins llavors assolida. Aquesta tasca, no obstant això, depèn de l'estil de la implementació: amb casos base prou grans, es redueixen les despeses indirectes de la repetició de les crides recursives.

Un altre desavantatge o inconvenient important, és la dificultat o fins i tot inconveniència d'aplicar el mètode a situacions en les quals la solució al problema general no es deriva de la suma directa i simple dels subproblemes (parts). Això es presenta per exemple quan són rellevants les interaccions o efectes mutus entre els subproblemes, la qual cosa genera nous subproblemes, en considerar cadascuna d'aquestes interaccions, incrementant exponencialment el nombre de subproblemes a considerar, en incrementar-se la complexitat de la situació general i dels seus components.

De manera similar, l'algorisme pot no ser aplicable quan les interaccions no es poden predir amb precisió.

Exemples

• Multiplicació d'enters grans: algorisme eficient per multiplicar nombres de grandària considerable, que sobrepassen els límits de representació, i no abordable amb els algorismes clàssics a causa de l'excessiu cost.
• Subvector de suma màxima: Algorisme eficient per trobar subcadenes dins d'un vector evitant haver de recórrer tot el vector des de cada posició.

Vegeu també

• Algorisme voraç
• Algorisme de Las Vegas
• Programació dinàmica