Agoritmo divide e vencerás

Na Galipedia, a wikipedia en galego.

Na cultura popular, divide e vencerás fai referencia a un refrán que implica resolver un problema difícil, dividíndoo en partes máis simples tantas veces como sexa necesario, ata que a resolución das partes tórnase obvia. A solución do problema principal constrúese coas solucións atopadas.

Nas ciencias da computación, o termo divide e vencerás (DYV) fai referencia a un dos máis importantes paradigmas de deseño algorítmico. O método está baseado na resolución recursiva dun problema dividíndoo en dous ou máis subproblemas de igual tipo ou similar. O proceso continúa ata que estes chegan a ser o suficientemente sinxelos como para que se resolvan directamente. Ao final, as solucións a cada un dos subproblemas combínanse para dar unha solución ao problema orixinal. Esta técnica é a base dos algoritmos eficientes para case calquera tipo de problema como, por exemplo, algoritmos de ordenamento (quicksort, mergesort, entre moitos outros) e a transformada discreta de Fourier.

[editar] Deseño e implementación

Os algoritmos divide e vencerás (ou divide and conquer, en inglés), deséñanse como procedementos xeralmente recursivos.

AlgoritmoDYV(p: TipoProblema): TipoSolucion
 
    IF esCasoBase(p)
       return resolve(p)
 
    ELSE
       subproblemas: ARRAY OF TipoProblema
       subproblemas = divideEnSubproblemas(p)
       solucións_parciais: ARRAY OF TipoSolucion
 
       FOR EACH sp IN subproblemas
          solucións_parciais.push_back(AlgoritmoDYV(sp))
 
       return mestura(solucións_parciais)

k Con todo, este tipo de algoritmos tamén se poden implementar como un algoritmo non recursivo que almacene as solucións parciais nunha estrutura de datos explícita, como pode ser unha pila, cola, ou cola con prioridade. Esta aproximación dá maior liberdade ao deseñador, de forma que se poida escoller que subproblema é o que se vai a resolver a continuación, o que pode ser importante no caso de usar técnicas como Ramificación e anotación ou de optimización.

[editar] Vantaxes

[editar] Resolución de problemas complexos

Este modelo algorítmico é unha ferramenta potente para solucionar problemas complexos, talles como o clásico xogo das torres de Hanoi. Todo o que necesita este algoritmo é dividir o problema en subproblemas máis sinxelos, e estes en outros máis sinxelos ata chegar a uns subproblemas sinxelos (tamén chamados casos basee). Unha vez aí, resólvense e combínanse os subproblemas en orde inversa ao seu inicio. Como dividir os problemas é, a miúdo, a parte máis complexa do algoritmo. Por iso, en moitos problemas, o modelo só ofrece a solución máis sinxela, non a mellor.

[editar] Eficiencia do algoritmo

Normalmente, esta técnica proporciona unha forma natural de deseñar algoritmos eficientes. Por exemplo, se o traballo de dividir o problema e de combinar as solucións parciais é proporcional ao tamaño do problema (n); ademais, hai un número limitado p de subproblemas de tamaño aproximadamente igual a n/p en cada etapa; e para rematar, os casos basee requiren un tempo constante (Ou(1)); entón o algoritmo divide e vencerás ten por cota superior asintótica a Ou(nlogn). Esta cota é a que teñen os algoritmos divide e vencerás que solucionan problemas talles como ordenar e a transformada discreta de fourier. Ambos os procedementos reducen a súa complexidade, anteriormente definida por Ou(n²). Para terminar, cabe destacar que existen outros enfoques e métodos que melloran estas cotas.

[editar] Paralelismo

Este tipo de algoritmos adáptase de forma natural á execución en contornas multiprocesador, especialmente en sistemas de memoria compartida onde a comunicación de datos entre os procesadores non necesita ser planeada por adiantado, polo que subproblemas distintos pódense executar en procesadores distintos.

[editar] Acceso a memoria

Os algoritmos que seguen o paradigma Divide e vencerás, tenden naturalmente a facer un uso eficiente das memorias cachés. A razón é que unha vez que un subproblema é o suficientemente pequeno, el e todos os seus subproblemas pódense, en principio, solucionar dentro desa caché, sen ter acceso á memoria principal, que é da orde de decenas de veces máis lenta. Un algoritmo deseñado para aproveitar a memoria caché deste xeito chámase modelo caché-olvidadiza, olvidadiza porque non contén o tamaño da memoria como parámetro explícito. Por outra banda, estes algoritmos pódense deseñar para moitos problemas importantes, talles como ordenación, a multiplicación de matrices, de maneira que se faga un uso óptimo da caché. En contraste, o achegamento tradicional para explotar a caché é facer bloques, desta forma, o problema divídese explicitamente nas partes de tamaños apropiados para que se poida utilizar ao caché de forma óptima, pero soamente cando o algoritmo é mellorado para o tamaño específico da caché dunha máquina particular. A mesma vantaxe existe no que respecta a outros sistemas xerárquicos de memoria, por exemplo NUMA ou memoria virtual, así como para niveis múltiples de caché: unha vez que un subproblema é suficientemente pequeno, pode ser solucionado dentro dun nivel dado da xerarquía, sen ter que acceder ao máis alto (máis lento).

Con todo, a clase de optimalidad asintótica descrita aquí, análoga a notación Ou maiúscula, non fai caso de factores constantes, e o engadir melloras adicionais específicas da máquina e caché non é un requirimento para alcanzar o óptimo nun sentido absoluto.

[editar] Desvantaxes

A principal desvantaxe deste método é a súa lentitude na repetición do proceso recursivo: os gastos indirectos das chamadas recursivas á resolución dos subproblemas, xunto co feito de ter que almacenar a pila de chamadas (o estado en cada punto na repetición), poden empeorar calquera mellora ata entón lograda. Esta tara, con todo, depende do estilo da implementación: con casos basee o suficientemente grandes, redúcense os gastos indirectos da repetición das chamadas.

[editar] Exercicios

• Multiplicación de Enteiros Grandes: algoritmo eficiente para multiplicar números de tamaño considerable, que se saen dos límites de representación, e non abordable cos algoritmos clásicos debido ao excesivo custo.
• Subvector de suma máxima: Algoritmo eficiente para atopar subcadenas dentro dun vector evitando ter que percorrer todo o vector desde cada posición.