动态规划 -- 动态规划基础

时间:2021-06-24 16:44:32

参考资料:

算法导论

什么时候需要用到动态规划呢?大致有两个要素:最优子结构和重叠子问题。


1 最优子结构

如果问题的一个最优解中包含了子问题的最优解,则该问题具有最优子结构。当一个问题具有最优子结构时,动态规划就可能适用(贪心算法可能也适用)。


寻找最优子结构的时候,可遵循一种共同的模式

1 问题的一个解可以是做一种选择。例如,选择一个前一个装配线装配站(有两个选择);或者选择一个下标以在该位置分裂矩阵链(有j-i个选择)。

2  对一个给定的问题,假设已知的是一个导致最优解的选择。不必关心如何确定这个选择。

3 在已知这个选择后,要确定哪些子问题会随之发生,以及如何最好的描述所得到的的子问题控件。

4 利用剪贴技术,来证明在一个问题的最优解中,使用的子问题的解本身也是最优的。


最优子结构在问题域中以两种方式变化:

1) 多少个子问题被使用在原问题的一个最优解中,以及

2) 决定一个最优解中使用哪些子问题时有多少个选择。


2 重叠子问题

问题与子问题之间,子问题与子自问题之间等,它们之间共享资源,即它们包含了公共的解,通过从下到上解保证这些公共解只解一次,用到时查看表中已有的解即可。动态规划算法总是充分利用重叠子问题,即通过每个子问题只解一次,把解保存在一个在需要时就可以查看的表中,而每次查表的时间为常数。动态规划要求子问题既要独立又要重叠。如果同一个问题的两个子问题不共享资源,则他们就是独立的。


3 构造最优解

在实际应用中,我们通常把每一个子问题中所做的选择保存在一个表格中,这样在需要时,就不必根据已存下来的代价信息来重构这方面的信息了。