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

《算法课程设计(动态规划)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、HUNANINSTITUTEOFTECHNOLOGY机与信息科学课程设计报告课程名称：算法分析课程设计设计题目：动态规划算法的应用专业：信息与计算科学指导教师：伍友龙班级：信本0802班姓名：廖彩霞、魏丹学号：08301440219、083014402322011年6月2日一、课程设计目的1二、设计课题：动态规划算法的应用11、实验平台12、实验目的13、动态规划算法的思想14、解决的问题2最优二叉树搜索.2最长公共子序列.6防卫导弹.8滑雪问题.9矩阵连乘问题.12凸多边形最优三角问题、15最大子段和.17三、设计总结23四、参考文献23一、课程设计目的1、本算法分析与设计课程设计

2、是综合分析和理解动态规划算法，综合运用C、C++或JAVA等程序设计语言，自行实现一系列的经典问题。2、通过课程设计，自己更加熟练掌握算法的分析、算法设计、编程调试，写实验报告等环节，进一步掌握和灵活运用各种程序设计语言在问题实现中的应用。3、学会将知识应用于实际的方法，提高分析和解决问题的能力，增加综合能力。总之，本课程设计的目的是使学生掌握算法分析与设计的一半规律和思想，以提高学生的编程能力和解决实际问题的能力。二、设计课题：动态规划算法的应用1、实验平台VC++6.02、实验FI的通过实验，掌握面向对象编程的分析设计方法，以及与面向对象技术相关的一些软件开发技术，掌握在Visu

3、alC++6环境下进行可视化程序设计技术。通过实践，为进一步开展相关领域的学习和科研打下良好的基础。3、动态规划算法的思想：1）、动态规划算法的基本要素•最优子结构矩阵连乘计算次序问题的最优解包含着其了问题的最优解。这种性质称为最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。重叠子问题递归算法求解问题时，每次产

4、生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。2）、解题步骤•找出最优解的性质，并刻画其结构特征•递归地定义最优值•自底向上的方式计算出最优值•根据计算最优值是得到的信息，构造最优解。4、解决的问题1）、最优二叉树搜索2）、最长公共子序列3）、防卫导弹4）、滑雪问题5）、矩阵连乘最长公共子序列6）、凸多边形最优三角问题7）

5、、最大子段和问题8）、01背包问题最优二叉树搜索1.问题描述给定一个有序序列K={kl

6、,qn｝。2.问题分析：在二叉树中T内搜索一次的期望代价为：E[T]=(depth(ki)+l)*pi//对每个i=Pn,搜索成功情况+(depth(di)+l)*qi//对每个i二Ob,搜索失败情况。3.问题求解步骤一：寻找最优子结构。一个最优二叉树的子树必定包含连续范围的关键字ki~kj,1〈二iUj〈二n,同时也必须含有连续的虚叶子节点di-rdjo如果一棵最优二叉查找树T有一棵含有关键字ki〜kj的子树T',那么，T'也是一棵最优查找树，这通过剪贴思想可以证明。现在开始构造最优子结构：在ki~kj中，选定一个r,i<=r<=j,使以好为根,kPk(r-1)和k(r+l厂kj为

7、左右孩子的最优二叉树。注意r=i或者r=j的情况，表示左子树或右子树只有虚叶子节点。步骤二：一个递归解。定义c[i,j]为一棵包含关键字kPkj的最优二叉树的期望代价。当沪i-l时没有真实的关键在，只有虚叶子节点d(i-l)o于是：当j二i-1时，e[i,i-l]=q(i-l)o当j>=i时，需要选择合适的kr作为根节点，然后其余节点ki^K(r-1)和k(r+l)~kj构造左右孩子。这时要考虑左右孩子这些节点成为一个节点的子树后，它的搜索代价的变化：根据