OpcionesEs una técnica muy extendida gracias a su sencillez. Su aproximación es bastante intuitiva, si un problema es demasiado grande se descompone en partes de menor tamaño y más sencillas de resolver. Podremos aplicar esta técnica siempre
que la "instancia" del problema se pueda dividir en subinstancias de menor tamaño.
¿En qué consiste esta técnica?
- Se divide el problema en subproblemas. Por eficiencia debemos intentar que los subproblemas tengan un tamaño similar. Si es posible resolver el problema, porque este es indivisible, se resuelve directamente
- Se resuelve el problema para cada una de las instancias más pequeñas
- Se combinan las soluciones obtenidas para obtener una solución global
La principal ventaja de esta técnica es su sencillez. Sin embargo no siempre obtendremos una solución óptima, aunque en muchas ocasiones será eficiente.
Veamos un ejemplo de aplicación de esta técnica para calcular la suma de los n primeros números naturales (1, 2, 3, ..., n):
Nos hemos ayudado de una función auxiliar, suma_aux, que suma los números existentes en un intervalo dado. Para divide el intervalo por su punto medio. Si no se puede dividir el intervalo se devuelve el valor ínfimo. Sería
el caso del intervalo [2,2], donde se devolvería el 2. En otro caso se resolvería el problema más pequeño de calcular la suma de los intervalos más pequeños. Por último se combinarían las soluciones de los problemas más pequeños
sumándolas:
