tree.cpp

Solving the TSP problem using the Branch and Bound Algorithm

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include <time.h>
typedef struct {
	int nSource;          //where the Arc from
	int nDestination;     //where the Arc want to go
	long nLength;         //how long the Arc is
}Arc;
typedef struct _TreeNode
{
	long nLength;       //the length if choose one arc
	long nCost;         // The  cost if choose one arc
	Arc theArc;         //The Choosed Arc
	_TreeNode *parent;  // parent of this node
	_TreeNode *lchild;//left and right child;
}TreeNode,*pTreeNode;

Arc ArcArray[500];
long Cost[51][51];
void Printout(pTreeNode p);
////////////////////1,load from text
void LoadFromText()
{
	int i,j,k = 0,m = 0;
	long nTemp = 0;
	ifstream fm1("m1.txt");
	for(i = 1;i<=50;i++)
	{
		for(j = 1;j<=50;j++)
		{
			fm1>>nTemp;
			if(nTemp==9999)
				continue;
			ArcArray[k+m].nLength = nTemp;
			ArcArray[k+m].nSource = i;
			ArcArray[k+m].nDestination = j;
			k++;
		}
		k = 0;
		m = i * 10;
	}
	fm1.close();
	ifstream fm2("m2.txt");
	for(i = 1;i<=50;i++)
		for(j = 1;j<=50;j++)
		{
			fm2>>Cost[i][j];
		}
	fm2.close();
}

///////////////////////////////////2,Sort the Array of Arc
void SortToArray()
{
	int i = 0,j = 0,k = 0;
	for(i = 0;i<50;i++)
	{
		for(j = 0;j<10;j++)
		{
			if(ArcArray[j+i*10].nLength!=0)
			for(k = 0;k<j;k++)
				if(ArcArray[k+i*10].nLength>ArcArray[j+i*10].nLength)
				{
					Arc aTemp = ArcArray[k+i*10];
					ArcArray[k+i*10] = ArcArray[j+i*10];
					ArcArray[j+i*10] = aTemp;
				}
		}
	}
}

/////////////////////////////////3,Construct a Tree
long MinLength;
int IsVisited[51][51];
int IsNodeVisited[51];
long MintoPoint[51];
long MinCosttoPoint[51];
pTreeNode ConstructTree(Arc oneArc,pTreeNode preNode,int &goon)
{

	if(goon==1){
		return NULL;
	}
	/////if a Arc is visited,this is not a feasible solution
	
	if(IsVisited[oneArc.nSource][oneArc.nDestination] == 1){
	
		return NULL;
	}
	////if a node is visited , this is also not a feasible solution
	if(IsNodeVisited[oneArc.nDestination]==1){
		return NULL;
	}
	if(oneArc.nLength == 0)
		return NULL;
	//////initialize a TreeNode
	pTreeNode Root = new _TreeNode;
	Root->nLength = preNode->nLength + oneArc.nLength;
	Root->nCost = preNode->nCost + Cost[oneArc.nSource][oneArc.nDestination];
	Root->theArc = oneArc;
	Root->parent = NULL;
	if(Root->nLength > MintoPoint[oneArc.nDestination] && 
		Root->nCost > MinCosttoPoint[oneArc.nDestination]){
		delete Root;
		return NULL;
	}
	////if the length is longer than the current min one,it is not a feasible 
	////solution
	////if the cost is more than 1500,it is not the feasible solution
	if(Root->nLength>MinLength||Root->nCost>1500){
		delete Root;
		return NULL;
	}

	////mark this arc and the ard's destination be visited
	IsVisited[oneArc.nSource][oneArc.nDestination] = 1;
	IsNodeVisited[oneArc.nDestination] = 1;

	////if the arc's destination is 50(the last node),and its length is smaller
    ////than the current min length, so it is a feasible solution
	if(oneArc.nDestination == 50 && Root->nLength < MinLength)
	{
		MinLength = Root->nLength;
		Root->parent = preNode;
		cout<<"the path length is : "<<MinLength<<endl;
		cout<<"the cost of this path is :"<<Root->nCost<<endl;
		Printout(Root);
		cout<<"Searching for other feasible solutions..."<<endl;
		goon = 1;
		return NULL;
	}
	Root->parent = preNode;
	int i = 0; 
	Arc anotherArc ;
	////first,selete the smallest arc,if this arc cannot make a feasible solution
	////select a longer one and so on,if all these arcs cannot make the feasible 
	////solution delete this node, this branch is unfeasible.
	while(i<6)
	{
		anotherArc = ArcArray[(oneArc.nDestination-1)*10+i];
		if(anotherArc.nLength!=0&&IsVisited[anotherArc.nSource][anotherArc.nDestination]!=1)
		{
			Root->lchild = ConstructTree(anotherArc,Root,goon);
		    if(Root->lchild == NULL)
			{i++;continue;}
			else{break;}
		}
		i++;
		
	}
	if(i==6){//not found
		IsVisited[oneArc.nSource][oneArc.nDestination] = 0;
		IsNodeVisited[oneArc.nDestination] = 0;
		if(goon!=1)
		    delete Root;
		return NULL;
	}
	
	
	return Root;
}
////////////////////////////////////4,print out
void Printout(pTreeNode p)
{
	if(p==NULL)
		return;
	char chTemp[100][10];
	int i = 0;
	pTreeNode q;
	while(1)
	{
		//p = p->parent;
		if(p->theArc.nDestination<0)
			return;
		if(MintoPoint[p->theArc.nDestination]>p->nLength && p->theArc.nSource!=1)
		{
			MintoPoint[p->theArc.nDestination] = p->nLength;
			MinCosttoPoint[p->theArc.nDestination] = p->nCost;
		}
	    _itoa(p->theArc.nSource, chTemp[i],10);
		i++;
		if(p->theArc.nSource==1)
			break;
		q = p;
		p = p->parent;
		if(p!=NULL)
			delete q;

	}
	cout<<"A feasible solution is:"<<endl;
	//cout<<"1 -> "
	i--;
	for(;i>=0;i--)
	{
		cout<<chTemp[i]<<" -> ";
	}
	cout<<"50"<<endl;
}

	

void main()
{
	struct tm *newtime;
    time_t long_time;
	time( &long_time );                /* Get time as long integer. */
    newtime = localtime( &long_time ); /* Convert to local time. */
	int min1 = newtime->tm_min;
	int sec1 = newtime->tm_sec;
	LoadFromText();
	SortToArray();
	////this is a very tightened bound by my experiment.
	////if not this bound it will take more time to find the 
	////best solution
	MinLength = 9999;
	int nTemp = MinLength;
	char wait;
	int i,j,k,m;
	for(i = 0;i<51;i++)
	{
		MintoPoint[i] = 9999;
	}
	for(i = 0;i<51;i++)
	{
		MinCosttoPoint[i] = 9999;
	}
	for(m = 0; m<6;m++){
		if(m>0)
		  for(k = m-1;k>=0;k--)
			ArcArray[k].nLength = 0;
		while(1)
		{
			for(i = 1;i<=50;i++)
				for(j = 1;j<=50;j++)
					IsVisited[i][j] =0;
			for(i = 1;i<=50;i++)
				IsNodeVisited[i] = 0;
			cout<<"please wait..."<<endl;
			pTreeNode Head = new _TreeNode;
			Head->nCost = 0;
			Head->nLength = 0;
			i = 0;
			ConstructTree(ArcArray[m],Head,i);
			if(nTemp == MinLength)
				break;
			nTemp = MinLength;
			i = 0;
			delete Head;
		}
	}
	cout<<"no more feasible solutions"<<endl;
	struct tm *newtime1;
	time_t long_time1;
	time( &long_time1 );                /* Get time as long integer. */
    newtime1 = localtime( &long_time1 ); /* Convert to local time. */
	int min2 = newtime1->tm_min;
	int sec2 = newtime1->tm_sec;
	int minutes = min2-min1;
	int secs = sec2 - sec1;
	if(minutes<0)
		minutes += 60;
	if(secs<0)
	{
		minutes--;
		secs += 60;
	}
	cout<<"this process runs : "<<minutes<<" minutes , "<<secs <<" secs"<<endl;
	cin>>wait;	
	//Printout(Head);
}