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.diferencia entre el seguimiento posterior y la programación dinámica
Hay dos implementaciones típicas del enfoque de programación dinámica: de abajo hacia arriba y de arriba a abajo.
arriba hacia abajo Programación Dinámica es nada más que ordinario recursividad, mejorado con la memorización de las soluciones intermedias para sub-problemas. 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 memoria (no 'r' antes '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 fib(i) a lo 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) por segunda vez, lo obtienes de la mesa en lugar de calcularlo de nuevo).
En de abajo hacia arriba Programación Dinámica el enfoque también se basa en el almacenamiento de sub-soluciones en la memoria, sino que se resuelven en un orden diferente (de menor a mayor), y la estructura general resultante del algoritmo no es recursivo LCS algorithm es un clásico ejemplo de DP de fondo a cima.
Los algoritmos DP de abajo hacia arriba suelen ser 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á 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.
Los problemas dinámicos también requieren una "subestructura óptima".
Según Wikipedia:
La programación dinámica es un método de resolución de problemas complejos rompiendo hacia abajo en pasos más simples. Es aplicable a problemas que exhiben las propiedades de superposición de subproblemas que son solo subestructura pequeña y óptima.
Backtracking es un algoritmo general para encontrar todos (o algunos) soluciones a algún problema computacional, que construye incrementalmente candidatos a los soluciones, y abandona cada parcial candidato c ("preclasificación") tan pronto como , determina que c no puede posiblemente completar una solución válida.
Para obtener una descripción detallada de la "subestructura óptima", lea the CLRS book.
problemas comunes para dar marcha atrás que puedo pensar son:
problemas DP:
DP permite resolver un gran problema computacionalmente intensivo dividiéndolo en subproblemas cuya solución solo requiere 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 donde 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 la memoria ya que DP supone que todos los cálculos se realizan y luego el algoritmo retrocede recorriendo los nodos de menor costo.
Una diferencia más podría ser que los problemas de programación dinámica generalmente se basan en el principio de optimización . 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 parcial candidata.
Estoy bastante seguro de que no se puede construir un DP sin invocar "el principio de optimalidad". El retroceso dinámico suena un poco como la aplicación de la heurística. –
¡Respuesta pequeña y clara! – kakurala
Creo que se refería a la memorización sin la "r". – grokus
@grokus: Sí, eso es lo que también se llama * memoial *. Lo agregaré a la respuesta. – AnT
¿Entonces Backtracking es DP de abajo hacia arriba? – mb21