algorithm - geeksforgeeks - dynamic programming problems
¿Qué es la técnica de prueba de “cortar y pegar”? (4)
He visto referencias a pruebas de cortar y pegar en ciertos textos sobre análisis y diseño de algoritmos. A menudo se menciona en el contexto de la Programación Dinámica cuando se demuestra que la subestructura es óptima para un problema de optimización (consulte el Capítulo 15.3 CLRS). También se muestra en la manipulación de gráficos.
¿Cuál es la idea principal de tales pruebas? ¿Cómo hago para usarlos para demostrar la corrección de un algoritmo o la conveniencia de un enfoque particular?
Cortar y pegar es una forma utilizada en la comprobación de los conceptos de la teoría de grafos. La idea es la siguiente: asuma que tiene una solución para el Problema A, quiere decir algo de borde / nodo, debería estar disponible en la solución. Supondrá que tiene una solución sin un borde / nodo específico, intenta reconstruir una solución cortando un borde / nodo y pegando un borde / nodo específico y dice que el beneficio de la nueva solución es al menos igual al de la solución anterior.
Una de las muestras más importantes es probar los atributos de MST (lo que demuestra que la elección codiciosa es lo suficientemente buena). Ver presentación en MST del libro de CLRS .
El término "cortar y pegar" se muestra en algoritmos a veces cuando se realiza una programación dinámica (y otras cosas también, pero ahí es donde lo vi por primera vez). La idea es que para usar la programación dinámica, el problema que intenta resolver probablemente tenga algún tipo de redundancia subyacente. Utiliza una tabla o técnica similar para evitar resolver los mismos problemas de optimización una y otra vez. Por supuesto, antes de comenzar a usar la programación dinámica, sería bueno probar que el problema tiene esta redundancia, de lo contrario no obtendrás nada al usar una tabla. A menudo, esto se denomina propiedad "subproblema óptimo" (por ejemplo, en CLRS).
La técnica de "cortar y pegar" es una forma de demostrar que un problema tiene esta propiedad. En particular, desea mostrar que cuando se le ocurre una solución óptima a un problema, necesariamente ha utilizado soluciones óptimas para los subproblemas constituyentes. La prueba es por contradiccion. Supongamos que se le ocurrió una solución óptima a un problema mediante el uso de soluciones subóptimas para los subproblemas. Luego, si tuviera que reemplazar ("cortar") esas soluciones de subproblema subóptimas con soluciones de subproblema óptimas (al "pegarlas"), mejoraría su solución óptima. Pero, dado que su solución fue óptima por supuesto, tiene una contradicción. Hay otros pasos involucrados en dicha prueba, pero esa es la parte de "cortar y pegar".
La técnica de "cortar y pegar" se puede utilizar para probar la corrección del algoritmo codicioso (tanto la estructura óptima como la propiedad de elección codiciosa) y la corrección del algoritmo de programación dinámica.
Corrección codiciosa
Esta conferencia señala que la corrección de MST de la clase de algoritmo de licenciatura MIT 2005 muestra la técnica de "cortar y pegar" para demostrar la estructura óptima y la propiedad de elección codiciosa.
Esta conferencia señala la corrección de MST de MIT 6.046J / 18.410J primavera de 2015, utiliza la técnica de "cortar y pegar" para demostrar la propiedad de elección codiciosa
Corrección de la programación dinámica
Una explicación más auténtica para ''cortar y pegar'' se introdujo en CLRS (tercera edición) Capítulo 15.3 Elemento de la programación dinámica en la página 379
"4. Usted muestra que las soluciones a los subproblemas utilizados dentro de la solución óptima al problema deben ser óptimas utilizando una técnica de" cortar y pegar ". Lo hace suponiendo que cada una de las soluciones del subproblema no es óptima y luego se deriva una contradicción. En particular, al "eliminar" la solución de subproblema no óptimo y "pegar" la solución óptima, usted demuestra que puede obtener una mejor solución al problema original, contradiciendo así su suposición de que ya tenía una solución óptima. solución. Si hay más de un subproblema, normalmente son tan similares que el argumento de cortar y pegar para uno puede modificarse para los otros con poco esfuerzo ".
Prueba por contradicción
Se supone que P es falso, es decir, P es verdadero.
Se muestra que! P implica dos aserciones mutuamente contradictorias, Q y! Q.
Como Q y! Q no pueden ser verdaderas, la suposición de que P es falsa debe ser incorrecta, y P debe ser verdadera.