Algorisme divideix i venceràs: diferència entre les revisions

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 [[Algorisme|algorítmic.]] El mètode es basa en la resolució [[Recursivitat|recursiva]] d'un problema dividint-lo en dos o més subproblemassubproblemes d'igual tipus o similar. El procés continua fins que els subproblemes arriben a ser prou senzills com perquè es resolguin directament. Al final, les solucions a cadascun dels subproblemassubproblemes es combinen per donar la solució del problema original.

La cerca binària, un tipic algorisme de divideix i venceràs en el qual el problema original és parteix successivament en subproblemassubproblemes 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 d'Euclides|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.

# En primer lloc ha de plantejar-se el problema de forma que aquest es pugui descompondre en k subproblemassubproblemes 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 subproblemassubproblemes (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 subproblemassubproblemes, ja sigui directament si són elementals o bé de forma recursiva. El fet que la grandària dels subproblemassubproblemes sigui estrictament menor que la grandària original del problema ens garanteix la convergència cap als casos elementals, també anomenats casos base.

Els algorismes de “divideix i venceràs” s'implementen de forma natural, com a processos [[Recursivitat|recursius.]] En aquest cas, els subproblemassubproblemes parcials encapçalats per aquells que ja han estat resolts s'emmagatzemen a la pila de crides de procediments.

Els algorismes de divideix i venceràs també poden ser implementats mitjançant un programa no recursiu que emmagatzemi els subproblemassubproblemes parcials en alguna estructura de dades explícita, tal com una [[Memòria en pila (estructura de dades)|pila]], una cua, o una [[Cua (estructura de dades)|cua]] de prioritat. Aquest enfocament permet més llibertat a l'hora de triar els subproblemassubproblemes 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 subproblemassubproblemes. Aquest enfocament és també la solució estàndard en llenguatges de programació que no permeten procediments recursius.

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

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 subproblemassubproblemes, 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.