algbb.cpp

*程序AlgBB用于求解甲乙城市之间的最短路径的分支限界问题 * //*输入：距离文件m1.txt

//*************************************************************
//*程序AlgBB用于求解甲乙城市之间的最短路径的分支限界问题	  *
//*输入：距离文件m1.txt，耗费文件m2.txt						  *
//*输出：甲乙城市间的具体最短路径及其总长度和总耗费		      *
//*************************************************************

#include <iostream>
#include <fstream>
using namespace std;

const int MAX=9999;

//类HeapNode：用于构造类的节点
class HeapNode
{
	public:
		HeapNode()
		{
			n=0;
		}
		HeapNode(const HeapNode& );
		HeapNode& operator=(const HeapNode&);
		int length;		//当前路径长度的边界
		int cost;		//所耗养路费的值
		int num;		//城市的编号
		int path[50];	//到该节点所经过的路径
		int n;			//路径中的顶点数（城市数）
};

//构造函数
HeapNode::HeapNode(const HeapNode& a)
{
	int i;
	length=a.length;
	cost=a.cost;
	num=a.num;
	n=a.n;
	for(i=0;i<a.n;i++)
	{
		path[i]=a.path[i];
	}
}

//赋值操作符重载
HeapNode& HeapNode::operator =(const HeapNode& a)
{
	int i;
	length=a.length;
	cost=a.cost;
	num=a.num;
	n=a.n;
	for(i=0;i<a.n;i++)
	{
		path[i]=a.path[i];
	}
	return *this;
}

//类Heap：用于最小堆的构造
class Heap
{
	public:
		Heap(int heapSize);				//构造函数
		void delNode(HeapNode & x);		//从堆中删除最小元素
		void insNode(HeapNode & x);		//向堆中插入元素
		bool isEmpty();					//判断堆是否为空
	private:
		int size;						//堆的最大容量
		int n;							//当前堆的大小
		HeapNode * heap;				//指向堆的指针
		void moveUp(int i);				//用于在堆中从下到上交换元素
		void moveDown(int i);			//用于在堆中从上到下交换元素
};

//构造函数
Heap::Heap(int heapSize)
{
	heap=new HeapNode[heapSize];
	size=heapSize;
	n=0;
}

//判断堆是否为空
bool Heap::isEmpty()
{
	if(n<=0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//用于在堆中从下到上交换元素
void Heap::moveUp(int i)
{
	while(i>0)
	{
		if(heap[i].length < heap[(i-1)/2].length)
		{
			HeapNode a=heap[i];
			heap[i]=heap[(i-1)/2];
			heap[(i-1)/2]=a;
			i=(i-1)/2;
		}
		else 
		{
			return;
		}
	}
	return;
}

//用于在堆中从上到下交换元素
void Heap::moveDown(int i)
{
	while((2*i+1) < n)
	{
		i=2*i+1;
		if(i+1<n)
		{
			if(heap[i].length > heap[i+1].length)
			{
				i=i+1;
			}
		}
		if(heap[(i-1)/2].length > heap[i].length)
		{
			HeapNode a=heap[i];
			heap[i]=heap[(i-1)/2];
			heap[(i-1)/2]=a;
		}
		else
		{
			return;
		}
	}
	return;
}

//从堆中删除最小元素
void Heap::delNode(HeapNode& x)
{
	x=heap[0];
	heap[0]=heap[n-1];
	if(--n<=0)
	{
		return;
	}
	moveDown(0);
}

//向堆中插入元素
void Heap::insNode(HeapNode& x)
{
	heap[n++]=x;
	moveUp(n-1);
	
}

//利用分枝定界法求解最短路径
void AlgBB(int cost[51][51],int length[51][51])
{
	int i,j,tmp,u,n,min,shortestCost,s[51];
	int distance[51];			//用于存放到目的地最短路径长度
	int path[50];				//到目前为止的最短路径
	int pathLength=0;			//目前路径中包含的结点数

	Heap heap(200);				//构造堆
	HeapNode node;
	n=50;
	min=MAX;
	node.num=1;
	node.cost=0;
	node.path[node.n++]=1;

	for(i=1;i<n;i++)
	{
		distance[i]=length[i][50];
		s[i]=false;
	}
	for(i=1;i<n;i++)
	{
		tmp=MAX;
		for(j=1;j<n;j++)
		{
			if(!s[j] && (distance[j]<tmp))
			{
				tmp=distance[j];
				u=j;
			}
		}
		if(tmp<MAX)
		{
			s[u]=true;
			for(j=1;j<n;j++)
			{
				if(!s[j] && (distance[u]+length[j][u]<distance[j]))
				{
					distance[j]=distance[u]+length[j][u];
				}
			}
		}
	}

	node.length=distance[1];

	//遍历解空间树
	for(;;)
	{
		for(i=1;i<=n;i++)
		{
			//判断是否剪枝
			if((length[node.num][i] < MAX) && (node.cost+cost[node.num][i]<=1500) && (node.length-distance[node.num]+length[node.num][i]+distance[i]<=min))
			{
				//是否到达目的地
				if(i==50)
				{
					if(node.length+length[node.num][i]-distance[node.num]<=min)
					{
						for(j=0;j<node.n;j++)
						{
							path[j]=node.path[j];
						}
						path[node.n]=50;
						pathLength=node.n+1;
						min=node.length+length[node.num][i]-distance[node.num];
					}				
					continue;
				}

				//查看是否出现回路
				for(j=0;j<node.n;j++)
				{
					if(node.path[j]==i)
					{
						break;
				
					}
				}
				//将节点其插入最小堆中
				if(node.n==j)
				{
					HeapNode tmp;
					tmp.num=i;
					tmp.length=node.length-distance[node.num]+length[node.num][i]+distance[i];
					tmp.cost=node.cost+cost[node.num][i];
					tmp.n=node.n+1;
					for(j=0;j<node.n;j++)
					{
						tmp.path[j]=node.path[j];
					}
					tmp.path[node.n]=i;
					heap.insNode(tmp);
				}
			}
		}

		//每次从优先队列中取一个最小的结点
		while(true)
		{
			//如果队列为空则输出结果
			if(heap.isEmpty())
			{
				cout<<"算法AlgBB所得结果:"<<endl;
				cout<<"甲乙之间最短路线长度是:"<<min<<endl;
				shortestCost=0;
				for(i=0;i<pathLength-1;i++)
				{
					shortestCost+=cost[path[i]][path[i+1]];
				}
				cout<<"最短路线收取的费用是:"<<shortestCost<<endl;
				cout<<"最短路径是:"<<endl;
				for(i=0;i<pathLength;i++)
				{
					cout<<path[i]<<"	";
				}
				cout<<endl;
				return;
			}
			//队列不为空则取出堆中的最小结点
			heap.delNode(node);
			//判断是否剪枝
			if(node.length>min)
			{
				continue;
			}
			else
			{
				break;
			}
		}
	}
}

int main()
{
	int i,j,n;
	int cost[51][51];						//耗费矩阵
	int length[51][51];						//距离矩阵

	ifstream inFile;			
	//读文件m1.txt到length矩阵中
	inFile.open("m1.txt");					
	n=50;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			inFile>>length[i][j];
		}
	}
	inFile.close();
	//读文件m2.txt到cost矩阵中
	inFile.open("m2.txt");
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			inFile>>cost[i][j];
		}
	}
	inFile.close();
	//调用分支限界函数求解
	AlgBB(cost,length);
	return 1;
}