文档介绍：摘要
算法设计与分析,其实可以解释为一类优化问题,一般针对可以利用计算机解决的离散型问题的优化。主要目的就是为了解决某一问题而提出的各种不同的解决方案,并且要针对具体问题做细致的空间与时间复杂度分析。本文通过计算机算法分析设计出解最优二叉搜索树问题的动态规划算法和设计出解图的着色问题全部可行解的回溯法算法,利用C++语言编写程序实现算法。
动态规划算法是将待求解的问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。首先找出最优解的性质,并刻画其结构特征,然后递归的定义最优值(写出动态规划方程)并且以自底向上的方式计算出最优值,最后根据计算最优值时得到的信息,构造一个最优解。
回溯法算法是确定了解空间的组织结构后,回溯法就是从开始节点(根结点)出发,以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点处,搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点,并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动,则当前的扩展结点就成为死结点。换句话说,这个节点,这个结点不再是一个活结点。此时,应往回(回溯)移动至最近一个活结点处,并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索,直到找到所要求的解或解空间中以无活结点为止。即通过确定初始解和剪枝函数原则画出状态图进行搜索产生全部可行解。
关键词:动态规划;二叉搜索树;回溯法;剪枝原则;C++
目录
一、课程设计目的 1
二、课程设计内容 1
三、概要设计 1
动态规划—最优二叉搜索树 1
回溯法—图的着色 1
四、详细设计与实现 2
动态规划—最优二叉搜索树 2
2
3
4
4
回溯法—图的着色 6
图的m着色问题描述 6
算法设计 7
8
总结 13
参考文献 14
一、课程设计目的
《计算机算法设计与分析》这门课程是一门实践性非常强的课程,要求我们能够将所学的算法应用到实际中,灵活解决实际问题。通过这次课程设计,能够培养我们独立思考、综合分析与动手的能力,并能加深对课堂所学理论和概念的理解,可以训练我们算法设计的思维和培养算法的分析能力。
二、课程设计内容
1、动态规划:设计出解最优二叉搜索树问题的动态规划算法;
回溯法:设计出解图的着色问题全部可行解的回溯法算法。
三、概要设计
动态规划—最优二叉搜索树
动态规划的基本思想是将问题分解为若干个小问题,解子问题,然后从子问题得到原问题的解。设计动态规划法的步骤:
找出最优解的性质,并刻画其结构特征;
(2)递归地定义最优值(写出动态规划方程);
(3)以自底向上的方式计算出最优值;
(4)根据计算最优值时得到的信息,构造一个最优解。
回溯法—图的着色
回溯法的基本思想是确定了解空间的组织结构后,回溯法就是从开始节点(根结点)出发,以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点处,搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点,并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动,则当前的扩展结点就成为死结点。换句话说,这个节点,这个结点不再是一个活结点。此时,应往回(回溯)移动至最近一个活结点处,并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索,直到找到所要求的解或解空间中以无活结点为止。
用回溯法解决图的着色问题的步骤:
(1)针对所给问题,定义问题的解空间;
(2)确定易于搜索的解空间结构;
(3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数原则避免无效搜索。
四、详细设计与实现
动态规划—最优二叉搜索树
设是有序集,且,表示有序集S的二叉搜索树利用二叉树的结点存储有序集中的元素。它具有下述性质:存储于每个结点中的元素x大于其左子树中任一结点所存储的元素,小于其右子树中任一结点所存储的元素。二叉树的叶结点是形如的开区间,在表示S的二叉搜索树中搜索元素x,返回的结果有两种情况:
(1)在二叉搜索树的内结点中找到。
(2)在二叉搜索树的叶结点中确定。
设在第(1)中情形中找到元素的概率为;在第(2)种情形中确定的概率为。其中约定。显然有:
称为集合S的存取概率分布。
在表示S的二叉搜索树T中,设存储元素的结点深度为;叶结点
的