文档介绍：动态规划
陈新驰
2
动态规划是运筹学的一个分支,是求解多阶段决策过程最优化问题的数学方法。 动态规划在经济管理、工程技术、工农业生产及军事部门中都有着广泛的应用,并且获得了显著的效果。 学****动态规划,我们首先要了解多阶段决策问题。
3
最短路径问题:给定一个交通网络图如下,其中两点之间的数字表示距离(或运费),试求从A点到G点的最短距离(总运输费用最小)。
1
2
3
4
5
6
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
E3
F1
F2
G
5
3
1
3
6
8
7
6
3
6
8
5
3
3
8
4
2
2
2
1
3
3
3
5
2
5
6
6
4
3
多阶段决策问题
阶段
状态
决策
转移方程
边界条件
B1 3 C1 1 D1
2 1
3 4 2
A1 C2 E1
2 1 2
3
B2 5 C3 1 D2
问题:求从A1到E1的最短路径长度。
A B C D E
阶段
状态
f(i)=min{f(j)+g(i, j)},
f(i)表示到从起点到节点i的最短路径长度
f(A1)=0
思考:如果定义“路径长度”为实际长度模3的余数,为了求A1到E1的最短“路径长度”,还能用上述方法吗?
动态规划算法的适用范围
最优子结构
最优决策序列的字序列也是最优的
无后效性
决策只取决于当前状态的特征因素,而和到达此状态的方式无关
递推——将最优性变成统计的动态规划
递推同样需要状态的划分和无后效性
但是递推的转移函数(状态转移方程)通常不包括max和min,而是一些统计函数——如求和
递推的难点通常在状态建模和转移函数的确定
综上所述,将递推看成动态规划的一种形式是没问题的
因此,接下来的内容将不区别动态规划和递推
例题:最长上升子序列
一个数的序列bi,当b1 < b2 < ... < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN),我们可以得到一些上升的子序列(ai1, ai2, ..., aiK),这里1 <= i1 < i2 < ... < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8)
你的任务,就是对于给定的序列,求出最长上升子序列的长度。
输入数据
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数,这些整数的取值范围都在0到10000。
输出要求
最长上升子序列的长度。
输入样例
7
1 7 3 5 9 4 8
输出样例
4
递归函数为:dp[i]=max{dp[k]+1,1}(v[k]<v[i],0<=k<i),其中下标从0开始
例题: Poj 1458 最长公共子序列
给出两个字符串,求出这样的一个最长的公共子序列的长度:子序列中的每个字符都能在两个原串中找到,而且每个字符的先后顺序和原串中的先后顺序一致。
经常会遇到复杂问题不能简单地分解成几个子问题,而会分解出一系列的子问题。简单地采用把大问题分解成子问题,并综合子问题的解导出大问题的解的方法,问题求解耗时会按问题规模呈幂级数增加。
为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法。
【问题】 求两字符序列的最长公共字符子序列
问题描述:字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=“x0,x1,…,xm-1”,序列Y=“y0,y1,…,yk-1”是X的子序列,存在X的一个严格递增下标序列<i0,i1,…,ik-1>,使得对所有的j=0,1,…,k-1,有xij=yj。例如,X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。
最长公共子序列
考虑最长公共子序列问题如何分解成子问题,设A=“a0,a1,…,am-1”,B=“b0,b1,…,bm-1”,并Z=“z0,z1,…,zk-1”为它们的最长公共子序列。不难证明有以下性质:
(1) 如果am-1=bn-1,则zk-1=am-1=bn-1,且“z0,z1,…,zk-2”是“a0,a1,…,am-2”和“b0,b1,…,bn-2”的一个最长公共子序列;
(2) 如果am-1!=bn-1,则若zk-1!=am-1,蕴涵“z0,z1,…,zk-1”是“a0,a1,…,am-2”和“b0,b1,…,b