算法设计与分析 王红梅 第二版 第6章动态规划.ppt

第6章动态规划Dynamic Programming
算法设计与分析—本科生课程
Design and Analysis of Algorithm
海南大学信息科学技术学院
College of Information Science and Technology, Hainan University
2017/11/22
2
教学重点
动态规划法的设计思想,各种经典问题的动态规划思想
教学难点
多阶段决策过程,最优性原理,各种经典问题的动态规划思想
教学内容及目标
知识点
教学要求
了解
理解
掌握
熟练掌握
多阶段决策过程
√
动态规划法的设计思想
√
多段图的最短路径问题
√
多源点最短路径问题
√
TSP问题
√
最长递增子序列问题
√
最长公共子序列问题
√
0/1背包问题
√
最优二叉查找树
√
近似串匹配问题
√
学****目标
Chapter 6 Dynamic Programming
2017/11/22
Chapter 6 Dynamic Programming
3
本章要点
概述
图问题中的动态规划法
组合问题中的动态规划法
查找问题中的动态规划法
2017/11/22
Chapter 6 Dynamic Programming
4
概述
动态规划?
在1950年代由美国数学家贝尔曼为研究最优控制问题而提出的概念。
它是一种求解多阶段决策最优化问题的工具。
与分治法的关系
动态规划法也将待求解问题分解成若干子问题,但各问题间往往不是独立的。
分治法对子问题的重叠部分要被重复计算多次。
动态规划法将每个子问题只求解一次并保存在表中,下次查表获得解,免去重复计算。
2017/11/22
Chapter 6 Dynamic Programming
5
最优化问题?
有 n 个输入,它的解由这 n 个输入的一个子集组成,这个子集必须满足某些事先给定的条件,这些条件称为约束条件,满足约束条件的解称为问题的可行解。满足约束条件的可行解可能不只一个,为了衡量这些可行解的优劣,事先给出一定的标准,这些标准通常以函数的形式给出,这些标准函数称为目标函数,使目标函数取得极值(极大或极小)的可行解称为最优解,这类问题就称为最优化问题。
多阶段决策过程
2017/11/22
Chapter 6 Dynamic Programming
7
例:0/1背包问题
物品i或者被装入背包(xi=1),或者不被装入背后(xi=0)。有如下约束条件和目标函数:

()
()
最优化问题
于是问题归结为寻找一个满足式()的约束条件,并使式()的目标函数达到最大的解向量X=( x1, x2, …, xn)
2017/11/22
Chapter 6 Dynamic Programming
8
最优性原理
对于一个具有n个输入的最优化问题,其求解过程往往可以划分为若干个阶段,每一阶段的决策仅依赖于前一阶段的状态,由决策所采取的动作使状态发生转移,成为下一阶段决策的依据;
从而,一个决策序列在不断变化的状态中产生。这个决策序列产生的过程称为多阶段决策过程。
A
P1
P2
P7
动态规划的决策过程
B
C
D
E
P3
P4
P5
P6
初始状态
最终状态
2017/11/22
Chapter 6 Dynamic Programming
9
多阶段决策过程满足最优性原理(Optimal Principle):无论决策过程的初始状态和初始决策是什么,其余的决策都必须相对于初始决策所产生的当前状态,构成一个最优决策序列。各子问题的解只与它前面的子问题的解相关,而且各子问题的解都是相对于当前状态的最优解,整个问题的最优解是由各个子问题的最优解构成。
如果一个问题满足最优性原理通常称此问题具有最优子结构性质。
最优性原理
2017/11/22
Chapter 6 Dynamic Programming
10
动态规划法的设计思想
动态规划法将待求解问题分解成若干个相互重叠的子问题,每个子问题对应决策过程的一个阶段,一般来说,子问题的重叠关系表现在对给定问题求解的递推关系(也就是动态规划函数)中,将子问题的解求解一次并填入表中,当需要再次求解此子问题时,可以通过查表获得该子问题的解而不用再次求解,从而避免了大量重复计算。