Moh*_*han 11 theory algorithm dynamic-programming backtracking
我一直想知道这件事.没有书明确说明这一点.
回溯正在探索所有可能性,直到我们发现一种可能性无法引导我们找到可能的解决方案,在这种情况下我们放弃它.
据我所知,动态编程的特点是重叠的子问题.那么,动态编程是否可以表示为缓存回溯(对于以前探索过的路径)？
谢谢
这是动态编程的一个方面,但还有更多内容.
对于一个简单的例子,采取斐波那契数字:
F (n) =
n = 0: 0
n = 1: 1
else: F (n - 2) + F (n - 1)
我们可以调用上面的代码"回溯"或"递归".让我们将其转换为"使用缓存进行回溯"或"使用memoization进行递归":
F (n) =
n in Fcache: Fcache[n]
n = 0: 0, and cache it as Fcache[0]
n = 1: 1, and cache it as Fcache[1]
else: F (n - 2) + F (n - 1), and cache it as Fcache[n]
不过,还有更多.
如果可以通过动态编程解决问题,则存在状态和它们之间的依赖关系的有向非循环图.有一个国家对我们感兴趣.还有基本状态,我们立即知道答案.
我们可以从我们感兴趣的顶点到它的所有依赖关系,从它们到它们依赖的所有依赖关系等遍历那个图形,停止在基本状态进一步分支.这可以通过递归来完成.
有向无环图可以视为顶点上的部分顺序.我们可以在拓扑上对该图进行排序,并按排序顺序访问顶点.此外,您可以找到一些与您的部分订单一致的简单总订单.
还要注意,我们经常可以在状态上观察一些结构.例如,状态通常可以表示为整数的整数或元组.因此,我们可以预先分配一个更容易和更快使用的常规数组,而不是使用通用缓存技术(例如,关联数组来存储状态 - >值对).
回到我们的Fibonacci例子,偏序关系只是状态n >= 2取决于状态n - 1和n - 2.基本状态是n = 0和n = 1.这个顺序关系一致的一个简单的订单总额的自然顺序:0,1,2,....以下是我们的开始:
Preallocate array F with indices 0 to n, inclusive
F[0] = 0
F[1] = 1
好的,我们有命令访问各州.现在,什么是"访问"？还有两种可能性:
(1)"Backward DP":当我们访问一个状态时u,我们会查看它的所有依赖关系v并计算该状态的答案u:
for u = 2, 3, ..., n:
F[u] = F[u - 1] + F[u - 2]
(2)"转发DP":当我们访问一个州时u,我们会查看所有v依赖它并在以下各个州中占据u的州v:
for u = 1, 2, 3, ..., n - 1:
add F[u] to F[u + 1]
add F[u] to F[u + 2]
请注意,在前一种情况下,我们仍然直接使用Fibonacci数的公式.然而,在后一种情况下,命令性代码不能通过数学公式容易地表达.但是,在某些问题上,"前向DP"方法更直观(现在没有好的例子;任何愿意贡献它的人？).
动态编程的另一个用途是难以表达为回溯:Dijkstra的算法也可以被认为是DP.在算法中,我们通过向顶点添加顶点来构造最优路径树.当我们添加一个顶点时,我们使用的事实是它的整个路径 - 除了路径中的最后一个边缘 - 已经知道是最优的.因此,我们实际上使用了一个子问题的最优解决方案 - 这正是我们在DP中所做的事情.仍然,我们事先不知道向树添加顶点的顺序.
不,或者更确切地说.
在回溯中,你往下走,然后备份每条路径.但是,动态编程是自下而上的,因此您只能获得备份部分而不是原始的部分.此外,动态编程的顺序首先是广度,而回溯通常是深度优先.
另一方面,memoization(动态编程非常接近的表兄)经常用作缓存的回溯,就像你描述的那样.