问题描述

给定一个无向图G=(V, E),设U\subseteq V是G的顶点集。对任意(u, v)∈E,若u∈U，且v∈V-U,就称(u, 1)为关于顶点集U的一条割边。顶点集U的所有割边构成图G的一个割。G的最大割是指G中所含边数最多的割。

对于给定的无向图G,设计一个优先队列式分支限界法，计算G的最大割。

分析

• 解向量：（x1,x2,……xn)是一个01序列，其中xi=1表示点xi在割集，0表示不在割集
• 解空间：完全二叉树，子集树
• 用node类来表示节点，每个节点含有的元素：当前层 割边数量 剩余边的数量 解向量
• 优先级：每个节点当前割边数量
• 如果还没有到叶节点：
  ①左子节点直接加入优先队列。修改解向量，该左子节点加入后修改割边数量和剩余边数量。
  ②右子节点需要判断是否需要剪枝：当前割边数+剩余边数>当前最优解时，加入队列。修改解向量，该右子节点加入后修改剩余边数量。
• 到达叶节点，即求得最优值

代码

#include <bits/stdc++.h>
#include <fstream>
#include <iostream> 
using namespace std;const int MAX = 1000;
int G[MAX][MAX];//存储边信息 
int bestx[MAX];//最优值的割集 
int w[MAX];//顶点的权
int n, e; //顶点数，边数 
ifstream in("input.txt");
ofstream out("output.txt"); //结点类 
class Node
{
public:int dep;  //当前层int cut;  //割边数量int e;    //剩余边的数量int *x;   //解向量Node(int d, int c, int ee){x = new int[n+1];dep = d;cut = c;e = ee;}//割边数大的先出队列bool operator<(const Node &node) const{return cut < node.cut;}
};//存储待解决的结点的优先队列 
priority_queue<Node> q;//添加结点
void addNode(Node enode, bool isLeft)
{Node now(enode.dep+1,enode.cut,enode.e);copy(enode.x, enode.x+n+1, now.x);//是左结点 if(isLeft){now.x[now.dep] = 1;//因为是左节点 标记是割集元素 for(int j=1;j<=n;j++)//统计割边的增量 if(G[now.dep][j])if(now.x[j] == 0) //如果当前顶点在割集中，但边的另一个顶点不在割集{now.cut++;  //割边的数量增加now.e--;    //剩余边的数量减少}elsenow.cut--;//否则割边数量减少 }else//右节点 { now.x[now.dep] = 0;//标记不是割集元素 now.e--;//剩余边的数量减少}q.push(now);//加入优先队列 
}int search()
{//初始化 ：层0 割边0 剩余边e Node enode(0, 0, e);for(int j=1; j<=n; j++)enode.x[j] = 0;//解向量 int best = 0;//分支限界求解 while(true){if(enode.dep>n)//到达叶子节点，如果比当前最优解更优，更新 {if(enode.cut>best){best = enode.cut;copy(enode.x, enode.x+n+1, bestx);break;}}else//没有到达叶子节点 {addNode(enode,true);//加入左子结点 if(enode.cut+enode.e>best)//满足约束条件，加入右子结点 addNode(enode,false);}if(q.empty())break;else//取出队首元素 {enode = q.top();q.pop(); }}return best;
}int main()
{int a, b, i;in>>n>>e;    memset(G, 0, sizeof(G));for(i=1; i<=e; i++){in >> a >> b;G[a][b] = G[b][a] = 1;}out << search()<<'\n';for(i=1; i<=n; i++){out << bestx[i];if(i!=n) out<<" ";}out<<'\n';   in.close();out.close();return 0;} 

时间复杂度

• 时间复杂度：最坏情况下要遍历整棵树，O（2^n)
• 空间复杂度：最坏情况下要保存最后一层的所有结点，每个结点要记录当前的解，O（n*2^n)