下载文档原格式
c++最大团问题分支限界法
C++最大团问题分支限界法
最大团问题是一类典型的计算机视觉算法，是一种经典的NP难问题。
它的出处可以追溯到1960年代的军事合作活动，它是一个试图确定由一系列正交关系中的最大团的问题。
为了解决该问题，具有一组称为“分支限界法”（Branch and Bound）的方法已经开发出来，它是一种基于回溯的搜索算法。
分支限界法主要是通过组合所有可能的顶点组合来求解最大团问题。
该算法从一个指定顶点顺序表开始，依次检查每个顶点，组合每个子团，直到它找到最大的团为止。
算法步骤如下：
（1）将所有顶点按照一定的顺序排序，然后将它们放入一个队列中。
（2）移除队列中的第一个顶点并将其加入当前团中。
（3）继续循环，检查剩余顶点是否需要加入当前团，如果确定它们满足条件，则将它们加入当前团。
（4）检查团大小是否达到最大值。
（5）如果当前团的大小小于最大值，则回到步骤2，继续检查剩余顶点是否可以加入团中。
（6）重复步骤2到5，直到找到最大团为止。
该算法通过在搜索空间中枚举所有可能的节点组合，来求解最大团问题。
尽管该算法可以有效地解决最大团问题，但它也存在一些弊端，例如，该算法的时间复杂度非常高（O（n^2）），因为它需要搜索所有可能的节点组合。
这就是该算法的局限性。
分支限界法求单源最短路径分支限界法是一种求解最优化问题的算法，在图论中，可以用来求解单源最短路径。
本文将介绍分支限界法的基本原理和步骤，并通过一个具体的示例来说明其应用。
一、分支限界法简介分支限界法是一种穷举搜索算法，通过不断地将问题空间划分成更小的子问题，以寻找最优解。
它与传统的深度优先搜索算法相似，但在搜索过程中，通过引入上界（界限）来限制搜索范围，从而有效地剪枝和加速搜索过程。
分支限界法求解单源最短路径问题的基本思想是，首先将源点标记为已访问，然后以源点为根节点构建一棵搜索树，树中的每个节点表示当前访问的顶点，并记录到达该顶点的路径和权值。
通过遍历搜索树，逐步更新最短路径以及当前最优权值，从而找到最短路径。
二、分支限界法的步骤1. 创建搜索树：- 将源点标记为已访问，并将其作为根节点。
- 根据源点与其他顶点之间的边权值构建搜索树的第一层。
- 初始化当前最优路径和权值。
2. 遍历搜索树：- 从当前层中选择一个未访问的顶点作为扩展节点。
- 计算到达该扩展节点的路径和权值，并更新当前最优路径和权值。
- 根据已有的路径和权值，计算该扩展节点的上界，并与当前最优权值进行比较。
若上界小于当前最优权值，则进行剪枝操作，否则继续搜索。
- 将该扩展节点的子节点添加到搜索树中。
3. 更新最短路径：- 当搜索树的所有叶子节点都已遍历时，找到最短路径以及相应的权值。
三、示例分析为了更好地理解分支限界法的运行过程，我们将通过一个具体的示例来进行分析。
假设有一个有向带权图，其中包含5个顶点和6条边。
首先，我们需要构建初始搜索树，将源点A作为根节点。
根据源点与其他顶点之间的边权值，我们可以得到搜索树的第一层B(2)、C(3)、D(4)、E(5)。
接下来，我们从第一层选择一个未访问的顶点作为扩展节点。
假设选择节点B进行扩展。
此时，我们计算到达节点B的路径和权值，并更新当前最优路径和权值。
对于节点B，到达它的路径为AB，权值为2。
分支限界算法
通俗来讲，分支限界法是一种将一个具有相互冲突和复杂约束的大型优化问题划分成一系列规模较小的子问题的方法，并以此最终获得给定问题的最优解。
它把原问题分割成几个小子问题，每个子问题都有一个限制条件，分支限界法从一个子集中选择，分支出若干解法，并把选出的最优解作为下一次算法迭代的初始解，继续作为一个新的子集挑选优解，以此迭代直至找到了全局最优解。
分支限界法的运行流程主要包括以下几个步骤：
1.初始化：确定问题的规模大小及初始解；
2.分支：根据某种规则，将现有的一个节点分成若干个候选子节点，并构建子节点与父节点之间的映射关系；
3.限界：每个候选子节点都有一个下限价值，以降低算法计算量；
4.剪枝：根据某种明确的剪枝规则，去除那些应该剪枝的节点，减少计算量；
5.搜索：递归搜索下一个更优解，直至得出最优解。
武汉理工大学算法设计与分析论文题目：分支限界法应用研究目录摘要 (1)1.绪论 (2)2分支限界法的内容 (3)2.1 分支限界法基本思想 (3)2.2 两种分支限界法 (3)2.3 分支限界法的设计思路 (4)2.4分支限界法与回溯法区别 ............... 错误！未定义书签。
3 分支限界法应用 (5)3.1批处理作业问题 (5)3.2 旅行售货员问题 (6)3.3单源最短路径问题 (12)3.4 01背包问题 (12)4.总结 (24)5.参考文献 (25)摘要分支限界法常以广度优先或以最小耗费优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。
这个过程一直持续到找到所需的解或活结点表为空时为止。
本文讲述了分支限界法的含义、基本思路及实现过程，分支限界法的核心、基本性质、特点及其存在的问题。
并通过分支限界法的特点，举例列出了以往研究过的几个经典问题，对于实际应用中的问题，也希望通过分支限界法的特点来解决。
关键词：分支限界法；解空间树；最优解；1.绪论为了解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、分支限界法等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。
虽然设计一个好的求解算法更像是一门艺术而不像是技术 ,但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法 ,你可以使用这些方法来设计算法 ,并观察这些算法是如何工作的。
一般情况下,为了获得较好的性能,必须对算法进行细致的调整。
但是在某些情况下,算法经过调整之后性能仍无法达到要求,这时就必须寻求另外的方法来求解该问题。
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。
这个过程一直持续到找到所需的解或活结点表为空时为止。
2分支限界法的内容2.1 分支限界法基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。
这个过程一直持续到找到所需的解或活结点表为空时为止。
2.2 两种分支限界法（1）队列式(FIFO)分支限界法按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
（2）优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点2.3分支限界法的设计思路设求解最大化问题，解向量为X=(x1,…,xn)，xi的取值范围为Si，|Si|=ri。
在使用分支限界搜索问题的解空间树时，先根据限界函数估算目标函数的界[down, up]，然后从根结点出发，扩展根结点的r1个孩子结点，从而构成分量x1的r1种可能的取值方式。
对这r1个孩子结点分别估算可能的目标函数bound(x1)，其含义：以该结点为根的子树所有可能的取值不大于bound(x1)，即：bound(x1)≥bound(x1,x2)≥…≥ bound(x1,…,xn)若某孩子结点的目标函数值超出目标函数的下界，则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表PT中。
再取PT表中目标函数极大值结点作为扩展的根结点，重复上述。
直到一个叶子结点时的可行解X=(x1,…,xn)，及目标函数值bound(x1,…,xn)。
2.4分支限界法与回溯法区别（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
3分支限界法应用3.1批处理作业问题（1）问题提出。
给定n 个作业的集合J={J1,J2,…,Jn}。
每一个作业Ji 都有2项任务要分别在2台机器上完成。
每一个作业必须先由机器1处理，然后再由机器2处理。
作业Ji 需要机器j 的处理时间为tji ，i=1,2,…,n ；j=1,2。
对于一个确定的作业调度，设是Fji 是作业i 在机器j 上完成处理的时间。
则所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。
批处理作业调度问题要求对于给定的n 个作业，制定最佳作业调度方案，使其完成时间和达到最小。
（2）算法分析。
在结点E 处相应子树中叶结点完成时间和的下界是：注意到如果选择Pk ，使t1pk 在k>=r+1时依非减序排列，S1则取得极小值。
同理如果选择Pk 使t2pk 依非减序排列，则S2取得极小值。
这可以作为优先队列式分支限界法中的限界函数。
（3）主要算法介绍。
do {if (enode.s == n ) { if (enode.sf2 < bestc) { bestc = enode.sf2;for (int i = 0; i < n; i++) bestx[i] = enode.x[i]; } } elsefor (int i = enode.s; i < n; i++) {∑==ni i F f 12},max{212S S F f Mi i +≥∑∈}ˆ,ˆmax{212S S Ff Mi i+≥∑∈MyMath.swap(enode.x, enode.s,i);int [] f= new int [3];int bb=bound(enode,f);if (bb < bestc ) {HeapNode node=new HeapNode(enode,f,bb,n);heap.put(node); }MyMath.swap(enode.x, enode.s,i);}算法的while循环完成对排列树内部结点的有序扩展。
在while循环体内算法依次从活结点优先队列中取出具有最小bb值（完成时间和下界）的结点作为当前扩展结点，并加以扩展。
首先考虑enode.s=n的情形，当前扩展结点enode是排列树中的叶结点。
enode.sf2是相应于该叶结点的完成时间和。
当enode.sf2 < bestc时更新当前最优值bestc和相应的当前最优解bestx。
当enode.s<n时，算法依次产生当前扩展结点enode的所有儿子结点。
对于当前扩展结点的每一个儿子结点node，计算出其相应的完成时间和的下界bb。
当bb < bestc时，将该儿子结点插入到活结点优先队列中。
而当bb≥bestc时，可将结点node舍去。
3.2 旅行售货员问题（1）问题提出。
某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。
他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。
（2）算法分析。
旅行商问题的解空间是一个排列树。
有两种实现的方法：第一种是只使用一个优先队列，队列中的每个元素中都包含到达根的路径。
另一种是保留一个部分解空间树和一个优先队列，优先队列中的元素并不包含到达根的路径。
以下为第一种方法，由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝定界法。
在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHeapNode。
每个节点包括如下区域： x（从1到n的整数排列，其中x[0] = 1 ），s（一个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s], 而剩余待访问的节点是x [s + 1 : n - 1 ]），cc（旅行路径前缀，即解空间树中从根节点到当前节点的耗费），lcost（该节点子树中任意叶节点中的最小耗费）， rcost（从顶点x[s : n - 1]出发的所有边的最小耗费之和）。
当类型为MinHeapNode( T )的数据被转换成为类型T时，其结果即为lcost的值。
程序代码：#include <stdio.h>#include <istream>using namespace std;//---------------------宏定义------------------------------------------#define MAX_CITY_NUMBER 10 //城市最大数目#define MAX_COST 10000000 //两个城市之间费用的最大值//---------------------全局变量---------------------------------------- int City_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER];//表示城市间边权重的数组int City_Size; //表示实际输入的城市数目int Best_Cost; //最小费用int Best_Cost_Path[MAX_CITY_NUMBER];//最小费用时的路径//------------------------定义结点--------------------------------------- typedef struct Node{int lcost; //优先级int cc; //当前费用int rcost; //剩余所有结点的最小出边费用的和int s; //当前结点的深度，也就是它在解数组中的索引位置int x[MAX_CITY_NUMBER]; //当前结点对应的路径struct Node* pNext; //指向下一个结点}Node;//---------------------定义堆和相关对操作-------------------------------- typedef struct MiniHeap{Node* pHead; //堆的头}MiniHeap;//初始化void InitMiniHeap(MiniHeap* pMiniHeap){pMiniHeap->pHead = new Node;pMiniHeap->pHead->pNext = NULL;}//入堆void put(MiniHeap* pMiniHeap,Node node){Node* next;Node* pre;Node* pinnode = new Node; //将传进来的结点信息copy一份保存//这样在函数外部对node的修改就不会影响到堆了pinnode->cc = ;pinnode->lcost = node.lcost;pinnode->pNext = node.pNext;pinnode->rcost = node.rcost;pinnode->s = node.s;pinnode->pNext = NULL;for(int k=0;k<City_Size;k++){pinnode->x[k] = node.x[k];}pre = pMiniHeap->pHead;next = pMiniHeap->pHead->pNext;if(next == NULL){pMiniHeap->pHead->pNext = pinnode;}else{while(next != NULL){if((next->lcost) > (pinnode->lcost)){ //发现一个优先级大的，则置于其前面pinnode->pNext = pre->pNext;pre->pNext = pinnode;break; //跳出}pre = next;next = next->pNext;}pre->pNext = pinnode; //放在末尾}}//出堆Node* RemoveMiniHeap(MiniHeap* pMiniHeap){Node* pnode = NULL;if(pMiniHeap->pHead->pNext != NULL){pnode = pMiniHeap->pHead->pNext;pMiniHeap->pHead->pNext = pMiniHeap->pHead->pNext->pNext;}return pnode;}//---------------------分支限界法找最优解-------------------------------- void Traveler(){int i,j;int temp_x[MAX_CITY_NUMBER];Node* pNode = NULL;int miniSum; //所有结点最小出边的费用和int miniOut[MAX_CITY_NUMBER];//保存每个结点的最小出边的索引MiniHeap* heap = new MiniHeap; //分配堆InitMiniHeap(heap); //初始化堆miniSum = 0;for (i=0;i<City_Size;i++){miniOut[i] = MAX_COST; //初始化时每一个结点都不可达for(j=0;j<City_Size;j++){if (City_Graph[i][j]>0 && City_Graph[i][j]<miniOut[i]){//从i到j可达，且更小miniOut[i] = City_Graph[i][j];}}if (miniOut[i] == MAX_COST){// i 城市没有出边Best_Cost = -1;return ;}miniSum += miniOut[i];}for(i=0;i<City_Size;i++){ //初始化的最优路径就是把所有结点依次走一遍Best_Cost_Path[i] = i;}Best_Cost = MAX_COST; //初始化的最优费用是一个很大的数pNode = new Node; //初始化第一个结点并入堆pNode->lcost = 0; //当前结点的优先权为0 也就是最优pNode->cc = 0; //当前费用为0（还没有开始旅行）pNode->rcost = miniSum; //剩余所有结点的最小出边费用和就是初始化的miniSumpNode->s = 0; //层次为0pNode->pNext = NULL;for(int k=0;k<City_Size;k++){pNode->x[k] = Best_Cost_Path[k]; //第一个结点所保存的路径也就是初始化的路径}put(heap,*pNode); //入堆while(pNode != NULL && (pNode->s) < City_Size-1){//堆不空不是叶子for(int k=0;k<City_Size;k++){Best_Cost_Path[k] = pNode->x[k] ; //将最优路径置换为当前结点本身所保存的}/** * pNode 结点保存的路径中的含有这条路径上所有结点的索引* * x路径中保存的这一层结点的编号就是x[City_Size-2]* * 下一层结点的编号就是x[City_Size-1] */if ((pNode->s) == City_Size-2){ //是叶子的父亲Int edge1 = City_Graph[(pNode->x)[City_Size-2]][(pNode->x)[City_Size-1]];int edge2 = City_Graph[(pNode->x)[City_Size-1]][(pNode->x)[0]];if(edge1 >= 0 && edge2 >= 0 && (pNode->cc+edge1+edge2) < Best_Cost){ Best_Cost = pNode->cc + edge1+edge2;pNode->cc = Best_Cost;pNode->lcost = Best_Cost; //优先权为 Best_CostpNode->s++; //到达叶子层}}else{ //内部结点for (i=pNode->s;i<City_Size;i++){ //从当前层到叶子层if(City_Graph[pNode->x[pNode->s]][pNode->x[i]] >= 0){//pNode的层数就是它在最优路径中的位置Int temp_cc =pNode->cc+City_Graph[pNode->x[pNode->s]][pNode->x[i]];int temp_rcost = pNode->rcost-miniOut[pNode->x[pNode->s]];//下一个结点的剩余最小出边费用和//等于当前结点的rcost减去当前这个结点的最小出边费用if (temp_cc+temp_rcost<Best_Cost){//下一个结点的最小出边费用和小于当前的最优解，说明可能存在更优解for(j=0;j<City_Size;j++){temp_x[j]=Best_Cost_Path[j];}temp_x[pNode->x[pNode->s+1]] = Best_Cost_Path[i];//将当前结点的编号放入路径的深度为s+1的地方temp_x[i] = Best_Cost_Path[pNode->s+1];Node* pNextNode = new Node;pNextNode->cc = temp_cc;pNextNode->lcost = temp_cc+temp_rcost;pNextNode->rcost = temp_rcost;pNextNode->s = pNode->s+1;pNextNode->pNext = NULL;for(int k=0;k<City_Size;k++){pNextNode->x[k] = temp_x[k];}put(heap,*pNextNode);delete pNextNode;}}}}pNode = RemoveMiniHeap(heap);}}int main(){int i,j;printf("请输入旅行的节点数");scanf("%d",&City_Size);for(i=0;i<City_Size;i++){printf("请分别输入每个节点与其它节点的路程花费");for(j=0;j<City_Size;j++){scanf("%d",&City_Graph[i][j]);}}Traveler();printf("最小花费""%d\n",Best_Cost);return 1;}实验结果如图：由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝限界法。
