Divide Y Venceras

Páginas: 21 (5175 palabras) Publicado: 16 de enero de 2013
Capitulo 2 La técnica Divide y Vencerás

Introducción Divide y Vencerás es una técnica para diseñar algoritmos que consiste en descomponer el caso del problema que queremos resolver en un número de subproblemas menores del mismo problema, resolviendo sucesiva e independientemente cada uno de ellos mediante un algoritmo que suponemos existe, al que en lo sucesivo referiremos como “básico”, ydespués combinando las soluciones así obtenidas de modo que se obtenga la solución del problema inicial. Si el problema de partida lo notamos P, {PBiB , i∈I} representa la colección de subproblemas en la que dividimos P, {SiB , i∈I} la de sus correspondientes soluciones y S la combinación de esas soluciones de los subproblemas, el siguiente diagrama refleja como se desarrollaría un algoritmo Divide yVencerás

A pesar de la sencillez del método que describe este esquema, el desarrollo del mismo no esta exento de dificultades, ya que hay diferentes escollos que deberemos tener previsto superar. Así, por ejemplo, es natural esperar que todos los subproblemas sean de la misma naturaleza entre si, y q ue además esta coincida con la de P. Pero nada hay seguro acerca del numero de subproblemas enel que deberemos dividir P. Solo hay datos basados en la experiencia que indican que la técnica Divide y Vencerás funciona mejor con un numero pequeño de subproblemas que con uno grande. Tampoco sabemos nada sobre el tamaño que deberán tener los subproblemas. La practica del Divide y Vencerás recomienda que cuanto mas parecidos sean los tamaños de los subproblemas, mejor funciona el algoritmo.Pero no hay ningún resultado teórico que demuestre que este hecho siempre conduce a buenos resultados. En este punto es necesario destacar que cuando hablamos de dividir el problema en subproblemas, no estamos diciendo que esa división tenga que ser exacta y exhaustiva (lo que llamaríamos una partición) sino, mas bien, que consideramos subproblemas de P, sin que ello suponga que la unión de todosellos deba reproducir exactamente P. Podría pasar que la unión de todos los subproblemas reprodujera P, pero lo mas normal será que de esa unión obtengamos algo mas que P. Entonces, supuesto que sabemos cuantos subproblemas tendremos y que tamaño tendrán estos, deberemos saber resolverlos, es decir, hallar las soluciones Si, i∈I, y lo que no es menos fácil, que podamos combinarlas entre si paraobtener una solución S que tenga sentido. Junto con todo eso, hay que confiar en que S se corresponda con la solución verdadera de P, y finalmente que todo este diagrama secuencial de pasos proporcione un algoritmo mas eficiente que el básico que suponemos tenemos para resolver los subproblemas, y por tanto valido para resolver P si hemos dicho que aquellos deben ser de la misma naturaleza que este.Bien, pues a pesar de todas estas dificultades y ambigüedades, cuando esta técnica puede aplicarse, proporciona algoritmos altamente eficaces. Comprobaremos esto con la siguiente ilustración. Supongamos que queremos resolver determinado problema P, y que para ello disponemos de un cierto algoritmo B (básico) de orden cuadrático, es decir, que una cierta implementación de B nos proporciona un tiempo tB (n) = bn2 para resolver un caso de tamaño n. Supongamos ahora que descubrimos que sería posible resolver tal caso descomponiéndolo en tres subcasos de tamaños n/2, resolviéndolos y combinando los resultados. Supongamos que la descomposición y la combinación de las soluciones parciales podemos llevarla a cabo mediante un algoritmo C que es lineal, es decir, de tiempo, tc(n) = kn para unacierta implementación y determinada constante k. Usando a la vez el algoritmo básico inicial B y esta nueva idea, obtenemos un nuevo algoritmo N cuya implementación consume un tiempo. tN (n) = 3tB(n/2) + tc(n) = 3b(n/2)2 + kn = (3/4)bn2 + kn El término (3/4)bn2 domina cuando n es suficientemente grande, lo que significa que el algoritmo N es esencialmente un 25% más rápido que el algoritmo básico...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • divide y venceras
  • divide y venceras
  • Divide y venceras
  • Divide Y Venceras
  • divide y venceras
  • Las torres de Hanoi, divide y venceras
  • Guia divide y vencerás
  • Divide y vencerás en programacion

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS