algorithm - programacion - diferencia entre el seguimiento posterior y la programación dinámica
programacion dinamica pdf (5)
DP permite resolver un gran problema computacionalmente intensivo descomponiéndolo en subproblemas cuya solución requiere solo el conocimiento de la solución anterior inmediata. Obtendrá una muy buena idea al seleccionar Needleman-Wunsch y resolver una muestra porque es muy fácil ver la aplicación.
Retroceder parece ser más complicado cuando se poda el árbol de la solución, se sabe que una ruta específica no dará un resultado óptimo.
Por lo tanto, se podría decir que Backtracking optimiza para la memoria ya que DP supone que todos los cálculos se realizan y luego el algoritmo retrocede recorriendo los nodos de menor costo.
Escuché que la única diferencia entre la programación dinámica y el seguimiento posterior es que DP permite la superposición de problemas secundarios. (fib (n) = fib (n-1) + fib (n-2)). Es correcto ? Hay otras diferencias ? También me gustaría saber algunos problemas comunes resueltos usando estas técnicas.
Hay dos implementaciones típicas del enfoque de programación dinámica: de abajo hacia arriba y de arriba hacia abajo .
La programación dinámica de arriba a abajo no es más que una recursión ordinaria, mejorada al memorizar las soluciones para sub-problemas intermedios. Cuando un sub-problema dado surge en segundo lugar (tercero, cuarto ...), no se resuelve desde cero, sino que la solución previamente memorizada se usa de inmediato. Esta técnica se conoce con el nombre de memorización (no ''r'' antes de ''i'').
Esto es en realidad lo que se supone que su ejemplo con la secuencia de Fibonacci debe ilustrar. Solo use la fórmula recursiva para la secuencia de Fibonacci, pero construya la tabla de valores de fib(i) largo del camino, y obtendrá un algoritmo DP de arriba a abajo para este problema (de modo que, por ejemplo, si necesita calcular fib(5) segunda vez, lo obtiene de la mesa en lugar de calcularlo de nuevo).
En la Programación Dinámica Bottom-to-top, el enfoque también se basa en almacenar sub-soluciones en la memoria, pero se resuelven en un orden diferente (de menor a mayor), y la estructura general resultante del algoritmo no es recursiva. El algoritmo LCS es un clásico ejemplo de DP de fondo a cima.
Los algoritmos DP de abajo a arriba son usualmente más eficientes, pero en general son más difíciles de construir (ya veces imposibles), ya que no siempre es fácil predecir qué subproblemas primitivos necesitará para resolver todo el problema original. y qué camino debe tomar desde pequeños sub-problemas para llegar a la solución final de la manera más eficiente.
La generación del primer nodo de profundidad del árbol de espacio de estado con función de límite se denomina retroceso. Aquí el nodo actual depende del nodo que lo generó.
La generación del primer nodo de profundidad del árbol de espacio de estado con función de memoria se denomina programación dinámica descendente. Aquí el nodo actual depende del nodo que genera.
Los problemas dinámicos también requieren una "subestructura óptima".
De acuerdo con Wikipedia:
La programación dinámica es un método para resolver problemas complejos dividiéndolos en pasos más simples. Es aplicable a problemas que exhiben las propiedades de subproblemas superpuestos que son solo una subestructura levemente más pequeña y óptima.
Backtracking es un algoritmo general para encontrar todas (o algunas) soluciones a algún problema computacional, que incrementalmente crea candidatos para las soluciones, y abandona cada candidato parcial c ("backtracks") tan pronto como determina que c no puede completarse a un solución válida
Para una discusión detallada de la "subestructura óptima", lea el libro de CLRS .
Los problemas comunes para retroceder pueden ser:
Problemas de DP:
- Este website en el MIT tiene una buena colección de problemas de DP con agradables explicaciones animadas.
- Un capítulo de un libro de un profesor en Berkeley.
Una diferencia más podría ser que los problemas de programación dinámica generalmente se basan en el principio de optimalidad . El principio de optimalidad establece que una secuencia óptima de decisión o elección cada sub secuencia también debe ser óptima.
¡Los problemas de retroceso generalmente NO son óptimos en su camino! Solo se pueden aplicar a problemas que admiten el concepto de solución candidata parcial .