Cuando se trata del diseño de algoritmos, a menudo se emplean las siguientes técnicas:
- Programación dinámica
- La codiciosa estrategia
- Divide y conquistaras
Si bien para los primeros dos métodos, existen fundamentos teóricos bien conocidos, a saber, el Principio de Optimidad de Bellman y la teoría matroide (resp. Greedoid), no pude encontrar un marco tan general para algoritmos basados en D&C.
En primer lugar, soy consciente de algo que nosotros (o más bien, el profesor) introdujimos en una clase de programación funcional, llamada "esqueleto algorítmico", que surgió en el contexto de los combinadores. Como ejemplo de esto, le dimos un esqueleto para algoritmos de D&C de la siguiente manera:
Definición : Sean conjuntos no vacíos. Llamamos a los elementos de las soluciones , y los elementos de (es decir, los subconjuntos de ) se denominan problemas . Entonces, un esqueleto D y C es una tupla de 4 , donde:
- es un predicado sobre el conjunto de problemas y decimos que un problema es básico si se cumple .
- es un mapeo que asigna una solución a cada problema básico.
- es un mapeo que divide cada problema en un conjunto de subproblemas.
- es un mapeo que une las soluciones (dependiendo del tipo de "problema de pivote") de los subproblemas para producir una solución.
Luego, para un esqueleto dado y un problema , la siguiente función genérica calcula una solución (en el formal sentido) para :
donde en la segunda línea usamos la notación para los subconjuntos del codominio de un mapeo .
Sin embargo, no examinamos más a fondo las propiedades "estructurales" subyacentes de los problemas que pueden formularse de esta manera (como dije, era una clase de programación funcional y esto era solo un pequeño ejemplo). Lamentablemente, no pude encontrar más referencias sobre este mismo enfoque. Por lo tanto, no creo que las definiciones anteriores sean bastante estándar. Si alguien reconoce lo que he dicho anteriormente, estaría encantado de los artículos relacionados.
En segundo lugar, para la estrategia codiciosa tenemos el famoso resultado de que el algoritmo codicioso general resuelve correctamente un problema si y solo si sus soluciones constituyen un matroide ponderado. ¿Existen resultados similares para los algoritmos D y C (no necesariamente basados en el método descrito anteriormente)?
fuente