动态规划-曹利国.ppt

动态规划;什么是动态规划？;多阶段决策问题;;如图，一个有向图，求一条从最左边的点走到最右边点的方案〔只能从左往右走〕，使得所经过的权值和除以4的余数最小。;;;让我们来换一个思路思考此题，因为此题是要求总和除以４余数最小的一条路径，我们先撇开最小余数不去管它，而是将此题改为从点1到点４的所有路径中，求出每条路上权值和除以４的不同余数的个数。

我们设一个数组can[I,j]表示从点1至点Ｉ可不可以求出一条路径是该路径的权值总和除以４的余数为Ｊ，那么又可以得出一个方程：

can[I,j]:=can[I-1,k]and((k+num[I,p])mod4=j)

(0=k=3,1=p=2)

边界：can[1,0]=truecan[1,1]=false

can[1,2]=falsecan[1,3]=false

通过这个方程我们可以求出从点1至点Ｉ可以到达的所有余数，我们只要从这些余数中选出一个值最小的输出就行。;动态规划的指导思想;两种算法的差异在于，贪心法产生一个按贪心策略形成的判定序列，该序列不保证解是全局最优的。而动态规划会产生许多判定序列，再按最优性原理对这些序列加以筛选，去除那些非局部最优的子序列。;什么是动态规划？;问题：给定一个具有N层的数字三角形如以下图，从顶至底有多条路径，每一步可沿左斜线向下或沿右斜线向下，路径所经过的数字之和为路径得分，请求出最大路径得分。;递归算法;通过以下搜索树可以看出在求Max(2,1),Max(2,2)的时候两次调用函数Max(3,2)，也就是说，函数Max(3,2)被重复计算了两次，其实在这棵搜索树中有很多结点都被重复计算了屡次，程序时效显然就会大打折扣了，实际上这也是搜索之所以会效率低下的一大原因。既然知道了上述搜索算法效率低的原因。对于同一个函数值搜索屡次是没有必要的，因此我们可以每求出一个函数的值便可将其用数组保存下来，到了下次要用的时候直接从数组里调出来用就可以了。这样时间复杂度一下子降成了O(N*N){函数个数最多不超过N*N个。};记忆化搜索;动态规划问题具有以下根本特征：

1、问题具有多阶段决策的特征。

2、每一阶段都有相应的“状态”与之对应，描述状态的量称为“状态变量”。

3??每一阶段都面临一个决策，选择不同的决策将会导致下一阶段不同的状态。

4、每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构。;动态规划的几个概念;动态规划问题的一般解题步骤;线性规划模型;分析;最长不下降序列;分析;进一步;改进算法;进一步;改进算法;;首先我们需要判定对于给定的两条航线是否相交，设北岸城市i1，j1(i1j1)分别与南岸城市i2，j2互为友好城市，那么这两条航线不相交(以下简称为i1，j1相容)的充要条件是I2=J2。(结论1)由以下图就可以很容易地得到这个结论。;

从上面的结论可以看出，最优的选择方案中，如果将所有航线按北岸村庄号从小到大排序，序列中每一个北岸村庄对应的南岸村庄号必然满足B1B2B3……Bn〔n为选出来的航线数〕。

同样，对于任一个方案，如果北岸村庄排好序后，与之对应的南岸村庄也是按升序排列，那么该方案必然不存在相交的两条航线；相反，如果南岸村庄不是按升序排列，必存在两条相交的航线。因此，我们可以先将各航线按北岸村庄号排一个序，那么最优的方案必然是从相对应的南岸村庄中找出一个最长不下降序列，该序列的长度即为问题的解。;凸多边形三角划分;分析;在数字串中插入假设干(K个)乘号使总的乘积最大。

分析：定义从l到r参加k个乘号的最大乘

积值为p(l,r,k)。

p(l,r,k)=max{d(l,q)*p(q+1,r,k-1)};解题思路

定义:从l到r参加k个乘号的最大乘

积值p(l,r,k)。

p(l,r,k)=max{d(l,q)*p(q+1,r,k-1)};树形动态规划(皇宫看守);;问题分析;;;;;状态转移方程;动态规划模型的建立;例题1：骨牌游戏;分析;;小优化;动态规划模型的建立;最长公共子串问题;分析;;;;;;;双层动态规划;;分析;动态规划时间效率的优化;有一批编