boundlesalesman.cpp

货郎担 分支限界 的相关代码 共同共享

#include "StdAfx.h"
#include "BoundleSalesMan.h"
#include "Node.h"
#include <queue>
#include <vector>
int BoundSalesMan::SimMatrix(vector<vector<int> > & m)
//将m规约
{
	int result=0;
	int col=(int)m.size()-1;
	bool boolMax,boolZone;
	//对行进行规约
	for (int i=0;i<=col;i++)
	{
		boolMax=true,
			boolZone=false;
		for (int j=0;j<=col;j++)
		{
			boolMax=boolMax && (m[i][j]==MAXNUM); //所有都是无穷大
			boolZone=boolZone || (m[i][j]==0) ; //是否有一个是0
		}
		if ((boolMax) || (boolZone))
			//如果本行所有数据元素都是无穷大，或者有一个是0，本行已经规约
			continue;//继续下一行
		else  //否则
		{
			//从本行中找到最小的一个值，减去他，约数加上这个值
			int min=m[i][0];
			for (int k=1;k<=col;k++)
			{
				if (min>m[i][k])
					min=m[i][k];
			}
			for (int k=0;k<=col;k++)
			{
				if (m[i][k]!=MAXNUM)  //如果是无穷值，则不变
					m[i][k]-=min;
			}
			result+=min;
		}
	}    
	//对列进行规约
	for (int i=0;i<=col;i++)
	{
		boolMax=true,
			boolZone=false;
		for (int j=0;j<=col;j++)
		{
			boolMax=boolMax && (m[j][i]==MAXNUM); //所有都是无穷大
			boolZone=boolZone || (m[j][i]==0) ; //是否有一个是0
		}
		if ((boolMax) || (boolZone))
			//如果本列所有数据元素都是无穷大，或者有一个是0，本列已经规约
			continue;//继续下一列
		else  //否则
		{
			//从本列中找到最小的一个值，减去他，约数加上这个值
			int min=m[0][i];
			for (int k=1;k<=col;k++)
			{
				if (min>m[k][i])
					min=m[k][i];
			}
			for (int k=0;k<=col;k++)
			{
				if (m[k][i]!=MAXNUM) //如果是无穷值，则不变
					m[k][i]-=min;
			}
			result+=min;
		}
	}
	return result;
}
int  BoundSalesMan::SetIMatrix(int i,int k,vector<vector<int> > & im)
//生成第i点的规约矩阵
{
	int cols=im.size()-1;
	//先将k行和i列置为无穷/
	for (int j=0;j<=cols;j++)
	{
		im[k][j]=MAXNUM;   
		im[j][i]=MAXNUM;
	}
	//再将i行0列置为无穷
	im[i][0]=MAXNUM;   
	//再进行规约，记录规约值
	return SimMatrix(im);
}

int BoundSalesMan::Cost(vector<int> A)
//获取A中保存的路径的路径长度
{
	int i=A.size();
	int sum=matrix[0][A[0]];//先求从0到第一个点的距离
	for (unsigned int i=1;i<A.size();i++)
	{
		sum+=matrix[A[i-1]][A[i]];
	}
	sum+=matrix[A[i-1]][0];//再加上最后一个点到0点的距离
	return sum;
}
void BoundSalesMan::Travel()
{
	path.clear();
	vector<vector<int> > simpleM=matrix; //0点的规约矩阵
	int n0=SimMatrix(simpleM);
	int cols=matrix.size()-1;   
	priority_queue<Node> p;
	Node firstNode(n0,0,0,path,simpleM); 
	p.push(firstNode);                    //0结点入队列
	Node node;
	while (! p.empty() && p.top().level<cols )
	{
		node=p.top();
		p.pop();
		for (int i=1;i<=cols;i++)
		{
			for (int j=0;j<node.states.size();j++)
			{
				if (i==node.states[j]) //路径里有这个点了
					break;
			}
			if (j<node.states.size()) 
				continue;  
			//否则
			simpleM=node.m;
			int tmp=node.num;
			tmp+=simpleM[node.position][i];
			tmp+=SetIMatrix(i,node.position ,simpleM); //对第i点的矩阵进行处理                       vector<int> tmpPath=node.states;
			tmpPath.push_back(i);
			Node newNode(tmp,node.level+1,i,tmpPath,simpleM);
			p.push(newNode);
		}
	}
	path=p.top().states;
	cout<<"Bound MinValue:"<<Cost(path)<<endl;
	PrintPath();
}