算法设计与分析

动态规划

1.动态规划基本原理

动态规划算法并非适用于所有的最优化问题,适用于动态规划求解的问题应具备两个基本要素:最优子结构性质和子问题重叠性质。

(1)最优子结构性质

最优子结构性质,通俗地讲就是问题的最优解包含其子问题的最优解。也就是说,如果把问题的最优解分解(比如划分为两个或者多个部分,或者删除第一个或者最后一个分量),得到一个子解,那么这个子解是特定子问题的最优解。

最优子结构性质隐含了问题最优解和子问题最优解之间的一种递推关系。它是动态规划的基础,保障了问题的最优解可以由子问题的最优解构造得到,即得到动态规划算法的递推方程。如果一个问题不具备该性质,则不可能用动态规划方法来求解。

在分析问题的最优子结构性质时,人们一般采用反证法:首先假设由问题最优解S导出的子问题的解不是最优的,然后再推导在这个假设下可构造出比S更好的解S’,从而得到矛盾。

(1)最优子结构性质

分治算法求解问题时,每次产生的子问题并不总是新问题,有些子问题重复出现,这种性质称为子问题重叠性质。

在动态规划算法中,对于重复出现的子问题,只是在第一次遇到时执行求解过程,然后把求解结果保存在一个表格(可能是高维表格)中,再遇到这个子问题时,直接从表格中引用答案,从而避免重复计算,达到提高效率的目标。

需要提醒的是,子问题重叠性质不是动态规划适用的必要条件,但是如果该性质不满足时,动态规划方法与其他方法相比就不具备优势。

2.动态规划算法设计步骤

动态规划算法适合用于求解最优化问题,通常可按下列步骤来设计动态规划算法:

1)分析最优子结构性质;
2)确定状态表示和状态递推方程,递归地定义最优值;
3)确定状态转移顺序,以自底向上的方式计算出最优值;
4)根据计算最优值时得到的信息,构造最优解。

第(1)步是基础,也是关键。在分析最优子结构性质时,子解分解和子解对应的子问题描述是关键。本书将介绍两种子解分解方法:基于划分的方法和基于减一的方法。在第一种方法中,问题的最优解依据问题性质划分成两个或者多个子解,但是其划分位置无法事先确定;在第二种方法中,问题的最优解依据问题性质缩减规模,比如减去最优解的第一个分量,或者最后一个分量,得到规模少1个单位的子解。得到子解后,分析和描述该子解对应的子问题,如果能证明该子解是对应子问题的最优解,则该问题满足最优子结构性质,转入第(2)步;否则,该问题不能用动态规划求解。

第(2)步是动态规划算法的核心,它是最优解的规划过程。状态表示本质上就是子问题的表示,形如f(x1,…,xk),其中x1,…,xk 是描述子问题的参数列表,每一个参数都需要定义其取值范围;f(·)的值域则体现问题的求解目标,一般地,f(·)直接定义为待求解问题的目标值。需要注意的是,对于有些问题来说,f(·)如果直接定义为原问题目标值,可能最优子结构性质不成立。此时,f(·)往往定义为某个中间目标值,比如最大上升子序列问题。在算法实现时,状态f(x1,…,xk)一般用一个k 维的表格存储,动态规划过程就是表格操作过程。

第(3)步体现了动态规划算法的执行过程。通俗地讲,动态规划是一个由易至难的求解过程:先求解最简单的子问题的解,然后利用简单子问题的解构造复杂一些的子问题的解,直至求解原问题的解。

第(4)步是可选步骤,只有问题要求构造最优解时才需要。


3.典型例题

1)最优搜索树

2)I need an offer

3)闺蜜的八卦路径

4)编辑距离

5)收集控


4.课件下载

Algorithm-5-DynamicProgramming.pptx

5.扩展阅读

隐马尔科夫模型(Hidden Markov Models,HMM)是模式识别中的最常用模型之一,HMM中的核心算法都应用了动态规划思想。 Ref4-1. A Tutorial on Hidden Markov Models and. Selected Applications in Speech Recognition.

Ref4-1-Tutorial on hidden Markov models and applications.pdf