算法课程设计

摘要当今科技迅速发展，运用计算机解决实际问题变得异常重要。尤其是运用计算机实现算法设计具要重大意义。算法设计与分析，其实可以解释为一种优化问题，一般是对可以利用计算机解决的离散型问题的优化。主要目的就是为了解决某一问题而提出的各种不同的解决方案，并且要针对具体问题做细致的空间与时间复杂度分析。本文是运用动态规划法解决租用游艇问题和回溯法解决部落卫队问题。利用C++编程实现算法。动态规划算法是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。首先找出最优解的性质，并刻画其结构特征，然后递归的定义最优值（写出动态规划方程）并且以自底向上的方式计算出最优值，最后根据计算最优值时得到的信息，构造一个最优解。回溯法算法是确定了解空间的组织结构后，回溯法从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结点。此时，应往回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。即通过确定初始解和剪枝函数原则画出状态图进行搜索产生全部可行解。关键字：动态规划法、租用游艇问题、回溯法、部落卫队问题、C++目录一、动态规划法解决租用游艇问题..........................11.1问题重述..........................................11.2问题分析..........................................11.3算法原理与设计....................................11.3.1算法原理.....................................11.3.2算法设计.....................................21.4算法实现与结果....................................31.5结果描述..........................................4二、回溯法解决部落卫队问题...............................52.1问题重述..........................................52.2问题分析..........................................52.3算法原理及设计.....................................52.3.1算法原理......................................52.3.2算法设计......................................62.4算法实现..........................................72.5结果描述..........................................9三、总结................................................11参考文献................................................121一、动态规划法解决租用游艇问题1.1问题重述长江游艇俱乐部在长江上设置了n个游艇出租站1,2,…,n。有可以游艇出租站用游艇并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1=ij=n。试设计一个算法，计算游艇出租站1到出租站n所需的最少租金。对于给定的游艇出租站i到游艇出租站j之间的租金为r(i,j),1=ij=n，编程计算从游艇出租站1到游艇出租站n所需的最少租金。由文件提供输入数据。文件的第1行中有1个正整数n（n=200），表示有n个游艇出租站。接下来的n-1行是一个半矩阵r(i,j),1=ij=n。程序运行结束时，将计算出的从游艇出租站1到游艇出租站n所需的最少租金输出到文件中。输入文件示例输出文件示例1231251571.2问题分析将每个出租站看作一个点，站与站之间的关系可以用有向无环图表示，同时站与站之间的租金为边的权。此问题可转化成求站1到站n的最短路径问题。用动态规划求解，递推方程如下所示：定义f[i][j]为站点i到站点j的最少租金。[i][j]=in{[i][][][j]},ikj,1=i,j=n.初始最优解为[1][n]。1.3算法原理与设计1.3.1算法原理本文主要适用动态规划法的思想求解，其基本思想时将原问题分解为若干个2子问题，先求解子问题，然后从这些子问题的解得到原问题的解。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优(最大或最)值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。设计动态规划法一般包含以下4个步骤为：找出最优解的性质，并刻画其结构特征；递归地定义最优值；以自底向上的方法计算出最优解；根据计算最优值得到的信息，构造最优解。1.3.2算法设计intmain(){intnum,i,j,k;for(k=2;knum;k++){for(i=0;inum-k;i++){intmark=i+k;for(j=i+1;jmark;j++){if(list[i][j]+list[j][mark]list[i][mark]){list[i][mark]=list[i][j]+list[j][mark];}}}}coutlist[0][num-1];return0;}3本课设中list[0][n-1]代表所用租金最少，n为游艇出租站的个数。List[i][j]表示从第i个游艇出租站到第j个游艇出租站的费用（其中ij）。当list[i][j]+list[j][mark]list[i][mark]时，list[i][mark]=list[i][j]+list[j][mark]。则递归方程为list[0][n-1]=min{list[0][k]+list[k][n-1],list[0][n-1]}1.4算法实现与结果程序代码：#includeiostream#includevectorusingnamespacestd;intmain(){intnum,i,j,k,tmp;cinnum;vectorvectorintlist;vectorintline;for(i=0;inum-1;i++){list.push_back(line);for(j=0;j=i;j++)//在容器前面添加些0，从而使list[i][j]表示从第i个出租站到第j个出租站所需的金额{//同时也去除无效的表示，比如list[0][0]直接赋值为0，从而使后面的计算更方便list[i].push_back(0);}for(j=i+1;jnum;j++){cintmp;list[i].push_back(tmp);//从i+1个出租站到第j+1个出租站所需金额}}for(k=2;knum;k++)//从两个出租站开始，逐步计算每几个出租站之间的最优解，最终计算num-1个出租站合并的最优解{for(i=0;inum-k;i++){intmark=i+k;for(j=i+1;jmark;j++){4if(list[i][j]+list[j][mark]list[i][mark])//例如list[0][1]+list[1][2]list[0][2],则改变list[0][2]的值{list[i][mark]=list[i][j]+list[j][mark];}}}}coutlist[0][num-1];return0;}1.5结果描述运行结果如图1.1所示。图1.1租用游艇问题运行结果如图1所示，含有3个游艇出租站，从出租站1到出租站2，3分别需要租金为5，15，从出租站2到出租站3需要租金为7，则运用动态规划法求解出从出租站1到出租站3所需最少租金为12。5二、回溯法解决部落卫队问题2.1问题重述原始部落byteland中的居民们为了争夺有限的资源，经常发生冲突。几乎每个居民都是他的仇敌。部落酋长为了组织一支保卫部落的队伍，希望从部落的居民中选出最多的居民入伍，并保证队伍中任何2个人都不是仇敌。2.2问题分析本问题为组织一支队伍保卫部落，并且卫队中任意2人不能有仇敌关系，因而，实际可考虑在居民中选择一个最大独立团体问题。构建一个树状图G,居民为树状图G的顶点，居民间的关系为树状图的边界线。“1”表示两个居民间没有仇敌关系，“0”表示两个居民间有仇敌关系。这样最大独立团问题就成了图G顶点集的子集的选取问题，可用子集树表示问题的解空间。设当前考察结点位于解空间树的第i层。先考虑顶点到要选入独立团中的所有结点都要相连（即无仇敌关系）且任意两个结点都仇敌关系，然后进入左子树进行深度优先遍历，在进入右子树。2.3算法原理及设计2.3.1算法原理具有限界函数的深度优先的方式系统第搜索问题的解的算法称为回溯法。它可以系统地搜索某一个问题的所有解或任一解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。它适用于解一些组合数较大的问题。6回溯法搜索解空间树时，通常采用两种策略避免无效搜索，提高回溯法的搜索效率。其一是用约束函数在扩展结点处剪去不满足约束的子树；其二是用限界函数剪去得不到最优解的子树。这两类函数统称为剪枝函数。问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。运用回溯法解题通常包含以下3个步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。对于本题来说，回溯法操作步骤如下：(1)针对所给问题，定义问题的解空间；确定易于搜索的解空间结构；以深度优先方式搜索解空间，并在搜索过程中利用剪枝函数剪去无效的搜索。(2)无向图G的最大团问题可以看作是图G的顶点集V的子集选取问题。因此可以用子集树表示问题的解空间。设当前扩展节点Z位于解空间树的第i层。在进入左子树前，必须确认从顶点i到已入选的顶点集中每一个顶点都有边相连。在进入右子树之前，必须确认还有足够多的可选择顶点使得算法有可能在右子树中找到更大的团。(3)用邻接矩阵表示图G，n为G的居民数，cn存储当前卫队数，bestn存储最大卫队人数。cn+n-i为进入右子树的上界函数，