Algoritmo divide e vencerás

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 baséase 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.

Deseño e posta en funcionamento

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)

Con todo, este tipo de algoritmos tamén se poden programar 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.

Vantaxes

Resolución de problemas complexos

Este modelo algorítmico é unha ferramenta potente para solucionar problemas complexos, tales 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 noutros máis sinxelos ata chegar a uns subproblemas sinxelos (tamén chamados casos base). 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.

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 base 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 tales 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.

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.

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é-esquecediza, esquecediza 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, tales 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.

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 de programación: con casos base o suficientemente grandes, redúcense os gastos indirectos da repetición das chamadas.

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.