最大堆分支限界法解最大团问题.cpp

算法分析中

/*
最大团问题描述：
G的完全子图U是G的一个团当且仅当U不包含在G的更大的完全子图中
G的最大团是指G中所含顶点数最多的团
G的空子图U是G的一个独立集当且仅当U不包含在G的更大的空子图中
G的最大独立集是G中所含顶点数最多的独立集

最大团和最大独立子集问题都可以用回溯法在O(n2^n)时间内解决
设当前扩展结点Z位于解空间树的第i层。
在进入左子树前，必须确认从顶点i到已选入的顶点集中每一个顶点
都有边相连。在进入右子树前，必须确认还有足够多的可选择顶点使得算法
有可能在右子树中找到更大的团
*/
/*
利用到最大堆，因为每个结点的结点上限个数
就是优先级。且每个结点属性都相同，所以不需要进行预处理，来对各个结点进行排序，以达到
搜索上的优化，像0-1背包问题，因为每个包的属性都不相同，所以通过一定的预处理可以达到比较好的
搜索效果。而这里是不必要进行预备处理的，因为各个结点只有名称不同，而且求的只是总个数
*/
#include<iostream>
using namespace std;

template<class Type>
class MaxHeap
{
	public:
		Type *H;
		int Capacity;
		int Size;
	public:
		MaxHeap(int n)
		{
			H = NULL;
			H = new Type[n+1];
			Capacity = n;
			Size = 0;
		};
		MaxHeap( MaxHeap& a )
		{
			//要排除自赋值的情况
			if ( this.H != a.H )
			{
				this.H = a.H;
				this.Size = a.Size;
				this.Capacity = a.Capacity;
				for( int i = 0; i < Size; ++i )
				{
					this.H[i] = a.H[size];
				}
			}
		};

		/*
		基本的堆插入操作
		为了将node插入到堆中
		首先在下一个空闲位置++Size处，创建一个空穴，否则该堆将不是完全树
		如果x可以放在该穴中而不破坏堆的序，那么插入完成
		否则我们把空穴的父亲结点上的元素移动到该穴中，这样空穴就朝着根的方向上行一步
		继续该过程直到x能被放入空穴为止
		*/
		void Insert( Type& node )
		{
			//插入元素的时候按照从大到顺序
			for( int i = ++Size; H[ i / 2 ] < node && i != 0; i /= 2 )
			{
				//cout<<"小于"<<endl;
				H[i] = H[ i / 2 ];
			}
			//一定要注意从下标一开始的时候，添加如何进行比较才行
			H[i] = node;
			//cout<<"insert i = "<<i<<endl;
			//cout<<"H[1].print():"<<endl;
			//H[1].print();
			
			//cout<<"Insert Size = "<<Size<<endl;
			for( int k = 1; k <= Size; ++k )
			{
				//cout<<"H["<<k<<"]: "<<endl;
				//H[k].print();
			}
			
		};

		/*
		当删除一个最小元时
		在根结点处产生一个空穴。
		由于现在堆少了一个元素，因此堆中最后一个元素必须移动到该堆的某个地方
		如果x可以放到空穴中，那么DeleteMin完成
		否则应该将两个儿子中较小者移入空穴
		这样空穴就向下推了一层。重复该步骤直到x可以被放入空穴中
		*/
		void DeleteMax( Type& node )
		{
			int i,Child;
			Type MinElement,LastElement;
			node = H[1];
			/*
			cout<<"Size = "<<Size<<endl;
			for( int k = 1; k < Size; ++k )
			{
				cout<<"H["<<k<<"]: "<<endl;
				H[k].print();
			}
			*/
			
			//cout<<"node: "<<endl;
			//node.print();
			LastElement = H[Size--];

			for( i = 1; i * 2 <= Size; i = Child )
			{
				Child = i * 2;
				if ( ( Child != Size && H[ Child + 1 ] > H[ Child ] ) )
				{
					Child++;
				}

				if ( LastElement < H[ Child ] )
					//找到孩子结点中最大的一个覆盖孩子结点
				{
					H[ i ] = H[ Child ];      
				}
				else
				{
					break;
				}
			}
			H[i] = LastElement;
			//node = MinElement;

		};
};

class bbnode
{
	friend class Clique;
public:
	bbnode()
	{
		parent = 0;
		LChild = 0;
	}
private:
	bbnode *parent;
	//指向父结点的指针
	bool LChild;
	//左儿子结点标志
};

class CliqueNode
{
	friend class Clique;
public:
	CliqueNode()
	{
		ptr = 0;
		ptr = new bbnode();
		cn = 0;
		un = 0;
		level = 0;
	}
	operator int() const
	{
		return un;
	}
	bool operator>( CliqueNode& a ) const
	{
		return un > a.un;
	}
private:
	int cn;
	//当前团的顶点数
	int un;
	//当前团的最大顶点数的上界
	int level;
	//结点在子集空间树中所处的层次
	bbnode* ptr;
	//指向活结点在子集树中相应结点的指针
};

class Clique
{
	friend void main(void);
public:
	int BBMaxClique( int [] );
private:
	void AddLiveNode( MaxHeap< CliqueNode > &H,
					  int cn,
					  int un,
					  int level,
					  bbnode *E,
					  bool ch );
	int **a;
	//图G的邻接矩阵
	int n;
	//图G的顶点数
};

/*
算法中函数AddLiveNode的功能是将当前构造出的活结点
加入到子集空间树中并插入活结点优先队列中
*/
void Clique::AddLiveNode( MaxHeap< CliqueNode > &H,
						  int cn,
						  int un,
						  int level,
						  bbnode *E,
						  bool ch )
{
	//将活结点加入到子集空间树中并插入到最大堆中
	bbnode *b = new bbnode;
	b->parent = E;
	b->LChild = ch;
	CliqueNode N;
	N.cn = cn;
	N.ptr = b;
	N.un = un;
	N.level = level;
	H.Insert( N );
}

/*
子集树的根结点是初始扩展结点
对于这个特殊的扩展结点，其cn的值为0
变量i用于表示当前扩展结点在解空间树中所处的
层次。因此，初始时扩展结点所相应的i值为1
当前最大团的顶点数存储于变量bestn中
在while循环中，我们不断从活结点优先队列中抽取当前
扩展结点并实施对该结点的扩展。while循环的终止条件是遇到子集树中的
一个叶结点（既n+1层结点）成为当前扩展结点。
对于子集树中的一个叶结点，我们有un = cn。
此时活结点优先队列中剩余的结点的un值均不超过当前扩展结点的un值
从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解
*/

/*
由于每一个图都有最大团
因此在从最大堆中抽取极大元素时不必测试堆是否为空是为什么
算法的while循环仅当遇到一个叶结点时退出
*/

int Clique::BBMaxClique( int bestx[] )
{
	//解最大团问题的优先队列式分支限界法
	//定义最大堆的容量为1000
	MaxHeap< CliqueNode > H(1000);
	bbnode *E = 0;
	int i = 1;
	int cn = 0;
	int bestn = 0;
	//搜索子集空间树
	while( i != n + 1 )
	{
		//非叶结点
		//检查顶点i与当前团中其他顶点之间是否有边相连
		bool OK = true;
		bbnode *B = E;
		for( int j = i - 1; j > 0; B = B->parent,j-- )
		{
			if ( B->LChild && a[i][j] == 0 )
			{
				OK = false;
				break;
			}
		}
		if ( OK )
		{
			//左儿子结点为可行结点
			if ( cn + 1 > bestn )
			{
				bestn = cn + 1;
			}
			AddLiveNode( H, cn + 1, cn + (n - i + 1), i + 1, E, true );
			//n-i+1是剩余的所有顶点数，所以当前团里的顶点数加上剩余的总的顶点数
			//
		}
		if ( cn + n - i >= bestn )
		{
			//右子树可能含有最优解
			AddLiveNode( H, cn, cn + n - i, i + 1, E, false );
		}
		//取下一个扩展结点
		CliqueNode N;
		H.DeleteMax( N );
		//堆非空
		E = N.ptr;
		cn = N.cn;
		i = N.level;
	}
	//构造当前最优解
	for ( int j = n; j > 0; --j )
	{
		bestx[j] = E->LChild;
		E = E->parent;
	}
	return bestn;
}

void main()
{
	Clique t;
	int V[6][6] =
	{
		{0,2,0,0,0,0},
		{0,1,1,0,1,1},
		{0,1,1,1,0,1},
		{0,0,1,1,0,1},
		{0,1,0,0,1,1},
		{0,1,1,1,1,1}
	};
	//cout<<*(V+1)<<endl;
	/*
	V指向第0行的首地址
	*V第0行第0列的地址
	**V第0行第0列的元素
	*/
	//cout<<*V<<endl;
	int **a = new int*[6];
	for( int j = 0; j < 6; ++j )
	{
		a[j] = new int[6];
	}
	for( j = 0; j < 6; ++j )
	{
		for( int k = 0; k < 6; ++k )
			a[j][k] = V[j][k];
	}
	//int **a = V;
	//常量指针，不能赋值给变量

	int b[6] = {0,0,0,0,0,0};
	int *c = b;
	int n = 5;
	t.a = a;
	t.n = 5;
	t.BBMaxClique(b);
	for( int i = 0; i <= 5; ++i )
	{
		if ( b[i] == 1 )
		{
			cout<<i<<endl;
		}
	}
	return;
}