Subestructura óptima

Question

Estoy tratando de obtener una imagen más completa del uso de la propiedad óptima de la subestructura en la programación dinámica, pero he pasado ciego sobre por qué tenemos que demostrar que CUALQUIER óptima solución al problema Contiene dentro de TI soluciones óptimas a los sub-problemas.

no sería suficiente mostrar que alguna solución óptima óptima al problema tiene esta propiedad, y luego usar esto para argumentar que, dado que la solución construida por nuestro algoritmo recursivo es al menos tan bueno como ¿Una solución óptima, será óptima? En otras palabras, no puedo detectar dónde, en el argumento de la corrección de nuestro algoritmo, necesitamos que todas las soluciones óptimas contengan soluciones óptimas a los submitros.

para aclarar:

La definición de CLRS de subestructura óptima dice que "un problema exhibe una subestructura óptima si la solución óptima al problema contiene en él soluciones óptimas a los subproblemes".

¿Por qué no sería suficiente decir que "un problema exhibe una subestructura óptima si la solución óptima óptima al problema contiene en él soluciones óptimas para los subproblemes"?

Answer 1

Me han molestado un poco por esto en mi investigación sobre algoritmos aproximados, que involucra programas dinámicos que encuentran soluciones aproximadamente óptimas. La forma correcta de pensar en la exactitud de los programas dinámicos, creo, es como una reducción (en la teoría de la complejidad) de un problema a un subproblema. Esta reducción a menudo se aplica de forma recursiva y con memoización, pero esas se detallan en este momento.

Deja que sea el problema y B sea el subproblem. Solo hay un subproblema porque podemos combinar múltiples subproblemas independientes en uno a través de un producto cartesiano generalizado. La reducción consiste en dos funciones: F, desde una instancia A a una instancia B, y H, de una solución B a una solución A. La propiedad de la corrección que necesitamos es que, para cada función G de cada instancia B a una solución B óptima correspondiente (el Oracle), la composición h. g. F es una función de cada instancia A a una solución A-óptima correspondiente. (Si H necesita acceso a la instancia A, luego extienda B para que sus instancias contengan una instancia A que se le debe copiar verbatim en la solución B correspondiente).

Para hacer su punto, para una instancia en particular y una solución A óptima, no existe un Oracle G de tal manera que la tubería h. g. f produce esa solución de la instancia dada. (En otras palabras, H no necesita ser Surjetivo). Por otro lado, H debe poder manejar cada solución B óptima posible de G para la instancia B construida por f.

Una estrategia común para garantizar que H sea correcta es encontrar una función de "subestructura" K de A-Solutions a B-Solutions y una forma de "empalmar" subestructura, es decir, una prueba de que, dada una solución A X y una solución B no peor que K (X), existe una solución A X 'No es peor que x tal que K (x')= y. Luego, se puede optimizar todo en la imagen inversa bajo K de su entrada. No es necesario que se aplique el empalme a todas las soluciones x, solo una óptima.

Answer 2

En la programación dinámica, dividimos el problema a los sub-problemas más pequeños, realizamos alguna manipulación y brinde respuesta a una respuesta más grande, muy similar al enfoque de recursión (y por ninguna coincidencia).

Ahora, cuando llegamos a demostrar formalmente la exactitud de dicho algoritmo, esto se hace por inducción. Probamos que nuestra 'cláusula base' es correcta (generalmente muy fácil), y luego asumimos que cualquier problema más pequeño que la actual, también es óptima. Luego usamos esta hipótesis para demostrar la exactitud del problema más grande.

Si no sabíamos que todas las soluciones son óptimas, no podríamos demostrar que usando el paso adicional, pudimos modificar una solución óptima a un problema más pequeño para una solución óptima a un problema más grande, simplemente no habría suficiente información para probar este reclamo.

Si sabíamos que algunos de los subproblemes son una solución óptima, no sería suficiente para garantizar que el uso de este subproblema, que tenemos una solución óptima para, de hecho, es el que necesitamos para obtener la solución óptima al problema más grande .

---

Eche un vistazo a Knapsack, por ejemplo, y echemos un vistazo a su paso DP:

f(x,i) = max(f(x-weight[i],i-1) +val[i], f(x,i-1))

Si sabíamos que solo uno de ellos es óptimo, no pudimos demostrar que el algoritmo es correcto, porque podríamos haber necesitado el caso "otro", donde no tenemos una solución óptima para.

Si elegimos f(x,i-1) en el max(), podría haber sido la opción incorrecta. Al garantizar que tenemos una solución óptima a todos los subproblemas, nos aseguramos de que esto no pueda suceder.