分支界限法 最大团问题

摘要

最大团问题（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的一个团。

下图1.1中，子集{1，2}是G的大小为2的完全子图。这个完全子图不是团，因为它被G的更大的完全子图{1，2，5}包含。{1，2，5}是G的最大团。{1，4，5}和{2，3，5}也是G的最大团。

图1.1无向连通图

2 问题分析

分支限界（Brand and Bound）法类似于回溯法，也是一种在问题的解空间树上搜索问题的解的算法。

分支限界法常以广度优先或最小耗费（最大效益）优先的方式搜索解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。一旦活结点成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，舍弃那些导致不可行解或导致非最优解的儿子结点，将其余儿子结点加入活结点表中。此后，从活结点表中取下一个结点成为当前扩展结点，并重复上述结点扩展过程，直至找到所需的解或活结点表为空时为止。

具体来讲，分支限界法由“分支”策略和“限界”策略两部分组成。“分支”体现在对问题空间是按广度优先搜索；“限界”策略是为了加速搜索速度而采用启发式剪枝的策略。分支搜索法采用广度优先的策略，依次生成E结点所有分支（即所有的子结点）。在生成的结点中，将采用更有效的约束函数（限界函数）控制搜索路径，去除那些不满足约束条件（即不可能导出最优解）的结点，使之能更好地朝着状态空间树上有最优解的分支推进。

根据从活结点表中选择下一个扩展结点的方式的不同，分支限界法主要分为以下两类：

1，队列式（FIFO）分支限界法

队列式分支限界法将活结点表组织成一个队列，并按队列的FIFO原则选取下一个结点成为当前扩展结点。具体流程为：

（1）初始化，根结点是唯一的活结点，根结点入队。

（2）从活结点队中取出根结点后，作为当前E结点。对当前E结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。

（3）重复上述过程：再从活结点表中取出队首结点（队中最先进来的结点）为当前E结点，……；直到找到一个解或活结点队列为空为止。

2，优先队列式分支限界法

优先队列式分支限界法将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。具体流程为：对每一活结点计算一个优先级，并根据这些优先级，从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

3 建立数学模型

最大团问题作为一个整数规划问题有许多等价的描述，整数规划问题描述如下：

设t : (0,1)n →2v ，t (x )={i ∈V : x i =1}，?x ∈{0,1}n ，?S ∈2v ，则x =t -1(S )={x i : i =1,2,…,n }，其中????∈=S i S i x i ,

0,

1，n 为图的顶点数。 ∑=-=n i i x x f 1

)(m in (1)

s.t. n j i x E j i x x }1,0{,),(,1∈'∈?≤+。如果x*是式(1)的

最优解，则集合C =t (x*)是图G 的一个最大团，且|C |=-f (x*)。

由于x i , x j ∈{0,1}，x i +x j ≤1，?(i , j )∈E '当且仅当x i x j =0，有

x I A x x x x x f G T j i E j i j i n i i )(2

)(,),(1-=+-='>'∈=∑∑，其中G A '为图G 的补图G'的邻接矩

阵。

MCP 问题等价于下面的全局二次0/1问题：

Ax x x f T =)(min (2)

s.t. x ∈{0,1}n

其中A =A G'-I 。如果x*是式(2)的最优解，则集合C =t (x*)是图G 的一个最大团，且|C |=-f (x*)。

4 算法设计

用变量cliqueSize表示与该结点相应的团的顶点数；level表示结点在子集空间树中所处的层次；用cliqueSize +n-level+1作为顶点数上界upperSize的值。在此优先队列式分支限界法中，upperSize实际上也是优先队列中元素的优先级。算法总是从活结点优先队列中抽取具有最大upperSize值的元素作为下一个扩

展元素。

子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize 的值为0。算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其他顶点之间是否有边相连。当顶点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。接着继续考察当前扩展结点的右儿子结点。当upperSize>bestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。

算法的while循环的终止条件是遇到子集树中的一个叶结点（即n+1层结点）成为当前扩展结点。

对于子集树中的叶结点，有upperSize＝cliqueSize。此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。

5 算法实现

// MaxClique_BB.cpp : 定义控制台应用程序的入口点。/*

分支限界法求解最大团问题

*/

#include"stdafx.h"

# include

# include

# include

# include

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;

ifstream fin("data.txt");

if(!fin)

{

cout<<"不能打开文件:"<<"data.txt"<

exit(1);

}

fin>>G.v;

for(int i=1;i<=G.v;i++)

for(int j=1;j<=G.v;j++)

fin>>G.a[i][j];

for(i=1;i<=G.v;i++) //初始化

{

G.bestx[i]=0;

}

cout<<"————————————————————————"<

for(i=1;i<=G.v;i++)

{

for(j=1;j<=G.v;j++)

cout<

cout<

}

}

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 && https://www.doczj.com/doc/f114378448.html,>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;j>0;B=B->parent,j--)

if(B->LChild && G.a[i][j]==0) //如果不满足就停止{

OK=0;

break;

}

if(OK) //满足条件，即左儿子结点为可行结点

{

CliqueNode *D=new(CliqueNode); //定义一个节点D D->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); //定义一个节点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=https://www.doczj.com/doc/f114378448.html,; //记录当前团的顶点数

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<

}

cout<<")"<

getch();

}

6 测试分析

图6.1给定无向图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的最大团。

图6.2是无向图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'的最大独立集。

图6.1 无向图图6.2无向图

结论

在这次课程设计中，运用分支界限法解决最大团问题，分支限界法由“分支”策略和“限界”策略两部分组成。“分支”体现在对问题空间是按广度优先搜索；“限界”策略是为了加速搜索速度而采用启发式剪枝的策略。分支搜索法采用广度优先的策略，依次生成E结点所有分支（即所有的子结点）。在生成的结点中，将采用更有效的约束函数（限界函数）控制搜索路径，去除那些不满足约束条件（即不可能导出最优解）的结点，使之能更好地朝着状态空间树上有最优解的分支推进。而用优先队列式分支限界法对每一活结点计算一个优先级，并根据这些优先级，从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。但是单独使用一种启发式算法求解最大团问题，算法性能往往并不是很好，因此，常借鉴算法之间优势互补策略，形成新的混合启发式算法来求解最大团问题。对算法设计与分析的基础知识有了更进一步的了解和学习。在收获的同时，也丰富了自己的知识，同过查阅书籍，网上查资料，使我对原本陌生的知识又有了进一步的了解，通过不断的努力，难关最终被攻破，这是一种成就感，独立思考问题的能力，动手操作的能力都有了很大程度的提高。

参考文献

[1]霍红卫.算法设计与分析[M].西安电子科技大学出版社2005年2月.

[2]王晓东.计算机算法高计与分析[M].电子工业出版社，2000年6月.

[3]邹海明.佘详宣计算机算法基础[M].华中科技大学出版社，1998年7月.

[4] 常友渠.贪心算法的探讨与研究[M].重庆电力高等专科学报,2008.9.

[5] 龚雄兴.堆与贪心算法[M],湖北襄樊学院，2003.

[6] 张洁,朱莉娟.贪心算法与动态规划的比较[M].新乡师范高等专科科学学报,

2005.9.

(完整版)分支限界算法作业分配问题

分支限界法的研究与应用 摘要： 分支限界法与回溯法的不同:首先,回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。其次，回溯法以深度优先的方式搜索解空间树，而分支限界法则一般以广度优先或以最小耗费优先的方式搜索解空间树。再者，回溯法空间效率高；分支限界法往往更“快”。 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 常见的分支限界法有：队列式分支限界法，按照队列先进先出原则选取下一个结点为扩展结点。栈式分支限界法，按照栈后进先出原则选取下一个结点为扩展结点。优先队列式分支限界法，按照规定的结点费用最小原则选取下一个结点为扩展结点（最采用优先队列实现）。 分支搜索法是一种在问题解空间上进行搜索尝试的算法。所谓分支是采用广度优先的策略国,依次搜索E-结点的所有分支,也就是所有的相邻结点。和回溯法一样,在生成的结点中,抛弃那些不满足约束条件的结点,其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点,断续搜索。 关键词： 分支限界法回溯法广度优先分支搜索法

目录 第1章绪论 (3) 1.1 分支限界法的背景知识 (3) 1.2 分支限界法的前景意义 (3) 第2章分支限界法的理论知识.................. 错误!未定义书签。 2.1 问题的解空间树 ............................................... 错误!未定义书签。 2.2 分支限界法的一般性描述 (6) 第3章作业分配问题 (7) 3.1 问题描述 (7) 3.2 问题分析 (7) 3.3 算法设计 (8) 3.4 算法实现 (10) 3.5 测试结果与分析 (12) 第4章结论 (13) 参考文献 (14)

回溯法与分支限界法的分析与比较

回溯法与分支限界法的分析与比较 摘要：通过对回溯法与分支限界法的简要介绍，进一步分析和比较这两种算法在求解问题时的差异，并通过具体的应用来说明两种算法的应用场景及侧重点。 关键词：回溯法分支限界法n后问题布线问题 1、引言 1.1回溯法 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。这种以深度优先方式系统搜索问题解的算法称为回溯法。 1.2分支限界法 分支限界法是以广度优先或以最小耗费优先的方式搜索解空间树，在每一个活结点处，计算一个函数值，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解，这种方法称为分支限界法。 2、回溯法的基本思想 用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少应包含问题的一个解。之后还应将解空间很好的组织起来，使得能用回溯法方便的搜索整个解空间。在组织解空间时常用到两种典型的解空间树，即子集树和排列树。确定了解空间的组织结构后，回溯法从开始结点出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法以这种工作方式递归的在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。 3、分支限界法的基本思想 用分支限界法解问题时，同样也应明确定义问题的解空间。之后还应将解空间很好的组织起来。分支限界法也有两种组织解空间的方法，即队列式分支限界法和优先队列式分支限界法。两者的区别在于：队列式分支限界法按照队列先进先出的原则选取下一个节点为扩展节点，而优先队列式分支限界法按照优先队列

分支限界法实现单源最短路径问题

实验五分支限界法实现单源最短路径 一实验题目：分支限界法实现单源最短路径问题 二实验要求：区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。 三实验内容：解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。 结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。 四实验代码 #include using namespace std; const int size = 100; const int inf = 5000; //两点距离上界 const int n = 6; //图顶点个数加1 int prev[n]; //图的前驱顶点 int dist[] = {0,0,5000,5000,5000,5000}; //最短距离数组 int c[n][n] = {{0,0,0,0,0,0},{0,0,2,3,5000,5000}, //图的邻接矩阵 {0,5000,0,1,2,5000},{0,5000,5000,0,9,2}, {0,5000,5000,5000,0,2},{0,5000,5000,5000,5000,0}}; const int n = 5; //图顶点个数加1 int prev[n]; //图的前驱顶点 int dist[] = {0,0,5000,5000,5000}; int c[][n] = {{0,0,0,0,0},{0,0,2,3,5000},{0,5000,0,1,2},{0,5000,5000,0,9}, {0,5000,5000,5000,0}};

分支界限法.

武汉理工大学 算法设计与分析论文题目：分支限界法应用研究

目录 摘要 (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.绪论 为了解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、分支限界法等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不像是技术 ,但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法 ,你可以使用这些方法来设计算法 ,并观察这些算法是如何工作的。一般情况下,为了获得较好的性能,必须对算法进行细致的调整。但是在某些情况下,算法经过调整之后性能仍无法达到要求,这时就必须寻求另外的方法来求解该问题。分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

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

问题描述 给定无向图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。算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其它顶点之间是否有边相连。当顶点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。 接着继续考察当前扩展结点的右儿子结点。当 upperSize>bestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。

实验五、优先队列式分支限界法解装载问题

实验五优先队列式分支限界法解装载问题 09电信实验班I09660118 徐振飞 一、实验题目 实现书本P201所描述的优先队列式分支限界法解装载问题 二、实验目的 （1）掌握并运用分支限界法基本思想 （2）运用优先队列式分支限界法实现装载问题 （3）比较队列式分支限界法和优先队列式分支限界法的优缺点三、实验内容和原理 （1）实验内容 有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船， 其中集装箱i的重量为Wi，且∑ = + ≤ n i i c c w 1 2 1 ，要求确定是否有一个合 理的装载方案可将这n个集装箱装上这2艘轮船。如果有，请给出方案。 （2）实验原理 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中活结点x的优先级为x.uweight。以结点x为根的子树中所有结点相应的路径的载重量不超过x.uweight。子集树中叶结点所相应的载重量与其优先级相同。因此在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结

点，则可以断言该叶结点所相应的解即为最优解，此时终止算法。 上述策略可以用两种不同方式来实现。第一种方式在结点优先队列的每一个活结点中保存从解空间树的根结点到该活结点的路径，在算法确定了达到最优值的叶结点时，就在该叶结点处同时得到相应的最优解。第二种方式在算法的搜索进程中保存当前已构造出的部分解空间树，在算法确定了达到最优值的叶结点时，就可以在解空间树中从该叶结点开始向根结点回溯，构造出相应的最优解。在下面的算法中，采用第二种方式。 四、源程序 import https://www.doczj.com/doc/f114378448.html,parator; import java.util.Iterator; import java.util.PriorityQueue; import java.util.Scanner; public class test5 { public void addLiveNode(PriorityQueue H,bbnode E,int wt,boolean ch,int lev){ bbnode b = new bbnode(E,ch); HeapNode N = new HeapNode(b, wt, lev); H.add(N); } public int maxLoading(int w[],int c,int n,boolean bestx[]){ PriorityQueue H = new PriorityQueue(1000,new comp()); /*生成最大堆*/ int[] r = new int[n+1]; r[n] = 0; for(int j=n-1;j>0;j--){ r[j] = r[j+1] + w[j+1]; } int i = 1; bbnode E = new bbnode(null,false); int Ew = 0; while(i!=n+1){ if(Ew+w[i]<=c){ addLiveNode(H, E, Ew+w[i]+r[i], true, i+1);

分支限界法实验(最优装载问题)

算法分析与设计实验报告第八次附加实验

for(int i=1;i

完整代码（分支限界法） //分支限界法求最优装载 #include #include #include #include using namespace std; class QNode { friend void Enqueue(queue&,int,int,int,int,QNode *,QNode *&,int *,bool); friend void Maxloading(int *,int,int,int *); private: QNode *parent; //指向父节点的指针 bool LChild; //左儿子标志，用来表明自己是否为父节点的左儿子 int weight; //节点所相应的载重量 }; void Enqueue(queue&Q,int wt,int i,int n,int bestw,QNode *E,QNode *&bestE,int bestx[],bool ch) { //将活节点加入到队列中 if(i==n) //到达叶子节点 { if(wt==bestw) //确保当前解为最优解 { bestE=E; bestx[n]=ch; } return; } //当不为叶子节点时，加入到队列中，并更新载重、父节点等信息 QNode *b; b=new QNode; b->weight=wt; b->parent=E; b->LChild=ch; Q.push(b); } void Maxloading(int w[],int c,int n,int bestx[]) //其中w[]为重量数组| { // c为船的总载重量,n为节点数 //初始化 queue Q; //活节点队列

0-1背包问题(分支限界法)

分支限界法——01 背包问题 12 软工028 胡梦颖 一、问题描述 0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时,对每种物品i 只有2种选择,即装入背包或不装入背包。不能将物品i 装入背包多次,也不能只装入部分的物品i。 二、问题分析 分支限界法类似于回溯法,也是在问题的解空间上搜索问题解的算法。一般情况下,分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解。由于求解目标不同,导致分支限界法与回溯法对解空间的搜索方式也不相同。回溯法以深度优先的方式搜索解空间,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间。分支限界法的搜索策略是,在扩展结点处,先生成其所有的儿子结点（分支）,然后再从当前的 活结点表中选择下一扩展结点。为了有效地选择下一扩展结点,加速搜索的进程,在每一个活结点处,计算一个函数值（限界）,并根据函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间上有最优解的分支推进,以便尽快地找出一个最优解。这种方式称为分支限界法。人们已经用分支限界法解决了大量离散最优化的问题。 三．源代码 #include #include #define MaxSize 100 //结点数的最大值 typedef struct QNode

算法设计与分析---回溯+分支限界法实验报告

《算法设计与分析》作业 作业四+五回溯法+分支限界法 1. 二元最大连通块搜索 因为下了场大雨，青蛙王子高兴坏了，它有机会重新划定自己的王国范围。在下图中，空白区域表示积水的地方，青蛙王子需要找到一块最大的连续积水区域（上下或左右相连）作为自己的新领地。 2. 三元最大连通块搜索 小明在玩一种消除游戏。游戏中有一个长方形的区域，被RGB(红绿蓝)三种颜色的小球充满。要求每次找出当前最大连通区域（上下左右相邻同种颜色即可算作连通），进行消除。

####.### ###.#### ##.##### the ans is 7 12 8 ..#..... .##....# .#....#. .###.#.. ....#... ..##.#.. .#....#. .##..#.# ###..#.. ....#... ...#.... ..#..... the ans is 18 1.3 程序运行情况

1.4 程序源码（含注释） #include"bits/stdc++.h" using namespace std; #define inf 999 //代码下标从0始，输入时.为可走，#为不可走 int n,m;//行、列 int ans,now;//最大连通数，当前搜索时连通数 char e[inf][inf];//地图 int book[inf][inf];//标记地图 int pos[4][2]={-1,0,1,0,0,1,0,-1};//方位，上下右左 void read()//输入数据 { printf("input the row and the column of the map:"); scanf("%d%d",&n,&m); printf("now input the map:\n"); for(int i=0;i

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

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

问题描述 给定无向图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。算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点i 加入到当前团中，并检查该顶点与当前团中其它顶点之间是否有边相连。当顶点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。 接着继续考察当前扩展结点的右儿子结点。当upperSize>bestn 时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。

常用算法之：分支限界法

常用算法之：分支限界法 一、基本描述 类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。 （1）分支搜索算法 所谓“分支”就是采用广度优先的策略，依次搜索E-结点的所有分支，也就是所有相邻结点，抛弃不满足约束条件的结点，其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点，继续搜索。 选择下一个E-结点的方式不同，则会有几种不同的分支搜索方式。 1）FIFO搜索 2）LIFO搜索 3）优先队列式搜索 （2）分支限界搜索算法 二、分支限界法的一般过程 由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。 分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，

以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。 三、回溯法和分支限界法的一些区别 有一些问题其实无论用回溯法还是分支限界法都可以得到很好的解决，但是另外一些则不然。也许我们需要具体一些的分析——到底何时使用分支限界而何时使用回溯呢？ 回溯法和分支限界法的一些区别： 方法对解空间树的搜索方式存储结点的常用数据结构结点存储特性常用应用 回溯法深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解 分支限界法广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解

算法之分支限界法实现

实验5 分支限界法实现 一、实验目标： 1.熟悉分支限界法应用场景及实现的基本方法步骤； 2.学会分支限界法的实现方法和分析方法： 二、实验内容 1. n后问题： 编程计算当n=1到8时解的个数，分别利用回溯法和分支限界法实现，比较并分析你的算法效率。 回溯法： 代码： #include #include using namespace std; //法一：迭代回溯 class Queen { friend int nQueen(int); private: bool Place(int k); void Backtrack(int t); int n;//皇后个数 int *x;//当前解 int sum;//当前已找到的可行方案数 }; bool Queen::Place(int k)

{ for (int j = 1; j < k; j++) { if ((abs(k - j) == abs(x[j] - x[k])) || (x[j] == x[k])) return false; } return true; } void Queen::Backtrack(int t) { if (t > n) sum++; else for (int i = 1; i <= n; i++) { x[t] = i; if (Place(t)) Backtrack(t + 1); } } int nQueen(int n) { Queen X; //初始化X X.n = n; X.sum = 0; int *p = new int[n + 1]; for (int i = 0; i <= n; i++) p[i] = 0; X.x = p; X.Backtrack(1); delete[]p; return X.sum; } int main() { cout << "共有" << nQueen(8) << "种" << endl; system("pause"); return 0; }

动态规划法-回溯法-分支限界法求解TSP问题实验报告

TSP问题算法实验报告 目录 总述 (2) 动态规划法 (2) 算法问题分析 (2) 算法设计 (2) 实现代码 (2) 输入输出截图 (5) OJ提交截图 (5) 算法优化分析 (5) 回溯法 (5) 算法问题分析 (5) 算法设计 (6) 实现代码 (6) 输入输出截图 (8) OJ提交截图 (8) 算法优化分析 (9) 分支限界法 (9) 算法问题分析 (9) 算法设计 (9) 实现代码 (9) 输入输出截图 (14) OJ提交截图 (14) 算法优化分析 (14) 总结 (15)

总述 TSP问题又称为旅行商问题，是指一个旅行商要历经所有城市一次最后又回到原来的城市，求最短路程或最小花费，解决TSP可以用好多算法，比如蛮力法，动态规划法…具体的时间复杂的也各有差异，本次实验报告包含动态规划法，回溯法以及分支限界法。 动态规划法 算法问题分析 假设n个顶点分别用0~n-1的数字编号，顶点之间的代价存放在数组mp[n][n]中，下面考虑从顶点0出发求解TSP问题的填表形式。首先，按个数为1、2、…、n-1的顺序生成1~n-1个元素的子集存放在数组x[2^n-1]中，例如当n=4时，x[1]={1},x[2]={2},x[3]={3},x[4]={1,2},x[5]={1,3},x[6]={2,3},x[7]={1,2,3}。设数组dp[n][2^n-1]存放迭代结果，其中dp[i][j]表示从顶点i经过子集x[j]中的顶点一次且一次，最后回到出发点0的最短路径长度，动态规划法求解TSP问题的算法如下。 算法设计 输入：图的代价矩阵mp[n][n] 输出：从顶点0出发经过所有顶点一次且仅一次再回到顶点0的最短路径长度 1.初始化第0列（动态规划的边界问题） for(i=1;i #include

实验-4-用分支限界法实现0-1背包问题

实验四用分支限界法实现0-1背包问题 一．实验目的 1.熟悉分支限界法的基本原理。 2.通过本次实验加深对分支限界法的理解。 二．实验内容及要求 内容：.给定n种物品和一个背包。物品i的重量是w，其价值为v，背包容量为c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大? 要求：使用优先队列式分支限界法算法编程，求解0-1背包问题 三．程序列表 #include #include using namespace std; #define N 100 class HeapNode//定义HeapNode结点类 { public: double upper, price, weight; //upper为结点的价值上界，price是结点所对应的价值，weight 为结点所相应的重量 int level, x[N]; //活节点在子集树中所处的层序号 }; double MaxBound(int i); double Knap(); void AddLiveNode(double up, double cp, double cw, bool ch, int level);//up是价值上界，cp是相应的价值，cw是该结点所相应的重量，ch是ture or false stack High; //最大队High double w[N], p[N]; //把物品重量和价值定义为双精度浮点数 double cw, cp, c; //cw为当前重量，cp为当前价值，定义背包容量为c int n; //货物数量为 int main() { cout <<"请输入背包容量："<< endl; cin >> c; cout <<"请输入物品的个数："<< endl; cin >> n; cout <<"请按顺序分别输入物品的重量："<< endl; int i; for (i = 1; i <= n; i++) cin >> w[i]; //输入物品的重量