2-22.cpp

图论中使用分支与界法求解旅行商问题

// 991331 Wang Tian, Class 91
// FENZHIYUJIE FA
#include<stdio.h>

struct BLB{ //Bianliebiao
	int m,n;
	int *A;
	int *B;
	int *Z;
};

int isValidPath(int *result, struct BLB *blb)
{
	int i,j,count=0,ptr=0,flag=0;
	int useA=1,node1,node2;
	int *ue=new int[blb->n];	//Used Edge in result (index of result[])
	int *un=new int[blb->n];	//Used Node number

	for(i=0;i<blb->n;i++)
		un[i]=ue[i]=0;

	do {
		if(useA) {
			node1=blb->A[result[ptr]];
			node2=blb->B[result[ptr]];
		}
		else {
			node1=blb->B[result[ptr]];
			node2=blb->A[result[ptr]];
		}

		un[node1-1]++;
		ue[ptr]++;
		if((un[node1-1]==2) && (count!=blb->n))return(0);
		for(i=0;i<blb->n;i++){if (un[i]!=1) flag=1;}
		if(!flag) return(1);
		flag=0;

		for(j=0;j<blb->n;j++){
			if(!ue[j]) {
				if (node2==blb->A[result[j]])
					{ useA=1; ptr=j; break; }
				if (node2==blb->B[result[j]])
					{ useA=0; ptr=j; break; }
			}
		}
		if (j!=ptr) return(0);
		count++;
	}while(count<blb->n);
	return(1);
}


int getExpense(int* result, struct BLB *blb)
{
	int exp=0;
	for(int i=0;i<blb->n;i++) exp+=blb->Z[result[i]];
	return(exp);
}

int canAdd(int edge_ptr, int result_ptr, int* result, struct BLB* blb)
{
	//If the new path has nodes that has appeared 0 or 1 times, add it
	if(result_ptr==0) return(1);
	int *t,i;
	t=new int[blb->n];
	for(i=0;i<blb->n;i++) t[i]=0;
	for(i=0;i<result_ptr+1;i++){
		t[blb->A[result[i]]-1]++;
		t[blb->B[result[i]]-1]++;
	}
	if((t[blb->A[edge_ptr]-1]<=1)&&(t[blb->B[edge_ptr]-1]<=1)) return(1);
	else return(0);
}

int *findH(struct BLB* blb)
{
	if ((!blb)||(blb->m<=0)||(blb->n<=0)||(blb->n>blb->m)) return(0);
	//Bubble sort
	int i,j,k,flag=0;
	for(i=0;i<blb->m;i++){
		for(j=0;j<blb->m-1;j++){
			if (blb->Z[j]>blb->Z[j+1]) {
				k=blb->Z[j];blb->Z[j]=blb->Z[j+1];blb->Z[j+1]=k;
				k=blb->A[j];blb->A[j]=blb->A[j+1];blb->A[j+1]=k;
				k=blb->B[j];blb->B[j]=blb->B[j+1];blb->B[j+1]=k;
				flag=1;
			}
		}
		if(flag==0) break;
	}
	/*/////////////DISPLAY SORTED ARRAY
	for(i=0;i<blb->m;i++){
		printf("(%d,%d)=%d ",blb->A[i],blb->B[i],blb->Z[i]);
	}
	/////////////*/
	int *result,*old_result,*stack;
	unsigned int old_min=65535,min=65535;
	int stack_ptr=0,result_ptr=0,edge_ptr=0;
	result=new int[blb->n];			//Used to store the number of edge
	old_result=new int[blb->n];		//Used to store result
	stack=new int[blb->m];
	int pid=1;
	//Init
	for(i=0;i<blb->n;i++) result[i]=0;
	for(i=0;i<blb->m;i++) stack[i]=0;
	//Begin search
	do{
		result[result_ptr]=edge_ptr;
		if (result_ptr==blb->n-1) {	//result complete
			if ((result[blb->n-1]-result[blb->n-2]==1)&&(getExpense(result,blb)>old_min))
				return(old_result);
			if (isValidPath(result,blb)) {
				min=getExpense(result,blb);
				if (min<old_min) {
					old_min=min;
					printf("%d path(s) found\n",pid++);
					for(i=0;i<blb->n;i++) old_result[i]=result[i];
					do { //POP
						stack_ptr--;
						result_ptr--;
						edge_ptr=stack[stack_ptr]+1;
					} while(edge_ptr==blb->m);
					continue;
				}
				else return(old_result); //found, exit
			}
			else {
				if ((result[blb->n-1]-result[blb->n-2]==1)&&(getExpense(result,blb)>old_min))
					return(old_result);
				edge_ptr++;
				while(edge_ptr==blb->m){//POP
					stack_ptr--;
					result_ptr--;
					edge_ptr=stack[stack_ptr]+1;
				}
				continue;
			}
		}
		else { //PUSH
			stack[stack_ptr]=edge_ptr;
			//Find the next node
			do{
				edge_ptr++;
				if(canAdd(edge_ptr, result_ptr, result, blb))
					break;
			}while(edge_ptr<blb->m-1);
			stack_ptr++;result_ptr++;
		}
	} while(-1);
	return(0);
}

void main()
{
	struct BLB* blb=new BLB;
	int i;
	printf("How many vertex? "); scanf("%d",&blb->n);
	printf("How many edges? "); scanf("%d",&blb->m);
	blb->A=new int[blb->m];
	blb->B=new int[blb->m];
	blb->Z=new int[blb->m];
	printf("Now enter edges' vertex and their length...\n");
	for(i=0;i<blb->m;i++){
		printf("***Edge %d***\n From   : ",i+1);scanf("%d",&blb->A[i]);
		printf(" To     : ");scanf("%d",&blb->B[i]);
		printf(" Length : ");scanf("%d",&blb->Z[i]);
		printf("\n");
	}
	int *result=findH(blb);
	printf("\nBest Path:\n ");
	for(i=0;i<blb->n;i++)
		printf("(%d,%d)   ",blb->A[result[i]],blb->B[result[i]]);
	printf("\nTotal length: %d\n",getExpense(result,blb));
}