算法课程设计(动态规划).doc

计算机与信息科学系
课程设计报告
课程名称:算法分析课程设计
设计题目:动态规划算法的应用
专业: 信息与计算科学
指导教师: 伍友龙
班级: 信本0802班
姓名: 廖彩霞、魏丹
学号:08301440219、08301440232
2011年6月2日
目录
一、课程设计目的 1
二、设计课题:动态规划算法的应用 1
1、实验平台 1
2、实验目的 1
3、动态规划算法的思想 1
4、解决的问题 2
最优二叉树搜索 2
最长公共子序列 6
防卫导弹 8
滑雪问题 9
矩阵连乘问题 12
凸多边形最优三角问题 15
最大子段和 17
三、设计总结 23
四、参考文献 23
一、课程设计目的
1、本算法分析与设计课程设计是综合分析和理解动态规划算法,综合运用C、C++或JAVA等程序设计语言,自行实现一系列的经典问题。
2、通过课程设计,自己更加熟练掌握算法的分析、算法设计、编程调试,写实验报告等环节,进一步掌握和灵活运用各种程序设计语言在问题实现中的应用。
3、学会将知识应用于实际的方法,提高分析和解决问题的能力,增加综合能力。
总之,本课程设计的目的是使学生掌握算法分析与设计的一半规律和思想,以提高学生的编程能力和解决实际问题的能力。
二、设计课题:动态规划算法的应用
1、实验平台
VC++
2、实验目的
通过实验,掌握面向对象编程的分析设计方法,以及与面向对象技术相关的一些软件开发技术,掌握在 VisualC++6环境下进行可视化程序设计技术。通过实践,为进一步开展相关领域的学习和科研打下良好的基础。
3、动态规划算法的思想:
1)、动态规划算法的基本要素
最优子结构
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。在分析问题的最优子结构性质时,所用的方法具有普遍性:首先假设由问题的最优解导出的子问题的解不是最优的,然后再设法说明在这个假设下可构造出比原问题最优解更好的解,从而导致矛盾。利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
重叠子问题
递归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。这种性质称为子问题的重叠性质。动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果。通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间,从而获得较高的解题效率。
2)、解题步骤
找出最优解的性质,并刻画其结构特征
递归地定义最优值
自底向上的方式计算出最优值
根据计算最优值是得到的信息,构造最优解。
4、解决的问题
1)、最优二叉树搜索
2)、最长公共子序列
3)、防卫导弹
4)、滑雪问题
5)、矩阵连乘最长公共子序列
6)、凸多边形最优三角问题
7)、最大子段和问题
8)、01背包问题
最优二叉树搜索
问题描述
给定一个有序序列K={k1<k2<k3<,……,<kn}和他们被查询的概率P={p1,p2,p3,……,pn},要求构造一棵二叉查找树T,使得查询所有元素的总的代价最小。对于一个搜索树,当搜索的元素在树内时,表示搜索成功。当不在树内时,表示搜索失败,用一个“虚叶子节点”来标示搜索失败的情况,因此需要n+1个虚叶子节点{d0<d1<……<dn}。其中d0表示搜索元素小于k1的失败结果,dn表示搜索元素大于kn的失败情况。di(0<i<n)表示搜索节点在ki和k(i+1)之间时的失败情况。对于应di的概率序列是Q={q0,q1,
……,qn}。
2. 问题分析:
在二叉树中T内搜索一次的期望代价为:
E[T]= (depth(ki)+1)*pi //对每个i=1~n,搜索成功情况+(depth(di)+1)*qi //对每个i=0~n,搜索失败情况。
3. 问题求解
步骤一:寻找最优子结构。
一个最优二叉树的子树必定包含连续范围的关键字ki~kj,1<=i<=j<=n,同时也必须含有连续的虚叶子节点di-1~dj。
如果一棵最优二叉查找树T有一棵含有关键字ki~kj的子树T',那么,T'也是一棵最优查找树,这通过剪贴思想可以证明。
现在开始构造最优子结构:在ki~kj中,选定一个r,i<=r<=j,使以kr为根,ki~k(r-1)和k(r+1)~kj为左右孩子的最优二叉树。注意r=i或者r=j的情况,表示左子树或右子树只有虚叶子节点。
步骤二:一个递归解。
定义e[i,j]为一棵包含关键字ki~kj的最优二叉树的期望代价。当j=i-1