算法设计与分析_第3章_动态规划2

《算法设计与分析_第3章_动态规划2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计与分析第3章动态规划(2)1学习要点¢理解动态规划算法的概念。¢掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质¢掌握设计动态规划算法的步骤。（1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。2学习要点¢通过应用范例学习动态规划算法设计策略。（1）矩阵连乘问题；（2）最长公共子序列；（3）凸多边形最优三角剖分；（4）0/1背包问题；（5）最优二叉搜索树。3凸多边形最优三角剖分¢

2、应用¢Catalan数¢多边形三角剖分是数字城市研究许多工作的前提¢城市景观三维重建中的三角剖分算法¢基于图像特征和三角剖分的水印算法¢基于三角剖分的小脑模型在增强学习中的应用¢传感网中的动态Delauanay三角剖分算法¢……4凸多边形最优三角剖分¢多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。¢输入:给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。¢输出:要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。5凸多边形最优三角剖分¢用多边形顶

3、点的逆时针序列表示凸多边形，即P={v,v,…,v}表示具有n条边的01n-1凸多边形。¢若vi与vj是多边形上不相邻的2个顶点，则线段vv称为多边形的一条弦。ij¢弦将多边形分割成2个多边形{vi,vi+1,…,vj}和{v,v,…v}。jj+1i6三角剖分的结构及其相关问题¢一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。¢叶结点:表达式中一个原子¢例如，完全加括号的矩阵连乘积((A(AA))(A(AA)))相应的语法树为123456¢叶结点:一个矩阵7三角剖分的结构及其相关

4、问题¢凸多边形{v0,v1,…vn-1}的三角剖分也可以用语法树表示,如图。¢一个凸n多边形的三角剖分对应一棵有n-1个叶结点的语法树¢与矩阵连乘积问题的比较(P59)¢每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi¢矩阵连乘积A[i+1:j]对应于三角剖分中的一条弦vv，i

5、应的s∈ST三角形集合9步骤1：最优子结构性质¢分析¢若凸(n+1)边形P={v0,v1,…,vn}的最优三角剖分T包含三角形vvv，1≤k≤n-1，则T0kn的权为3个部分权的和：三角形vvv的0kn权，子多边形{v,v,…,v}和{v,v,…,v}01kkk+1n的权之和。¢由T所确定的这2个子多边形的三角剖分也是最优的。因为若有{v,v,…,v}或01k{v,v,…,v}的更小权的三角剖分将导致Tkk+1n不是最优三角剖分的矛盾。10步骤2：最优三角剖分的递归结构¢子问题{vi-1,vi,…,

6、vj}的最优三角剖分¢划分方法：三角形vi-1vkvj，关键怎么找vk！¢t[i][j](1≤i

7、其中i≤k≤j-1，而k的所有可能i-1kj位置只有j-i个，由此，t[i][j]可递归地定义为：110-1背包问题¢0-1背包问题是一类经典的组合优化问题¢对0-1背包问题的研究可以广泛运用于资源分配、投资决策、货物装载等方面。¢处理机和数据库在分布式计算机系统上的分配问题¢项目选择的货物装载问题¢削减库存问题等120-1背包问题¢研究¢在量子计算机上求解0/1背包问题¢计算机学报，中国科学技术大学计算机科学与技术系国家高性能计算中心，1999，12：1314～1316¢二次背包问题的一种快速解法

8、¢计算机学报，国防科学技术大学计算机学院长沙2004，9：1162～1169¢多维背包问题的一个蚁群优化算法¢计算机学报，哈尔滨工业大学计算机科学与技术学院，2008，5：810～819130-1背包问题¢给定n种物品和一背包。物品i的重量是w，其价值为v，背包的容量为C。问应ii如何选择装入背包的物品，使得装入背包中物品的总价值最大?¢每种物品要么装入，要么不装入¢不能装入多次，也不能装入部分V输入：C>0,w>0,v>0,1≤i≤niiV输出：(x,x,…,x),