动态规划ppt课件.ppt

第三章动态规划(DynamicProgramming)内容基本思想多阶段决策问题及多阶段决策过程
阶段：将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。
状态：各阶段开始时的客观条件叫做状态。
决策：当各阶段的状态确定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。
状态转移：根据上一阶段的状态和决策来导出本阶段的状态。由第k-1段的状态Sk-1和决策Uk-1确定第k段的状态Sk。
策略：各段决策确定后，整个问题的决策序列就构成一个策略。使整个问题达到最优效果的策略就是最优策略。最优策略的子策略也是最优策略。基本思想Solveforallof1¢,2¢,3¢,...,6¢
Tomake1¢(1coin)
Tomake2¢,1¢+1¢(1coin+1coin=2coins)
Tomake3¢,justusethe3¢coin(1coin)
Tomake4¢,justusethe4¢coin(1coin)
Tomake5¢,try
1¢+4¢(1coin+1coin=2coins)
2¢+3¢(2coins+1coin=3coins)
Tomake6¢,try
1¢+5¢(1coin+2coins=3coins)
2¢+4¢(2coins+1coin=3coins)
3¢+3¢(1coin+1coin=2coins)最优子结构性质(optimalsubstructure)
原问题的最优解包含了子问题的最优解。
该性质使我们能够以自底向上的方式递归地从子问题的最优解逐步构造出原问题的最优解。
重叠子问题(overlappingsubproblem)
有些子问题被反复计算多次（前一阶段的状态带到当前阶段，当前阶段的状态带到下一阶段）。最优子结构/最优化原理重叠子问题矩阵连乘(matrix-chainmultiplication)蛮力算法
设n个矩阵连乘有P(n)个不同的计算次序。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)，所以P(n)的递归关系式为：

动态规划算法
将矩阵连乘积AiAi+1...Aj简记为A[i:j]，这里i≤j
由于矩阵可乘，则设Ai的维数为Pi-1×Pi
设A[i:j]的最优计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤k<j，则其相应完全加括号方式为
(AiAi+1...Ak)(Ak+1Ak+2...Aj)
总的计算量=A[i:k]的计算量+A[k+1:j]的计算量+A[i:k]和A[k+1:j]相乘的计算量(Pi-1PkPj)分析最优解的结构：计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的；
递归定义最优值：设计算A[i:j](1≤i≤j≤n)所需要的最少的乘法次数为m[i,j]，则原问题的最优值为m[1,n]；

计算最优值：依据其递归式以自底向上的方式进行计算。记录已解决的子问题答案。例，5个矩阵连乘，行列数如下：计算最优值：
MatrixChain(p,m,s)
//p={p0,p1,…,pn}，Ai的维数是p[i-1]*p[i]
n=p.length-1
//对角线为单一矩阵
fori=1tondom[i][i]=0
//矩阵链长度
forr=2tondo
fori=1ton–r+1do
j=i+r–1//相邻矩阵
m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]
s[i][j]=i
//矩阵链长度>2时找断开位置
fork=i+1toj-1do
t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]
ift<m[i][j]
m[i][j]=t
s[i][j]=k动态规划算法的基本步骤凸多边形最优三角剖分(TriangulationofaConvexPolygon)本质上与矩阵连乘的最优计算次序问题极为相似
表达式的语法树是一个完全二叉树：叶结点、内结点、根节点
((A1(A2A3))(A4(A5A6)))所对应的语法树
矩阵连乘中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vj。三角剖分中的一条弦vivj，i<j，对应于矩阵连乘A[i+1:j]vk最长公共子序列(LongestCommonSubsequence)计算最优值：
LcsLength(x,y,b)
m=x.length-1
n=y.length-1
fori=1tomdoc[i][0]=0
fori=1tondoc[0][i]=0
fori=1tomdo
forj=1tondo
ifx[i]=y[j]
c[i][j]=c[i-1][j-1]+1
b[i][j]=对角线值
elseifc[i-1][j]>=c[i][j-1]
c