Disminuir y conquistar

Como ya se discutió el enfoque de divide y vencerás , que incluye los siguientes pasos:
Divide el problema en varios subproblemas que son instancias más pequeñas del mismo problema.
Conquista los subproblemas resolviéndolos recursivamente. Sin embargo, si los tamaños de los subproblemas son lo suficientemente pequeños, simplemente resuelva los subproblemas de una manera sencilla.
Combina las soluciones de los subproblemas en la solución del problema original.

De manera similar, el enfoque de disminuir y conquistar funciona, también incluye los siguientes pasos:
Disminuir o reducir la instancia del problema a una instancia más pequeña del mismo problema y ampliar la solución.
Conquista el problema resolviendo instancias más pequeñas del problema.
Extender la solución de una instancia más pequeña para obtener la solución al problema original.
La idea básica de la técnica de disminuir y conquistar se basa en explotar la relación entre una solución a una instancia dada de un problema y una solución a su instancia más pequeña. Este enfoque también se conoce como enfoque incremental o inductivo.

“Divide y vencerás” frente a “Disminuye y vencerás”:

Según Wikipedia , algunos autores consideran que el nombre “divide y vencerás” debe usarse solo cuando cada problema puede generar dos o más subproblemas. En cambio, se ha propuesto el nombre disminuir y conquistar para la clase de un solo subproblema. De acuerdo con esta definición, Merge Sort y Quick Sort se dividen y vencerán (porque hay 2 subproblemas) y la búsqueda binaria se reduce y vencerán (porque hay un subproblema).

Implementaciones de Reducir y Conquistar:

Este enfoque se puede implementar como de arriba hacia abajo o de abajo hacia arriba.

Enfoque de arriba hacia abajo: siempre conduce a la implementación recursiva del problema.
Enfoque ascendente: generalmente se implementa de manera iterativa, comenzando con una solución a la instancia más pequeña del problema.

Variaciones de Disminuir y Conquistar:

Hay tres variaciones principales de disminuir y conquistar:

1. Disminuir en una constante
2. Disminuir por un factor constante
3. Disminución de tamaño variable

Reducir por una constante : en esta variación, el tamaño de una instancia se reduce por la misma constante en cada iteración del algoritmo. Por lo general, esta constante es igual a uno, aunque ocasionalmente ocurren otras reducciones de tamaño constante. A continuación se muestran problemas de ejemplo:

• Tipo de inserción
• Algoritmos de búsqueda de grafos: DFS , BFS
• Clasificación topológica
• Algoritmos para generar permutaciones, subconjuntos

Reducir por un factor constante : esta técnica sugiere reducir una instancia de problema por el mismo factor constante en cada iteración del algoritmo. En la mayoría de las aplicaciones, este factor constante es igual a dos. Una reducción por un factor distinto de dos es especialmente rara.

Los algoritmos de disminución por un factor constante son muy eficientes, especialmente cuando el factor es mayor que 2, como en el problema de la moneda falsa. A continuación se muestran problemas de ejemplo:

• Búsqueda binaria
• Problemas con monedas falsas
• multiplicación campesina rusa

Disminución de tamaño variable : en esta variación, el patrón de reducción de tamaño varía de una iteración de un algoritmo a otra.
Como en el problema de encontrar mcd de dos números, aunque el valor del segundo argumento siempre es menor en el lado derecho que en el lado izquierdo, no disminuye ni por una constante ni por un factor constante. A continuación se muestran problemas de ejemplo:

• Cálculo de la mediana y problema de selección .
• Búsqueda de interpolación
• Algoritmo de Euclides

Puede haber un caso en el que el problema se pueda resolver mediante variaciones de disminución por constante y disminución por factor, pero las implementaciones pueden ser recursivas o iterativas. Las implementaciones iterativas pueden requerir más esfuerzo de codificación, sin embargo, evitan la sobrecarga que acompaña a la recursividad.

Referencia :
Anany Levitin
Disminuir y conquistar