0037算法笔记——【分支限界法】最大团问题

分支限界法解题算法框架分支限界法是一种建模和求解复杂优化问题的有效算法，它源于笛卡尔的科学思想，被认为是能够解决复杂优化问题的革命性工具。

它的基本思想是：分支限界法以树状结构的方式求解优化问题，不断的分割搜索空间，找到最优解。

1、分支限界法的基本概念分支限界法是求解优化问题的一种方法，它将解空间划分为若干个子空间，在每个子空间中评估优化指标，根据分支限界准则，搜索最优解。

它主要分为以下几个步骤：（1）定义一个有限的决策空间，并设置目标函数的优化指标；（2）将决策空间划分为若干个子空间，并设置有效限界和分裂标准；（3）在每个子空间中进行搜索，并进行评价；（4）根据评价结果，重复（2）、（3）步骤，直至满足停止条件，搜索得到最优解。

2、分支限界法的优势分支限界法是一种求解优化问题的有效算法，它在优化技术中占有很重要的地位。

其优势在于：（1）分支限界法可以使用更少的计算量，求解复杂的优化问题；（2）分支限界法采用分支和分割的方式，可以更好的避免搜索局部最优，获得更可靠的最优解；（3）分支限界法可以认为是一种智能化、自适应的搜索技术，它可以有效提高计算效率；（4）分支限界法易于理解，实现比较容易，可以节省程序员的工作量和计算时间。

3、案例应用分支限界法在很多领域有广泛的应用，其中最常见的应用是解决资源分配问题。

可以将需要分配的资源划分为若干个变量，然后使用分支限界法寻找该资源分配问题的最优解。

在运输问题中，如果要在有限的时间内最大限度地利用车辆从一个汽车站点出发，向其他若干个目的地发送货物，可以使用分支限界法来求解，以便在有限的时间内找到最优解。

在装配线调度问题中，如果要解决多个工序同时进行的装配线调度问题，则可以使用分支限界法来求解。

4、总结分支限界法解题算法是一种求解优化问题的有效算法，它将求解空间划分为若干个子空间，采用分支和分割的方式，找到最优解。

该算法具有计算量小、避免搜索局部最优、易于实现等优点，可以用于解决复杂优化问题，在资源分配、运输、装配线调度等领域都有广泛的应用。

一、分支限界法：分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。

但在一般情况下，分支限界法与回溯法的求解目标不同。

回溯法的求解目标是找出T 中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。

回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。

分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。

为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

二、分支限界法的基本思想：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。

在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。

在分支限界法中，每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。

这个过程一直持续到找到所求的解或活结点表为空时为止。

三、选择下一扩展结点的不同方式：从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。

最常见的有以下两种方式：1、队列式(FIFO)分支限界法：队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点。

算法分析与设计分支限界法分支限界法是一种常用的优化算法，它通过剪枝和分支的方式在空间中找到最优解。

在算法设计与分析中，分支限界法在求解组合优化问题和图论问题中有广泛应用。

分支限界法的基本思想是将问题划分为一个个子问题，并对每个子问题进行求解，同时通过剪枝操作减少空间。

算法从一个初始状态开始，通过扩展子节点来生成树。

在每个节点上，先判断该节点是否需要剪枝操作。

如果需要剪枝，则舍弃该节点及其子节点；如果不需要剪枝，则继续扩展该节点为新的可能解。

通过不断扩展和剪枝操作，最终找到最优解。

分支限界法的核心是选择一个合适的策略来确定节点的扩展顺序。

常用的策略包括优先级队列、最小堆、最大堆等。

这些策略可以根据问题的性质和特点来选择，以保证效率。

同时，剪枝操作也是分支限界法中关键的一环。

剪枝操作有多种方式，如上界和下界剪枝、可行剪枝、标杆剪枝等。

通过剪枝操作，可以减少空间，提高算法的效率。

分支限界法的时间复杂度通常是指数级别的，因为每个节点需要根据策略进行扩展，并进行剪枝操作。

然而，通过合理选择策略和剪枝操作，可以显著减少空间，降低时间复杂度。

此外，分支限界法还可以通过并行计算等技术进一步提高效率。

分支限界法在求解组合优化问题中有广泛应用。

组合优化问题是在有限的资源条件下，通过组合和选择来达到最优解的问题。

例如，旅行商问题、背包问题等都是经典的组合优化问题，而分支限界法可以在有限的时间内找到最优解。

在图论问题中，分支限界法也有重要的应用。

例如，最短路径问题、图着色问题等都可以通过分支限界法求解。

总之，分支限界法是一种基于和剪枝的优化算法，通过合理选择策略和剪枝操作，在有限的时间内找到最优解。

该算法在组合优化问题和图论问题中有广泛应用，可以有效提高问题求解的效率。

在实际应用中，可以根据问题性质和特点选择合适的策略和剪枝操作，以达到最佳的求解效果。

摘要最大团问题（Maximum Clique Problem, MCP）是现实世界中一类真实问题，在市场分析、方案选择、信号传输、计算机视觉、故障诊断等领域具有非常广泛的应用。

自1957年Hararv和Ross首次提出求解最大团问题的确定性算法以来，研究者们已提出了多种确定性算法来求解最大团问题。

但随着问题规模的增大（顶点增多和边密度变大），求解问题的时间复杂度越来越高，确定性算法显得无能为力，不能有效解决这些NP完全问题。

最大团问题又称为最大独立集问题（Maximum Independent Set Problem），在市场分析、方案选择、信号传输、计算机视觉、故障诊断等领域具有非常广泛的应用。

目前，求解MCP问题的算法主要分为两类：确定性算法和启发式算法。

确定性算法有回溯法、分支限界法等，启发式算法蚁群算法、顺序贪婪算法、DLS-MC算法和智能搜索算法等。

不管哪种算法，都要求在多项式时间内求得MCP问题的最优解或近似解。

图分为有向图和无向图，本文主要研究确定性算法求解无向图最大团问题。

根据算法的设计结果，采用C++语言在Visual Studio 2008上实现算法，通过测试分析，结果运行正确。

关键词：最大团问题，分支限界法，MCP目录1 问题描述 (1)2 问题分析 (2)3 建立数学模型 (4)4 算法设计 (5)5 算法实现 (6)6 测试分析 (10)结论 (11)参考文献 (12)1 问题描述给定一个无向图1.1=(V，E)，找出此无向图的最大团。

如果V⊆U，且对任意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的一个团。

分支限界法概述：分支定界(branch and bound) s搜索法是一种在问题的解空间树上搜索问题的解的方法。

分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。

搜索策略1 产生当前扩展结点的所有孩子结点；2 在产生的孩子结点中，抛弃那些不可能产生可行解（或最优解）的结点；3 将其余的孩子结点加入活结点表；4 从活结点表中选择下一个活结点作为新的扩展结点。

5 如此循环，直到找到问题的可行解（最优解）或活结点表为空。

从活结点表中选择下一个活结点作为新的扩展结点根据选择方式的不同分支定界算法通常可以分为两种形式：①队列式（FIFO）分支限界法队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点②优先队列式的分支限界法将活结点表组织成一个队列，并按优先队列中规定的优先级选取优先级最高的下一个节点成为当前扩展节点最大优先队列：使用最大堆，体现最大效益优先最小优先队列：使用最小堆，体现最小费用优先分支限界法和回溯法的区别①求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有解分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解②搜索方式不同：回溯法以深度优先的方式搜索解空间树分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树③搜索问题的解空间树方面：在分支限界法中，每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。

这个过程一直持续到找到所需的解或活结点表为空时为止。

什么是剪枝（以走迷宫举例）我们在“走迷宫”的时候，一般回溯法思路是这样的：1、这个方向有路可走，我没走过2、往这个方向前进3、是死胡同，往回走，回到上一个路口4、重复第一步，直到找着出口这样的思路很好理解，编程起来也比较容易。

分支限界法解最大团问题引言最大团问题是图论中经典的组合优化问题之一，它的基本思想是在给定的无向图中寻找一个最大的完全子图，其中图中的每一对顶点都相互连接。

在实际应用中，最大团问题有着广泛的应用，例如社交网络中的好友圈筛选、任务分配问题等都可以转化为最大团问题。

分支限界法的基本思想分支限界法是一种搜索算法，其基本思想是根据当前搜索路径上的节点来限制搜索空间，从而提高搜索效率。

具体来说，分支限界法会使用一个优先级队列来存储当前搜索路径上的节点，并对队列中的节点进行排序。

每次选择优先级最高的节点进行扩展，直到找到一个解或者搜索空间为空。

分支限界法解决最大团问题的步骤1.首先，定义一个最大团的上界，将其初始化为0。

同时，定义一个空的搜索路径，用于存储当前搜索路径上的节点。

2.从图中选择一个初始节点开始搜索，将其加入搜索路径，并更新当前搜索路径的最大团上界。

3.对当前搜索路径上的节点进行扩展：-选择一个未被访问的邻节点，将其加入搜索路径；-更新当前搜索路径的最大团上界；-将扩展后的节点加入优先级队列。

4.重复步骤3，直到搜索路径为空或者不再存在更优的搜索路径。

5.搜索结束后，得到的最大团即为所求解。

示例以下是一个简单的示例来说明分支限界法解决最大团问题的过程：假设有如下无向图：A----B/|\/|\C--D-------E||||||F--G-------H初始状态下，最大团的上界为0，搜索路径为空。

从节点A开始搜索，将其加入搜索路径，并更新最大团的上界为1。

然后将未被访问的邻节点B、D加入搜索路径，并更新最大团的上界为2。

由于节点D没有未被访问的邻节点，搜索路径无法继续扩展。

此时，搜索路径上的节点为[A,B,D]，最大团的上界为2。

接下来，从优先级队列中选择下一个节点扩展。

假设选择节点B进行扩展。

将未被访问的邻节点A、E加入搜索路径，并更新最大团的上界为3。

此时，搜索路径上的节点为[A,B,E]，最大团的上界为3。

分支限界算法
通俗来讲，分支限界法是一种将一个具有相互冲突和复杂约束的大型优化问题划分成一系列规模较小的子问题的方法，并以此最终获得给定问题的最优解。

它把原问题分割成几个小子问题，每个子问题都有一个限制条件，分支限界法从一个子集中选择，分支出若干解法，并把选出的最优解作为下一次算法迭代的初始解，继续作为一个新的子集挑选优解，以此迭代直至找到了全局最优解。

分支限界法的运行流程主要包括以下几个步骤：
1.初始化：确定问题的规模大小及初始解；
2.分支：根据某种规则，将现有的一个节点分成若干个候选子节点，并构建子节点与父节点之间的映射关系；
3.限界：每个候选子节点都有一个下限价值，以降低算法计算量；
4.剪枝：根据某种明确的剪枝规则，去除那些应该剪枝的节点，减少计算量；
5.搜索：递归搜索下一个更优解，直至得出最优解。

最⼤团问题⼀、定义⼀个⽆向图 G=(V，E)，V 是点集，E 是边集。

取 V 的⼀个⼦集 U，若对于 U 中任意两个点 u 和 v，有边 (u,v)∈E，那么称 U 是 G 的⼀个完全⼦图。

U 是⼀个团当且仅当 U 不被包含在⼀个更⼤的完全⼦图中。

G的最⼤团指的是定点数最多的⼀个团。

⼆、常⽤做法1、顺序贪婪启发式搜索算法2、局部搜索启发式算法3、智能搜索启发式算法4、遗传算法5、模拟退⽕算法6、禁忌算法7、神经⽹络算法8、改进蚁群算法-AntMCP看了所列出的算法，是不是有⼀种头⽪发⿇的感觉。

反正我是这样的感觉...因为上⾯的东西我都不会...如果你想看上⾯的东西，百度百科中有⼀些简略的介绍，我太弱，没看懂。

百度百科传送门：下⾯说说常⽤的⼀种搜索算法当然，这种算法很不⾼效，所以当图中有 100 个点以上时，请慎⽤先看看⼀个显⽽易见的 DFS ： 初始化： 从⼀个点 u 开始，把这个点加⼊到⼀个集合中，设为 U。

遍历⼀遍所有和他相连的点，把他们放⼊另⼀个集合 S1中，接下来进⾏第⼀遍 DFS 第⼀遍 DFS ： 从 S1 中选择⼀个点 u1，这个点肯定和集合 U 中的任何⼀个点相连。

把集合 S1 中 u1 能访问到的点加⼊到集合 S2中，并把 u1 加⼊到集合 U 中，进⾏第⼆遍 DFS 第⼆遍 DFS ： 从 S2 中选择⼀个点 u2，这个点肯定和集合 U 中的任何⼀个点相连。

把集合 S2 中 u2 能访问到的点加⼊到集合 S3中，并把 u2 加⼊到集合 U 中，进⾏第三遍 DFS 第三遍 DFS ： 从 S3 中选择⼀个点 u3，这个点肯定和集合 U 中的任何⼀个点相连。

把集合 S3 中 u3 能访问到的点加⼊到集合 S4中，并把 u3 加⼊到集合 U 中，进⾏第四遍 DFS ...... 最底层的 DFS ： 当某个 S 集合为空集的时候，DFS 结束，这时候我们就找到了⼀个完全⼦图，⽤这个完全⼦图更新我们的最⼤团。

实验报告14课程数据结构与算法实验名称分支限界法第页班级11计本学号105032011130 姓名风律澈实验日期：2013年6月8日报告退发(订正、重做)一、实验目的掌握分支限界法的原理和应用。

二、实验环境1、微型计算机一台2、WINDOWS操作系统，Java SDK，Eclipse开发环境三、实验内容必做题：1、编写程序，采用问题。

2、编写程序，采用分支限界法求解旅行售货员问题。

四、实验步骤和结果(附上代码和程序运行结果截图)1、分支限界法最大团package分支限界最大团;public class main {/*** @param args*/public static void main(String[] args) {// TODO Auto-generated method stubint [][]a={{1,1,0,1,1},{1,1,1,0,1},{0,1,1,0,1},{1,0,0,1,1},{1,1,1,1,1}};graph g=new graph(a);g.find_answer();g.show();}}----------------------------------------------------------------------------------------------------------------------package分支限界最大团;import java.util.ArrayList;import java.util.PriorityQueue;public class graph {private ArrayList<point> points;private ArrayList<point> answer_point;public graph(int [][]a){this.points=new ArrayList<>();this.answer_point=new ArrayList<>();int n=a.length;for(int i=0;i<n;i++)this.points.add(new point());for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)if(a[i][j]==1){point pi=this.points.get(i);point pj=this.points.get(j);pi.add_nearpoint(pj);pj.add_nearpoint(pi);}}public void find_answer() {// TODO Auto-generated method stubint total_points=this.points.size();PriorityQueue<Node> enode=new PriorityQueue<>();int node_in=0;point node_point=this.points.get(0);ArrayList<point> nowanswer=new ArrayList<>();int maxnum_point=this.points.size();Node startnode=new Node(node_in,node_point,nowanswer,maxnum_point);enode.offer(startnode);Node node=null;while(true){if(enode.isEmpty())break;node=enode.poll();if(node.get_node_in()==maxnum_point)break;if(node.ifleft()){int new_node_in=node.get_node_in()+1;int new_answer=node.get_maxnum_point();point newpoint;if(new_node_in==total_points)newpoint=null;elsenewpoint=this.points.get(new_node_in);ArrayList<point> new_answer_point=new ArrayList<point>(node.get_answer_point());new_answer_point.add(node.get_node_point());Node new_node=new Node(new_node_in,newpoint,new_answer_point,new_answer);enode.offer(new_node);if(new_node.get_answer_point().size()>this.answer_point.size())this.answer_point=newArrayList<>(new_node.get_answer_point());}if(node.ifright(this.points.size(),this.answer_point.size())){ArrayList<point>new_node_answer_points=node.get_answer_point();int new_node_in=node.get_node_in()+1;int new_node_max=node.get_maxnum_point()-1;point p=this.points.get(new_node_in);Node newnode=new Node(new_node_in,p,new_node_answer_points,new_node_max);enode.add(newnode);}}}public void show(){System.out.println(this.answer_point);}}---------------------------------------------------------------------------------------------------------------------- package分支限界最大团;import java.util.ArrayList;public class point {private static int ids=1;private int id;private ArrayList<point> nearpoints;public point(){super();this.id=ids++;this.nearpoints=new ArrayList<point>();}public String toString(){return"顶点"+this.id;}public void add_nearpoint(point p){this.nearpoints.add(p);}public boolean check_if_nearpoint(point p){return this.nearpoints.contains(p);}}---------------------------------------------------------------------------------------------------------------------- package分支限界最大团;import java.util.ArrayList;public class Node implements Comparable<Node> {private int node_in;private point node_point;private ArrayList<point> answer_points;private int maxnum_point;public Node(int n,point p,ArrayList<point> a,int m){super();this.node_in=n;this.node_point=p;this.answer_points=a;this.maxnum_point=m;}public int compareTo(Node o) {// TODO Auto-generated method stubif(this.maxnum_point>o.maxnum_point) return -1;if(this.maxnum_point<o.maxnum_point) return 1;return 0;}public int get_node_in(){return this.node_in;}public ArrayList<point> get_answer_point(){return this.answer_points;}public boolean ifleft(){for(point p:this.answer_points)if(!p.check_if_nearpoint(this.node_point))return false;return true;}public boolean ifright(int total_point,int nowanswer){int leftpoint=total_point-this.node_in;if(this.answer_points.size()+leftpoint>nowanswer)return true;return false;}public int get_maxnum_point(){return this.maxnum_point;}public point get_node_point(){return this.node_point;}}-----------------------------------------------------------------------2、分支限界法求旅行售货员package旅行售货员问题;public class main {/*** @param args*/public static void main(String[] args) {int[][]a={{0,30,6,4},{30,0,5,10},{6,5,0,20},{4,10,20,0},};graph g=new graph(a);g.findanswer();g.show();}}------------------------------------------------------------------------------- package 旅行售货员问题;import java.util.ArrayList;import java.util.Collections;import java.util.PriorityQueue;public class graph {private ArrayList<point> points;private int[][] a;private ArrayList<point> answer_points;private int answerpathlong;public graph(int[][] b) {this.points = new ArrayList<>();int n = b.length;for (int i = 0; i < n; i++)this.points.add(new point());this.a = b;this.answerpathlong = Integer.MAX_VALUE;this.answer_points = null;this.set_point_short_long();}public int get_value(point px, point py) {int p1id = px.getid();int p2id = py.getid();return this.a[p1id][p2id];}public void findanswer(){PriorityQueue<Node>enode=new PriorityQueue<>();ArrayList<point> root_list=this.points;int root_answer=0;for(point p:this.points)root_answer+=p.getshortestlong();int root_in=0;int root_path_long=0;Node root_node=new Node(root_in, root_list, root_path_long, root_answer);enode.offer(root_node);while(true){if(enode.isEmpty())break;Node old_node=enode.poll();int total_point=this.points.size();if(old_node.if_end(total_point)){this.answer_points=new ArrayList<>(old_node.get_now_sort());this.answerpathlong=old_node.get_now_path_long();break;}if(old_node.if_end_father(total_point)){int new_node_in=old_node.get_node_in()+1;ArrayList<point> new_node_set=old_node.get_now_sort();point old_point_node=old_node.get_node_point();point new_point_node=new_node_set.get(new_node_in);point startpoint=this.points.get(0);intnew_node_nowpath=old_node.get_now_path_long()+this.get_value(old_point_node, new_point_node)+this.get_value(new_point_node, startpoint);int maybe_the_best=new_node_nowpath;Node new_node=new Node(new_node_in, new_node_set, new_node_nowpath, maybe_the_best);if(new_node.get_now_path_long()<this.answerpathlong){this.answerpathlong=new_node.get_now_path_long();enode.offer(new_node);}continue;}for(int i=old_node.get_node_in()+1;i<total_point;i++){//尝试原节点的各个分支if(old_node.if_in_i(i, this.a, this.answerpathlong)){int new_node_in=old_node.get_node_in()+1;ArrayList<point> newnode_nowset=new ArrayList<>(old_node.get_now_sort());int j=new_node_in;this.changeij(newnode_nowset, i, j);point old_node_to_point=old_node.get_node_point();point new_node_to_point=newnode_nowset.get(new_node_in);intnew_maybe_the_best=old_node.get_node_answer()+this.get_value(old_node_to_point, new_node_to_point)-old_node_to_point.getshortestlong();intnew_node_path_long=old_node.get_now_path_long()+this.get_value(old_node_to_poin t, new_node_to_point);Node new_node=new Node(new_node_in, newnode_nowset, new_node_path_long, new_maybe_the_best);enode.offer(new_node);}}}}private void changeij(ArrayList<point> points,int i, int j) {// TODO Auto-generated method stubCollections.swap(points, i, j);}public void show(){System.out.println(this.answer_points);System.out.println("最优路径长度为："+this.answerpathlong);}private void set_point_short_long(){point p;int[]value;for(int i=0;i<this.points.size();i++){p=this.points.get(i);value=this.a[i];for(int x:value){if(x==0)continue;if(x<p.getshortestlong())p.setshortestlong(x);}}}}------------------------------------------------------------------------------- package旅行售货员问题;public class point {private static int ids=0;private int id;private int shortestlong;public point() {super();this.id=point.ids++;this.shortestlong=Integer.MAX_VALUE;}public int getid() {return id;}@Overridepublic String toString() {return"顶点："+this.id+";";}public int getshortestlong() {return shortestlong;}public void setshortestlong(int s) {this.shortestlong = s;}------------------------------------------------------------------------------- package旅行售货员问题;import java.util.ArrayList;public class Node implements Comparable<Node>{private int node_in;private point node_point;private ArrayList<point>now_sort;private int now_path_long;private int node_answer;public Node(int in, ArrayList<point> set, int p_l,int n_a) { super();this.node_in = in;this.now_sort = set;this.now_path_long = p_l;this.node_answer = n_a;this.node_point=this.now_sort.get(in);}public boolean if_in_i(int i,int[][]a,int now_long){point now_point=now_sort.get(node_in);point pointi=now_sort.get(i);int now_id=now_point.getid();int pointi_id=pointi.getid();int value=a[now_id][pointi_id];if(value==Integer.MAX_VALUE)return false;intpointi_answer=this.node_answer+value-now_point.getshortestlong();if(pointi_answer>now_long)return false;return true;}public boolean if_end(int point_sum){if(this.node_in==point_sum-1)return true;return false;}public boolean if_end_father(int point_number){if(this.node_in==point_number-2)return true;return false;}public int get_now_path_long() {return now_path_long;public ArrayList<point> get_now_sort() {return now_sort;}public int get_node_in() {return node_in;}public int get_node_answer() {return node_answer;}public point get_node_point() {return node_point;}@Overridepublic int compareTo(Node o) {if(this.node_answer>o.node_answer)return 1;if(this.node_answer<o.node_answer)return -1;return 0;}}-----------------------------------------------------------------------五、实验总结(本次实验完成的情况，心得体会)。

0033算法笔记分支限界法分支限界法与单源最短路径问题 0033算法笔记-分支限界法分支限界法与单源最短路径问题1、分支限界法(1)叙述：使用广度优先产生状态空间一棵的结点，并采用剪枝函数的方法称作分枝限界法。

所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即为：儿子结点）。

所谓“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减去搜寻一棵的某些分支，从而提升搜寻效率。

(2)原理：按照广度优先的原则，一个活结点一旦成为扩展结点（e-结点）r后，算法将依次生成它的全部孩子结点，将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。

然后，从活结点表中取出一个结点作为当前扩展结点。

重复上述结点扩展过程，直至找到问题的解或判定无解为止。

(3)分支限界法与回溯法1)解目标：追溯法的解目标就是找到求解空间树中满足用户约束条件的所有求解，而分支限界法的解目标则就是找到满足用户约束条件的一个求解，或是在八十足约束条件的解中找出在某种意义下的最优解。

2)搜寻方式的相同：追溯法以深度优先的方式搜寻求解空间一棵，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

(4)常见的分支限界法1)fifo分支限界法(队列式分支限界法)基本思想：按照队列先进先出(fifo)原则选取下一个活结点为扩展结点。

搜寻策略：一已经开始，根结点就是唯一的活结点，根结点入队。

从活结点队中抽出根结点后，做为当前拓展结点。

对当前拓展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足用户约束函数的儿子重新加入活结点队列中。

再从活结点表抽出队首结点（队中最先进去的结点）为当前拓展结点，……，直至找出一个求解或活结点队列入空年才。

2)lc(leastcost)分支限界法(优先队列式分支限界法)基本思想：为了加速搜索的进程，应采用有效地方式选择活结点进行扩展。

按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。

算法设计中的分支限界算法随着人类社会的发展，计算机科学也经历了飞速的发展，计算机算法的研究成为了计算机领域中的一个重要领域。

无论在理论上还是在实践中，算法都有着广泛的应用，例如数据分析、图像处理、搜索引擎等各个领域。

而在算法的发展中，分支限界算法是一种比较重要的算法之一，具体来讲，它是一种基于搜索的算法，可以应用于优化问题和决策问题等场景。

下面，就请跟随笔者的步伐，一起来了解一下分支限界算法的相关知识吧。

一、分支限界算法的基本原理分支限界算法的核心思想是利用深度优先搜索（DFS）的方式，不断地拓展搜索空间，并根据当前情况的限界条件，选择合适的分支进行搜索。

具体来讲，分支限界算法会优先进行深度优先搜索，并记下每个节点的评价函数值，当搜索到某个节点时，对应的评价函数值超出了限界条件，那么该节点即被剪枝掉。

对于一般有解优化问题（如旅行商问题等），分支限界算法的搜索空间应该被定义成“状态空间树”，每个状态代表一个可行解，并用“根节点”表示起始状态，“叶子节点”表示可行解，每个节点的子节点就是较小的状态空间。

通过这种方式，分支限界算法可以有序地遍历每个状态，从而找到评价函数最小的可行解。

二、分支限界算法的优缺点1. 优点：（1）分支限界算法可以解决许多实际中的优化问题，例如旅行商问题、背包问题等，这种算法应用广泛。

（2）分支限界算法使用深度优先搜索，因此可以在解空间中找到最优解。

（3）分支限界算法具有较好的可扩展性，在搜索结束之后，可以通过修改评价函数值，对下一次搜索进行优化。

2. 缺点：（1）由于分支限界算法使用深度优先搜索，在面对大规模的状态空间时，算法时间是指数级的增长，这会导致算法效率低下。

（2）由于分支限界算法利用评价函数值来进行分枝剪枝，对评价函数的选择有很大的影响，评价函数的设计需要非常经验丰富的算法设计师。

三、分支限界算法的应用场景1. 组合优化问题，例如旅行商问题、背包问题等。

2. 决策问题，例如产线安排、任务调度等。

问题描述给定无向图G=(V, E)，其中V是非空集合，称为顶点集；E 是V中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“( )”表示。

如果U∈V，且对任意两个顶点u，v∈U有(u, v)∈E，则称U是G的完全子图(完全图G就是指图G的每个顶点之间都有连边)。

G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。

G的最大团是指G中所含顶点数最多的团。

如果U∈V且对任意u，v∈U有(u, v)不属于E，则称U是G的空子图。

G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。

G的最大独立集是G中所含顶点数最多的独立集。

对于任一无向图G=(V, E)，其补图G'=(V', E')定义为：V'=V，且(u, v)∈E'当且仅当(u, v)∈E。

如果U是G的完全子图，则它也是G'的空子图，反之亦然。

因此，G的团与G'的独立集之间存在一一对应的关系。

特殊地，U是G的最大团当且仅当U是G'的最大独立集。

例：如图所示，给定无向图G={V, E}，其中V={1,2,3,4,5}，E={(1,2), (1,4), (1,5),(2,3), (2,5), (3,5), (4,5)}。

根据最大团(MCP)定义，子集{1,2}是图G的一个大小为2的完全子图，但不是一个团，因为它包含于G的更大的完全子图{1,2,5}之中。

{1,2,5}是G的一个最大团。

{1,4,5}和{2,3,5}也是G的最大团。

右侧图是无向图G的补图G'。

根据最大独立集定义，{2,4}是G的一个空子图，同时也是G的一个最大独立集。

虽然{1,2}也是G'的空子图，但它不是G'的独立集，因为它包含在G'的空子图{1,2,5}中。

{1,2,5}是G'的最大独立集。

{1,4,5}和{2,3,5}也是G'的最大独立集。

基本思想：分枝定界法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。

分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。

该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。

在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。

这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。

这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。

因此这种算法一般可以求得最优解。

将问题分枝为子问题并对这些子问题定界的步骤称为分枝定界法。

分枝节点的选择：对搜索树上的某些点必须作出分枝决策，即凡是界限小于迄今为止所有可行解最小下界的任何子集（节点），都有可能作为分枝的选择对象（对求最小值问题而言）。

怎样选择搜索树上的节点作为下次分枝的节点呢？有两个原则：1）从最小下界分枝（优先队列式分枝限界法）：每次算完界限后，把搜索树上当前所有叶节点的界限进行比较。

找出限界最小的节点，此结点即为下次分枝的结点。

·优点：检查子问题较少，能较快地求得最佳解；·缺点：要存储很多叶节点的界限及对应的耗费矩阵，花费很多内存空间。

2）从最新产生的最小下界分枝（队列式（FIFO）分枝限界法）：从最新产生的各子集中按顺序选择各结点进行分枝，对于下届比上届还大的节点不进行分枝。

优点：节省了空间；缺点：需要较多的分枝运算，耗费的时间较多。

这两个原则更进一步说明了，在算法设计中的时空转换概念。

分枝定界法已经成功地应用于求解整数规划问题、生产进度表问题、货郎担问题、选址问题、背包问题以及可行解的数目为有限的许多其它问题。

对于不同的问题，分枝与界限的步骤和内容可能不同，但基本原理是一样的。

分枝界限法是组合优化问题的有效求解方法，其步骤如下所述：步骤一：如果问题的目标为最小化，则设定目前最优解的值Z=∞步骤二：根据分枝法则（Branching rule），从尚未被洞悉（Fathomed）节点（局部解）中选择一个节点，并在此节点的下一阶层中分为几个新的节点。

# include <iostream># include <queue># include <conio.h>using namespace std;typedef struct{int v; //无向图G的顶点int e; //无向图G的边int a[50][50]; //定义图G的邻接矩阵int bestx[50]; //最优解}MCP;void Creat(MCP &G){int i,j;cout<<"请输入定点数："<<endl;cin>>G.v;cout<<"请输入无向图矩阵："<<endl;for( i=1;i<=G.v;i++)for(int j=1;j<=G.v;j++)cin>>G.a[i][j];for(i=1;i<=G.v;i++) //初始化{G.bestx[i]=0;}}struct BBNode{BBNode *parent; //指向父结点的指针bool LChild; //左儿子结点标志};struct CliqueNode //定义优先队列类型为CliqueNode{int cn; //当前团的顶点数int un; //当前团最大顶点数的上界int level; //结点在子集空间树种所处的层次BBNode *p; //指向活结点在子集树中相应结点的指针bool operator<(const CliqueNode& b) const //<号重载建立大根堆{if(b.un>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<CliqueNode> Q; //定义优先队列QE->LChild=false; //初始化E->parent=NULL;while(i!=G.v+1)//非叶结点{//检查顶点i与当前团中其它顶点之间是否有边相连OK=1;BBNode *B=E; //把当前点的数据给B，B为中间变量for(j=i-1;j>0;B=B->parent,j--)if(B->LChild && G.a[i][j]==0) //如果不满足就停止{OK=0;break;}if(OK) //满足条件，即左儿子结点为可行结点{CliqueNode *D=new(CliqueNode); //定义一个节点DD->p=new(BBNode);if(cn+1>bestn) 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-i>bestn ) //不满足条件但是还是可能有最优解{CliqueNode *D=new(CliqueNode); //定义一个节点DD->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=; //记录当前团的顶点数i=N.level; //所在的层次}for(j=G.v;j>0;j--) //保存最优解{G.bestx[j]=E->LChild;E=E->parent;bestn=cn;}}void main(){MCP G;Creat(G);BBMaxClique(G);cout<<"最大团方案为:( ";for(int i=G.v;i>0;i--)if(G.bestx[i]==1){cout<<i<<" ";}cout<<")"<<endl;getch();}。

问题描述给定无向图G=(V，E),其中V是非空集合，称为顶点集;E是V中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“( ）”表示.如果U∈V，且对任意两个顶点u，v∈U有(u，v)∈E，则称U是G的完全子图(完全图G就是指图G的每个顶点之间都有连边).G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。

G 的最大团是指G中所含顶点数最多的团.如果U∈V且对任意u，v∈U有(u，v）不属于E，则称U是G的空子图。

G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。

G的最大独立集是G中所含顶点数最多的独立集。

对于任一无向图G=(V, E)，其补图G’=(V’，E’)定义为：V'=V，且(u, v)∈E'当且仅当（u, v）∈E。

如果U是G的完全子图，则它也是G'的空子图，反之亦然.因此，G的团与G’的独立集之间存在一一对应的关系.特殊地，U是G的最大团当且仅当U是G’的最大独立集.例：如图所示，给定无向图G=｛V，E},其中V={1，2，3,4，5}，E=｛（1，2), (1,4）, （1，5)，(2，3), (2,5），(3，5），（4，5)}。

根据最大团（MCP)定义，子集{1,2｝是图G的一个大小为2的完全子图，但不是一个团，因为它包含于G的更大的完全子图{1,2，5｝之中。

｛1,2,5}是G的一个最大团。

｛1，4,5}和{2，3,5｝也是G的最大团。

右侧图是无向图G的补图G’.根据最大独立集定义，{2,4}是G的一个空子图，同时也是G的一个最大独立集.虽然｛1，2｝也是G’的空子图，但它不是G’的独立集,因为它包含在G’的空子图｛1,2,5}中.｛1，2,5｝是G'的最大独立集。

{1，4,5｝和{2，3,5｝也是G'的最大独立集。

算法设计最大团问题的解空间树也是一棵子集树。

子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0. 算法在扩展内部结点时，首先考察其左儿子结点。