Diseño e implementación

venceras

La resolución de un problema mediante esta técnica consta fundamentalmente de los siguientes pasos:

En primer lugar ha de plantearse el problema de forma que pueda ser descompuesto en k subproblemas del mismo tipo, pero de menor tamaño. Es decir, si el tamaño de la entrada es n, hemos de conseguir dividir el problema en k subproblemas (donde 1 ≤ k ≤ n), cada uno con una entrada de tamaño n/k y donde 0 ≤ n/k < n. A esta tarea se le conoce como división.

En segundo lugar han de resolverse independientemente todos los subproblemas, bien directamente si son elementales o bien de forma recursiva. El hecho de que el tamaño de los subproblemas sea estrictamente menor que el tamaño original del problema nos garantiza la convergencia hacia los casos elementales, también denominados casos base.

Por último, combinar las soluciones obtenidas en el paso anterior para construir la solución del problema original.
Los algoritmos divide y vencerás (o divide and conquer, en inglés), se diseñan como procedimientos generalmente recursivos.

AlgoritmoDyV (p: TipoProblema): TipoSolucion
   
   if esCasoBase(p)
      return resuelve(p)
   
   else
      subproblemas: array of TipoProblema
      subproblemas = divideEnSubproblemas(p)
      soluciones_parciales: array of TipoSolucion
   
      for each sp in subproblemas
         soluciones_parciales.push_back(AlgoritmoDYV(sp))
      endFor
   
      return mezcla(soluciones_parciales)
   
   endIf
   
 finAlgoritmoDyV

 

Por el hecho de usar un diseño recursivo, los algoritmos diseñados mediante la técnica de Divide y Vencerás van a heredar las ventajas e inconvenientes que la recursión plantea:

  • Por un lado el diseño que se obtiene suele ser simple, claro, robusto y elegante, lo que da lugar a una mayor legibilidad y facilidad de depuración y mantenimiento del código obtenido.
  • Por contra, los diseños recursivos conllevan normalmente un mayor tiempo de ejecución que los iterativos, además de la complejidad espacial que puede representar el uso de la pila de recursión.

Sin embargo, este tipo de algoritmos también se pueden implementar como un algoritmo no recursivo que almacene las soluciones parciales en una estructura de datos explícita, como puede ser una pila, cola, o cola de prioridad. Esta aproximación da mayor libertad al diseñador, de forma que se pueda escoger qué subproblema es el que se va a resolver a continuación, lo que puede ser importante en el caso de usar técnicas como Ramificación y acotación o de optimización.

Fuente:
Colaboradores de Wikipedia. Algoritmo divide y vencerás [en línea]. Wikipedia, La enciclopedia libre. Disponible en <https://es.wikipedia.org/w/index.php?title=Algoritmo_divide_y_vencer>.