bbtsp.cpp

计算机算法设计与分析(王晓东)教材上相关源程序代码。 包括分治法(4)

#include "iostream.h"
#include "exception"
#include "MinHeap.h"

class Traveling{
	friend void main(void);
	public:
		int BBTSP(int v[]);
	private:
		int n;//图G的顶点数
		int **a,//图G的邻接矩阵
			NoEdge,//图G的无边标志
			cc,//当前费用
			bestc;//当前最小费用
};

class MinHeapNode{
	friend class Traveling;
	public:
		operator int() const{return lcost;}
	private:
		int lcost,//子树费用的下届
			cc,//当前费用
			rcost;//x[s:n-1]中顶点最小出边费用和
		int s,//根节点到当前节点的路径为x[0:s]
			*x;//需要进一步搜索的顶点是x[s+1:n-1]
};

int Traveling::BBTSP(int v[])
{//解旅行商售货员问题的优先队列式分支限界法
//定义最小堆的容量为1000
	MinHeap<MinHeapNode>H(1000);
	int *MinOut = new int[n+1];
	//计算MinOut[i]=顶点i的最小出边费用
	int MinSum=0;//最小出边费用和
	for(int i=1;i<=n;i++)
	{
		int Min=NoEdge;
		for(int j=1;j<=n;j++)
		{
			if(a[i][j]!=NoEdge && (a[i][j]<Min||Min==NoEdge))
			{
				Min= a[i][j];
			}
		}
		if(Min==NoEdge) return NoEdge;//无回路
		MinOut[i]=Min;
		MinSum+=Min;
	}

	//初始化
	MinHeapNode E;
	E.x=new int[n];
	for(int j=0;j<n;j++)
	{
		E.x[j]=j+1;
	}
	E.s=0;
	E.cc=0;
	E.rcost=MinSum;
	int bestc=NoEdge;
	//搜索排列空间树
	while(E.s<n-1){//非叶节点
		if(E.s==n-2){//当前扩展结点是叶结点的父结点
			//再加2条边构成回路
			//所构成回路是否优于当前最优解
			if(a[E.x[n-2]][E.x[n-1]]!=NoEdge && a[E.x[n-1]][E.x[0]]!=NoEdge &&
				(E.cc+a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][E.x[0]]<bestc||bestc==NoEdge)){
				//费用更小的回路
				bestc = E.cc+a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][E.x[0]];
				E.cc=bestc;
				E.lcost=bestc;
				E.s++;
				H.Insert(E);
			}
			else
			{
				delete [] E.x;//舍弃扩展结点
			}
		}
		else//产生当前扩展节点的所有儿子结点
		{
			for(int i=E.s+1;i<n;i++){
				if(a[E.x[E.s]][E.x[i]]!=NoEdge){
					//可行儿子结点
					int cc= E.cc+a[E.x[E.s]][E.x[i]];
					int rcost = E.rcost-MinOut[E.x[E.s]];
					int b = cc+ rcost;//下界
					if(b<bestc || bestc==NoEdge){
						//子树可能含有最优解
						//节点插入最小堆
						MinHeapNode N;
						N.x=new int[n];
						for(int j=0;j<n;j++){
							N.x[j]=E.x[j];
						}
						N.x[E.s+1]=E.x[i];
						N.x[i]=E.x[E.s+1];
						N.cc= cc;
						N.s=E.s+1;
						N.lcost=b;
						N.rcost=rcost;
						H.Insert(N);
					}
				}	
			}
			delete [] E.x;//完成结点扩展
		}//end of if

		H.DeleteMin(E);//取下一扩展结点
		//catch(OutOfBounds){break;}//堆已空
	}//end of while

	if(bestc == NoEdge) return NoEdge;//无回路
	//将最优解复制到v[1:n]
	for(int k=0;k<n;k++)
	{
		v[k+1]=E.x[k];
	}	
	
	delete[] E.x;
	bool b =true;
	while(b){//释放最小堆中所有结点
		b=H.DeleteMin(E);
	}

	return bestc;		
}

void main(void)
{	
	Traveling bbtsp;
	bbtsp.n=4;
	
	int a[5]={0,0,0,0,0};
	int b[5]={0,0,30,6,4};
	int c[5]={0,30,0,5,10};
	int d[5]={0,6,5,0,20};
	int e[5]={0,4,10,20,0};
	int *p[5] ={a,b,c,d,e};
/*	for (int i=0;i<5;i++)
	{
		for(int j=0;j<5;j++)
		{
			cout<<b[i][j]<<" ";
		}
		cout<<endl;
	}*/
	bbtsp.a=p;

	for (int i=0;i<5;i++)
	{
		for(int j=0;j<5;j++)
		{
			cout<<bbtsp.a[i][j]<<" ";
		}
		cout<<endl;
	}
	bbtsp.NoEdge=0;
	bbtsp.cc=0;
	bbtsp.bestc=bbtsp.NoEdge;
	int v[5];
	int bestc = bbtsp.BBTSP(v);
	cout<<bestc<<endl;
	cout<<"最优路径为：";
	for(int k=1;k<=bbtsp.n;k++)
		cout<<v[k]<<" ";
	cout<<endl;
}


/******************MinHeap的实现***************************/
template<class T>
MinHeap<T>::MinHeap(int ms):defaultSize(100){
	 maxSize = ms > defaultSize ? ms : defaultSize;
	heap = new T[maxSize];
	currentSize = 0;
}

template<class T>
MinHeap<T>::MinHeap(T a[],int n):defaultSize(100)
{
	//用一个数组来初始化堆
	maxSize = n > defaultSize ? n : defaultSize;
	heap = new T[maxSize];
	currentSize = n;
	for(int i = 0; i < n; i++)
		heap[i] = a[i];
	int curPos = (currentSize - 2) / 2;
	
	while(curPos >= 0){
		FilterDown(curPos,currentSize - 1);
		curPos--;
	}
}


template<class T>
MinHeap<T>::~MinHeap(){
 delete []heap;
}


template<class T>
void MinHeap<T>::FilterDown(const int start,const int endOfHeap){
	//自顶向下进行调整，将start节点放至对应的位置
	int i = start,j = i * 2 + 1;//start的左子树
	T temp = heap[i];
 
	while(j <= endOfHeap){
		if(j < endOfHeap && heap[j] > heap[j+1]) j++;//如果左右子树都存在，找出最小者，用j标记      
		if(temp < heap[j]) break;//找到了相应的位置
		else{
			heap[i] = heap[j];
			i = j;
			j = 2 * i + 1;
			}

	}
	
	heap[i] = temp;
}


template<class T>
void MinHeap<T>::FilterUp(const int start){
	//自底向上进行调整，将start节点放至对应的位置
 int i = start, j = ( i - 1 ) / 2;//父节点的编号
 T temp = heap[i];
 while(i > 0){
   if(temp >= heap[j]) break;//找到了相应的位置
   else{
    heap[i] = heap[j];
    i = j;
    j = (i - 1) / 2;
   }
 }
 heap[i] = temp;
}


template<class T>
bool MinHeap<T>::DeleteMin(T &x){
 if(IsEmpty()){
  cerr<<"Heap empty!"<<endl;
  return false;
 }
 x = heap[0];
 heap[0] = heap[currentSize - 1];
 currentSize--;
 FilterDown(0,currentSize-1);
 return true;
}

template<class T>
bool MinHeap<T>::Insert(const T& x){
 if(IsFull()) {
  cerr<<"Heap Full!"<<endl;
        return false;
 }
 heap[currentSize] = x;
 FilterUp(currentSize);
 currentSize++;
 return true;
}



template<class T>
bool MinHeap<T>::IsEmpty(){
  return currentSize == 0;
}


 
template<class T>
bool MinHeap<T>::IsFull(){
  return currentSize == maxSize;
}



template<class T>
void MinHeap<T>::MakeEmpty(){
 currentSize = 0
}