subproblemas

Subproblemas es un término utilizado en la informática y las matemáticas para describir instancias más pequeñas de un problema original, obtenidas al dividirlo en partes. Cada subproblema mantiene la misma estructura general del problema inicial y puede resolverse de forma independiente o con dependencias respecto a otros subproblemas. Resolver los subproblemas permite construir la solución global de forma incremental.

En el diseño de algoritmos, muchos problemas se abordan mediante la resolución de subproblemas. Las relaciones de recurrencia describen cómo se combinan las soluciones de subproblemas para formar la solución del problema mayor. Dos enfoques comunes son dividir para vencer (divide and conquer), que reparte el problema en subproblemas independientes y luego une sus soluciones, y la programación dinámica, que aprovecha subproblemas que se repiten y almacena sus resultados para evitar recomputaciones.

Propiedades relevantes de los subproblemas incluyen que deben ser más simples o pequeños que el problema original y, a menudo, que la solución del problema depende del resultado de varios subproblemas. En la programación dinámica, los subproblemas suelen superponerse, lo que justifica el uso de memoización o tabulación para almacenar soluciones intermedias. En cambio, en estrategias como divide y vencer, los subproblemas suelen resolverse de forma independiente y de manera recursiva.

Ejemplos comunes ilustran el concepto. La secuencia de Fibonacci, cuando se resuelve de forma recursiva, genera muchos subproblemas repetidos; la programación dinámica soluciona cada uno solo una vez. En ordenamiento, mergesort divide el arreglo en subproblemas de menor tamaño y luego fusiona sus soluciones. Otros problemas de rutas óptimas o de mochila también se modelan mediante el uso de subproblemas para construir soluciones globales.