背面跟踪与动态编程之间的区别 [英] difference between back tracking and Dynamic programming

问题描述

我听说动态编程和反向跟踪之间的唯一区别是DP允许重复子问题。 （fib（n）= fib（n-1）+ fib（n-2））。这样对吗 ？还有其他的区别吗？另外我想知道使用这些技术解决的一些常见问题。

解决方案

动态编程方法有两个典型的实现： >底部到顶部和顶部到底部。

从上到下的动态编程只不过是普通的递归，它增强了记忆中间子问题的解决方案。当一个给定的子问题出现在第二（第三，第四...）时间时，它并没有从头开始解决，而是立即使用以前记忆的解决方案。这种技术在名称为 memoization （i之前的'r'）中是已知的。

这实际上是你的斐波那契序列的例子应该说明。只需使用Fibonacci序列的递归公式，但在路上建立 fib（i）值的表，您将获得一个从头到尾的DP算法（例如，如果您需要第二次计算 fib（5），则从表中获取它，而不是再次计算）。

在底层到顶部的动态编程中，该方法也基于将子解决方案存储在内存中，但是它们以不同的顺序（从较小到较大），并且所得到的算法的一般结构不是递归的。 LCS算法是一个经典的底层到顶端的DP示例。

底层到顶端的DP算法通常更有效，但是它们通常更难（有时候是不可能的）构建，因为并不总是很容易预测你将需要哪些原始子问题解决整个原始问题，以及从小的子问题到哪个路径，以最有效的方式获得最终解决方案。

I heard the only difference between dynamic programming and back tracking is DP allows overlapping of sub problems. (fib(n) = fib(n-1)+ fib (n-2)). Is it right ? Are there any other differences ? Also I would like know some common problems solved using these techniques.

解决方案

There are two typical implementations of Dynamic Programming approach: bottom-to-top and top-to-bottom.

Top-to-bottom Dynamic Programming is nothing else than ordinary recursion, enhanced with memorizing the solutions for intermediate sub-problems. When a given sub-problem arises second (third, fourth...) time, it is not solved from scratch, but instead the previously memorized solution is used right away. This technique is known under the name memoization (no 'r' before 'i').

This is actually what your example with Fibonacci sequence is supposed to illustrate. Just use the recursive formula for Fibonacci sequence, but build the table of fib(i) values along the way, and you get a Top-to-bottom DP algorithm for this problem (so that, for example, if you need to calculate fib(5) second time, you get it from the table instead of calculating it again).

In Bottom-to-top Dynamic Programming the approach is also based on storing sub-solutions in memory, but they are solved in a different order (from smaller to bigger), and the resultant general structure of the algorithm is not recursive. LCS algorithm is a classic Bottom-to-top DP example.

Bottom-to-top DP algorithms are usually more efficient, but they are generally harder (and sometimes impossible) to build, since it is not always easy to predict which primitive sub-problems you are going to need to solve the whole original problem, and which path you have to take from small sub-problems to get to the final solution in the most efficient way.

这篇关于背面跟踪与动态编程之间的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！