jinji.cpp

禁忌搜索算法的例子程序求解Tsp问题

#include "stdio.h"
#include "stdlib.h"
int D[5][5]={0,10,15,6,2,10,0,8,13,9,15,8,0,20,15,6,13,20,0,5,2,9,15,5,0};
int tabu[6]={0};
int cand[6]={0};
int fbest=59;//45[0 1 2 3],60[0 2 1 3],60[3 1 0 2],59[3 0 1 2]
int xbest[4]={3,0,1,2};
int x[4]={3,0,1,2};
int f=59;
int bnum=0;

int find(int array[],int k)
{
	int i=0;
	for (;i<4;i++){
		if (array[i]==k) {
			return i+1;
		}
	}
}
void CreAns( )
{
	int temp = 100;
	int ftemp = 100;
	int t;
	int pos=-1;
    int k=-1;
	for (int i=0;i<6;i++){
		if (!tabu[i]&&(temp > cand[i])) {
			temp = cand[i];
			k = i;
		}
		if (ftemp > cand[i]) {
			ftemp = cand[i];
			pos = i;
		}
	}
	if (k == -1) {
		switch(pos) {
		case 0:
			t=x[0];
			x[0]=x[1];
			x[1]=t;
			break;
		case 1:
			t=x[0];
			x[0]=x[2];
			x[2]=t;
			break;
		case 2:
			t=x[0];
			x[0]=x[3];
			x[3]=t;
			break;
		case 3:
			t=x[1];
			x[1]=x[2];
			x[2]=t;
			break;
		case 4:
			t=x[1];
			x[1]=x[3];
			x[3]=t;
			break;
		case 5:
			t=x[2];
			x[2]=x[3];
			x[3]=t;
			break;
		}
		for(int j=0;j<6;j++){
			if (tabu[j] > 0) {
				tabu[j] -=1;
			}
		}
		if (fbest > ftemp) {
			for (int i=0;i<4;i++)
			    xbest[i] = x[i];
			fbest = ftemp;
		}	
		tabu[pos] = 3;
		bnum++;
	}
	if (k != -1) {
		switch(k) {
		case 0:
			t=x[0];
			x[0]=x[1];
			x[1]=t;
			break;
		case 1:
			t=x[0];
			x[0]=x[2];
			x[2]=t;
			break;
		case 2:
			t=x[0];
			x[0]=x[3];
			x[3]=t;
			break;
		case 3:
			t=x[1];
			x[1]=x[2];
			x[2]=t;
			break;
		case 4:
			t=x[1];
			x[1]=x[3];
			x[3]=t;
			break;
		case 5:
			t=x[2];
			x[2]=x[3];
			x[3]=t;
			break;
		}
		f=cand[k];
		for(int j=0;j<6;j++){
			if (tabu[j] > 0) {
				tabu[j] -=1;
			}
		}
		if (fbest > temp) {
			for (int i=0;i<4;i++)
			    xbest[i] = x[i];
			fbest = temp;
		}	
		tabu[k] = 3;
	}
}
void CreCan( )
{
	int prior ;
	int pos=-1;
	int k=0;
	int x_temp[4];
	int t;
	int sum;
	int l;
	for (int i=0;i<6;i++){
		switch(i) {
	    case 0:
			for (l=0;l<4;l++)
			    x_temp[l] = x[l];
			t=x_temp[0];
			x_temp[0]=x_temp[1];
			x_temp[1]=t;
			sum = 0;
			k = 0;
			prior = 0;
			while (k<4) {
				pos = find(x_temp,k);
				sum = sum + D[prior][pos];
				prior = pos;
				k++;
			}
			sum = sum + D[prior][0];
			cand[0] = sum;
			break;
		case 1:
			for (l=0;l<4;l++)
			    x_temp[l] = x[l];
			t=x_temp[0];
			x_temp[0]=x_temp[2];
			x_temp[2]=t;
			sum = 0;
			k = 0;
			prior = 0;
			while (k<4) {
				pos = find(x_temp,k);
				sum = sum + D[prior][pos];
				prior = pos;
				k++;
			}
			sum = sum + D[prior][0];
			cand[1] = sum;
			break;
		case 2:
			for (l=0;l<4;l++)
			    x_temp[l] = x[l];
			t=x_temp[0];
			x_temp[0]=x_temp[3];
			x_temp[3]=t;
			sum = 0;
			k = 0;
			prior = 0;
			while (k<4) {
				pos = find(x_temp,k);
				sum = sum + D[prior][pos];
				prior = pos;
				k++;
			}
			sum = sum + D[prior][0];
			cand[2] = sum;
			break;
		case 3:
			for (l=0;l<4;l++)
			    x_temp[l] = x[l];
			t=x_temp[1];
			x_temp[1]=x_temp[2];
			x_temp[2]=t;
			sum = 0;
			k = 0;
			prior = 0;
			while (k<4) {
				pos = find(x_temp,k);
				sum = sum + D[prior][pos];
				prior = pos;
				k++;
			}
			sum = sum + D[prior][0];
			cand[3] = sum;
			break;
		case 4:
			for (l=0;l<4;l++)
			    x_temp[l] = x[l];
			t=x_temp[1];
			x_temp[1]=x_temp[3];
			x_temp[3]=t;
			sum = 0;
			k = 0;
			prior = 0;
			while (k<4) {
				pos = find(x_temp,k);
				sum = sum + D[prior][pos];
				prior = pos;
				k++;
			}
			sum = sum + D[prior][0];
			cand[4] = sum;
			break;
		case 5:
			for (l=0;l<4;l++)
			    x_temp[l] = x[l];
			t=x_temp[2];
			x_temp[2]=x_temp[3];
			x_temp[3]=t;
			sum = 0;
			k = 0;
			prior = 0;
			while (k<4) {
				pos = find(x_temp,k);
				sum = sum + D[prior][pos];
				prior = pos;
				k++;
			}
			sum = sum + D[prior][0];
			cand[5] = sum;
			break;
		}

	}
}
void insert(int array[])
{
	int Cn[2];
	int i,j;
	int pos;
	int index[4];
	Cn[0]=Cn[1]=-1;
	while (Cn[0]==Cn[1]) {
		for(i=0; i<2;i++){
		Cn[i]=rand()%4;
		}
	}
	for(j=0;j<2;j++){
		pos=array[Cn[j]];
	    array[Cn[j]]=-1;
	    for(i=0;i<4;i++){
		   if (array[i]>pos) {
			   array[i]--;
		   }
		}
	}
	for(i=0;i<4;i++){
		index[i]=-1000;
	}
	for(i=0;i<4;i++){
		if (array[i]>=0) {
			index[array[i]]=i;
		}
	}
	i=0;
	while (index[i]>=0) {
		
	}
}
int main()
{
	int i;
	for (i=0;i<10000;i++){
		CreCan();
		CreAns();
		if (bnum > 40) {
			break;
		}
	}
	
	printf("\n");
	for (i=0;i<4;i++)
	   printf("%d ",xbest[i]);
    printf(" %d\n",fbest);
	for (i=0;i<4;i++)
	   printf("%d ",x[i]);
	printf(" %d\n",f);
	return 1;

}