算法课程设计 信息与计算科学.doc

成 绩 评 定 表学生姓名班级学号专 业课程设计题目1.分支限界解决最大团问题2.回溯法解决0-1背包问题评语组长签字：成绩日期 20 年 月 日课程设计任务书学 院理学院专 业信息与计算科学学生姓名班级学号课程设计题目1.分支限界解决最大团问题2.回溯法解决0-1背包问题实践教学要求与任务:1、巩固和加深对计算机算法分析与设计基本知识的理解。2、初步掌握简单软件的分析方法和设计方法。3、了解与课程有关的工程技术规范，能正确解释和分析设计结果。4、具体任务（1）分支限界解决布线问题（2）动态规划解决最长公共子序列问题。工作计划与进度安排:第一天 查阅资相关料； 第二、三天 程序设计； 第四天 程序调试； 第五天 答辩指导教师： 201 年 月 日专业负责人：201 年 月 日学院教学副院长：201 年 月 日摘 要“计算机算法设计与分析” 着重介绍了计算机算法设计领域的基本原则和根本原理。深入分析了一些计算机模型上的算法，介绍了一些和设计有效算法有关的数据结构和编程技术，为读者提供了有关递归方法、分治方法和动态规划方面的详细实例和实际应用，并致力于更有效算法的设计和开发。同时，对NP完全等问题能否有效求解进行了分析，并探索了应用启发式算法解决问题的途径。本文第一问，最大团问题又称为最大独立集问题（Maximum Independent Set Problem），在市场分析、方案选择、信号传输、计算机视觉、故障诊断等领域具有非常广泛的应用。目前，求解MCP问题的算法主要分为两类：确定性算法和启发式算法。确定性算法有回溯法、分支限界法等，启发式算法蚁群算法、顺序贪婪算法、DLS-MC算法和智能搜索算法等。不管哪种算法，都要求在多项式时间内求得MCP问题的最优解或近似解。图分为有向图和无向图，本文主要研究分支限界算法求解无向图最大团问题。本文第二问，掌握回溯法的原理，并能够按其原理编程实现0-1背包问题，以加深对其的理解。关键字：分支限界；最大团问题；回溯法12目 录1 分支限界解决最大团问题11.1 问题重述11.2 问题分析11.3 算法分析与设计21.4 算法的实现与结果32 回溯法解决0-1背包问题72.1 问题重述72.2 问题分析72.3 算法分析与设计72.4 算法实现与结果8参考文献121 分支限界解决最大团问题1.1问题重述给定一个无向图1.1=(V，E)，找出此无向图的最大团。如果VU，且对任意u，v U有(u，v) E，则称U是G的完全子图。G的完全子图U是G的一个团，当且仅当U不包含G的更大完全子图。G的最大团是指G中所含顶点数最多的团。 无向完全图： 设G=（V,E）为N阶无向图，若G中的任何顶点都以其余的N-1个顶点相邻，则称G为N阶无向图。 完全子图：给定G=(V,E)，如果U为G的子图并且是完全图，则称为完全子图 团：设U为G完全子图,当图U不包含G的更大完全子图时，称U是G的一个团。1.2问题分析最大团问题作为一个整数规划问题有许多等价的描述，整数规划问题描述如下：设t: (0,1)n2v，t(x)=iV: xi=1，x0,1n，S2v，则x=t-1(S)=xi: i=1,2,n，其中，n为图的顶点数。 (1)s.t. 。如果x*是式(1)的最优解，则集合C=t(x*)是图G的一个最大团，且|C|=-f(x*)。由于xi, xj0,1，xi+xj1，(i, j)当且仅当xixj=0，有，其中为图G的补图G的邻接矩阵。MCP问题等价于下面的全局二次0/1问题： (2)s.t. x0,1n其中A=AG-I。如果x*是式(2)的最优解，则集合C=t(x*)是图G的一个最大团，且|C|=-f(x*)。1.3算法分析与设计算法设计：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树时表示问题解空间的一棵有序树，常见的由子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法的主要不同在于它们对当前扩展结点所采用的扩展方式。在分支限界法中，每一个活结点只有一次机会成为扩展检点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点总，导致不可行的解或者非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后从活结点表中取下一结点成为当前扩展结点，并重复上述扩展过程。这个过程一直持续到找到所需的解或活结点表空为止。具体方法：用变量cliqueSize表示与该结点相应的团的顶点数；level表示结点在子集空间树中所处的层次；用cliqueSize +n-level+1作为顶点数上界upperSize的值。 在此优先队列式分支限界法中，upperSize实际上也是优先队列中元素的优先级。算法总是从活结点优先队列中抽取具有最大upperSize值的元素作为下一个扩展元素。子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0。 算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其他顶点之间是否有边相连。当顶点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。接着继续考察当前扩展结点的右儿子结点。当upperSizebestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。算法的while循环的终止条件是遇到子集树中的一个叶结点（即n+1层结点）成为当前扩展结点。 对于子集树中的叶结点，有upperSizecliqueSize。此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。1.4算法的实现与结果代码如下：#include stdafx.h# include # include # include # include using namespace std;typedef structint v; /无向图G的顶点int e; /无向图G的边int a5050; /定义图G的邻接矩阵int bestx50; /最优解MCP;void Creat(MCP &G) int i,j;ifstream fin(data.txt);if(!fin)cout不能打开文件:data.txtG.v;for(int i=1;i=G.v;i+)for(int j=1;jG.aij; for(i=1;i=G.v;i+) /初始化 G.bestxi=0;coutendl;cout 优先队列式分支限界法求解最大团问题endl;coutendl;cout输入初始化无向图矩阵为:endl; /初始化 for(i=1;i=G.v;i+) for(j=1;j=G.v;j+) coutG.aij ; coutendl; struct BBNode BBNode *parent; /指向父结点的指针 bool LChild; /左儿子结点标志;struct CliqueNode /定义优先队列类型为CliqueNode int cn; /当前团的顶点数 int un; /当前团最大顶点数的上界 int level; /结点在子集空间树种所处的层次 BBNode *p; /指向活结点在子集树中相应结点的指针 bool operator(const CliqueNode& b) const /un) return true; if(b.un=un & cn) return true; else return false; ;void BBMaxClique(MCP &G) BBNode *E=new(BBNode); /定义B代表记录的队列情况 /初始化 int j,i=1; int cn=0,bestn=0; int OK=1; priority_queue Q; /定义优先队列Q E-LChild=false; /初始化 E-parent=NULL;while(i!=G.v+1)/非叶结点 /检查顶点i与当前团中其它顶点之间是否有边相连 OK=1; BBNode *B=E; /把当前点的数据给B，B为中间变量 for(j=i-1;j0;B=B-parent,j-) if(B-LChild & G.aij=0) /如果不满足就停止 OK=0; break; if(OK) /满足条件，即左儿子结点为可行结点 CliqueNode *D=new(CliqueNode); /定义一个节点D D-p=new(BBNode); if(cn+1bestn) bestn=cn+1; D-cn=cn+1; D-level=i+1; D-p-LChild=true; D-p-parent=E; D-un=cn+1+G.v-i; Q.push(*D); /进队列 if(cn+G.v-ibestn ) /不满足条件但是还是可能有最优解 CliqueNode *D=new(CliqueNode); /定义一个节点D D-p=new(BBNode); D-cn=cn; D-level=i+1; D-p-LChild=false; D-p-parent=E; D-un=cn+G.v-i; Q.push(*D); /进队列 CliqueNode N; N=Q.top(); /取队顶元素，最大堆 Q.pop(); /删除队顶元素 E=N.p; /记录当前团的信息 cn=N.cn; /记录当前团的顶点数 i=N.level; /所在的层次 for(j=G.v;j0;j-) /保存最优解 G.bestxj=E-LChild; E=E-parent; bestn=cn; void main() MCP G; Creat(G); BBMaxClique(G);cout0;i-) if(G.bestxi=1) couti ; cout)endl;getch();运行结果与分析：分支限界法由“分支”策略和“限界”策略两部分组成。“分支”体现在对问题空间是按广度优先搜索；“限界”策略是为了加速搜索速度而采用启发式剪枝的策略。算法性能往往并不是很好，因此，常借鉴算法之间优势互补策略，形成新的混合启发式算法来求解最大团问题。对算法设计与分析的基础知识有了更进一步的了解和学习。在收获的同时，也丰富了自己的知识，同过查阅书籍，网上查资料，使我对原本陌生的知识又有了进一步的了解，通过不断的努力，难关最终被攻破，这是一种成就感，独立思考问题的能力，动手操作的能力都有了很大程度的提高。2 回溯法解决0-1背包问题2.1 问题重述给定n种物品和一个背包，物品的重量是，其价值为一个载重量为，背包的容量为c，应该如何选择装入背包中的物品，使得装入背包的物品的总价值最大？（在选择装入背包物品时，对每种物品只有二种选择，即装入背包或不装入背包。不能将物品装入背包多次，也不能只装入部分的物品。因此，该问题称为01背包问题）2.2问题分析0-1背包问题可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树中有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余物品价值总和；cp是当前价值;bestp是当前最优价值。当cp+r=bestp时，可剪去右子树。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。2.3算法分析与设计算法分析：动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中，这就是动态规划法的基本思路。算法设计：1.由0-1背包问题的最优子结构性质，建立计算mij的递归式如下：2.查找装入背包物品的回溯函数：从0-1二叉树的根开始搜索：若是叶子节点，则判断此时的价值是否比当前最优的价值大，否则将之替换，并获得最优解向量且返回；若不是叶子节点，则向左右子树搜索，先改变当前的数据状态，递归的调用自己，然后恢复数据状态表示回溯。3.边界函数bound 主要是当还未搜索到叶子节点时，提前判断其子树是否存可能存在更优的解空间，否则进行回溯，即裁剪掉子树的解空间。2.4算法实现与结果代码如下：#includeusing namespace std;double c;/背包容量int n; /物品数double w100;/物品重量数组double p100;/物品价值数组double cw=0;/当前重量double cp=0;/当前价值double bestp=0;/当前最优值double bound(int i) double cleft,b; /计算上界 cleft=c-cw;/剩余容量 b=cp; /以物品单位重量价值递减序装入物品 while(i=n&wi=cleft) cleft-=wi; b+=pi; i+; /装满背包 if(in) if(cpbestp) bestp=cp; return; if(cw+wibestp)/搜索右子树 Backtrack(i+1);double Knapsack (double pp,double ww,double d)int i;double TP=0,TW=0;cw=0.0;cp=0.0;bestp=0.0;