动态规划的模型构建与优化方法.ppt

动态规划模型构建与优化;综述;分析思路;什么是动态规划？;多阶段决策问题;取石子游戏;分析;分析;什么是动态规划？;动态规划的核心——记忆化;记忆化搜索与动态规划;记忆化搜索与动态规划;例题一〔线性规划模型〕;对例一的优化;例题二〔区间模型〕;解法;继续;序列压缩;;算法一;;算法二;;;;;最长公共子串问题〔lcs);分析;;;;;拓展;例子;例子的扩展;决策变量满足单调性问题;矩阵处理类动态规划模型;;;分析;矩阵类规划模型;;分析;双层规划模型;;;树形动态规划;例题;分析;转移优化;例题：珠宝〔gems〕;分析;动态规划时间效率的优化;有一批编号为1至N且尺寸规格一样的箱子。现在要将其中某些箱子叠放起来，使叠放的高度最大，箱子叠放的规那么如下：

一、每个箱子上最多只能直接叠放一个箱子；

二、编号较小的箱子不能放在编号较大的箱子之上；

三、每个箱子都给出了自身重量与可承受重量，每个箱子上的所有箱子重量之和不得超过该箱的可承受重量。

输入箱子数N〔1≤N≤1000〕及每个箱子的自身重量与可承受重量，两个数值均为小于等于3000的正整数。输出最多可叠放的箱子总数M和每个箱子的编号。;箱子是按编号顺序叠放，所以可用动态规划求解。设：

Weight[I]表示第I个箱子的重量。

Support[I]表示第I个箱子的承受重量。

F(i,j)表示前i个箱子中最多可选出f(i,j)个叠放，最底层承受的重量为j。

F(i,j)=Max{F(i-1,j+Weight[i])+1,F(i-1,j)}。

〔其中，J=support[I]〕;;改进一下状态的表示方式，设F[I，j]表示前i个箱子叠放j个箱子(从上往下，按编号从大到小的顺序叠放)时可承受的最小重量。

F[i，j]：=Min{F[i-1，j]，F[i-1，j-1]+Weight[i]}

Ans：=Max〔J|F[i，j]〕〔F[i，j]〈=support[i]〉〕

上述算法的状态总数为O(n*n)，每个状态转移的状态数为O(1)，每次状态转移的时间为O(1)，所以总的时间复杂度=1000*1000=1*10^6。;;2、选择适当的规划方向

规划方向的选择主要有两种：顺推和逆推。假设初始状态确定，目标状态不确定，那么应考虑采用顺推，反之，假设目标状态确定，而初始状态不确定，就应该考虑采用逆推。那么，假设是初始状态和目标状态???已确定，可以选用双向规划。;;例题4：Divide(Merc`2000)

有价值分别为1..6的大理石各a[1..6]块，现要将它们分成两局部，使得两局部价值和相等，问是否可以实现。其中大理石的总数不超过20000。;令S=∑(i*a[i])，假设S为奇数，那么不可能实现，否那么令Mid=S/2，

问题转化为能否从给定的数中中选取局部数，使其和为Mid。

设m[i,j]表示能否从价值为1..i的大理石中选出局部大理石，

使其价值和为j，假设能，那么用true表示，否那么用false表示。

那么状态转移方程为：

m[i,j]=m[i-1,j]ORm[i-1,j-i*k](1≤k≤a[i])

规划的边界条件为：m[i,0]=true；0≤i≤6

假设m[i,Mid]=true，0≤i≤6，那么可以实现题目要求，否那么不可

能实现。;;此题在i较小时，值为true的状态也较少，但随着i的增大，

值为true的状态也急剧增多，影响了算法的时间效率。

我们分别求出从价值为1..3的大理石中选出局部大理石所能

获得的所有价值和，和从价值为4..6的大理石中选出局部大

理石所能获得的所有价值和。再判断是否存在和为Mid的价

值和，从而得出问题的解。;;回忆此题的优化过程可以发现：此题的实际背景与双向搜

索的背景十分相似，同样有庞大的状态空间，有确定的初始

状态和目标状态，状态量都迅速增长，而且可以实现交汇的

判断。

从此题的优化过程，我们认识到，双向扩展以减少状态

量的方法不仅适用于搜索，同样适用于动态规划。这种在不

同解题方法中，寻找共通的属性，从而借用相同的优化思想，

可以使我们不断创造出新的方法。;二、减少每个状态转移的状态数

在使用动态规划方法解题时，对当前状态

的计算都是进行一些决策并引用相应的已经计算过

的状态，这个过程称为“状态转移”。因此，每个状

态可能转移的状态数是决定动态规划算法时间复杂度

的一个重要因素。;1、决策量的优化

分析问题最优解的性质，缩