main.c

暴力破解TSP中国邮递员问题的程序。使用数据为Oliver30.tsp

//433.436055
//428.730955
//goal=423.245
//426.777745 - 12350269
//426.425447
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "acs.h"
#include "tsp.h"
#include "data_input.h"

#include <math.h>
extern double distances[CITY_NUM+1][CITY_NUM+1];
FILE *f_out=NULL;

//递归设置后续城市的位置
//找到一个以前没有使用的位置即可，递归处理后续城市位置，直到最后一个城市
void setAL(unsigned long pAL[CITY_NUM],int row)
{
	unsigned long tobu=0,temp;
	int i,j;
	for(i=0;i<row;i++) tobu= tobu | pAL[i];
	for(j=1;j<CITY_NUM;j++)
	{
		temp=(unsigned long)pow(2,j);
		if((~tobu & temp)!=0)
		{
			pAL[row]=1<<j;
			if( (row +1)==CITY_NUM ) return;
			setAL(pAL,row+1);
			break;
		}
	}
}
//更新路径序列，1234--1243---1324---1342--1423---1432
//从最后路径开始变更，第一个路径不变
//无法改变时返回0，其它返回1
int setNewPosition(unsigned long pAL[CITY_NUM])
{
	unsigned long tobu=0,temp;
	int i,j,find=0;
	for(i=CITY_NUM-1-1;i>0;i--)//从倒数第二个城市开始
	{
		find=0;
		tobu=0;
		for(j=0;j<i;j++) tobu=tobu | pAL[j];//计算以前使用过的位置
		for(j=1;j<CITY_NUM;j++)
		{
			temp=(unsigned long)pow(2,j);
			if((~tobu & temp)!=0)//找以前没有使用过的位置
			{
				if( find == 0  )//找到
				{
					if( pAL[i] == (1 << j) )//找到当前所在位置后才能更新为新位置
						find =1;//找到当前所在位置标记
				}
				else if(find == 1)//第二次找到
				{
					pAL[i]=1 << j;//更新为新位置
					setAL(pAL,i+1);//递归设置后续城市的位置
					return 1;
				}
			}
		}//for j
	}//for i
	return 0;
}

int main(void)
{
    Point p[CITY_NUM+1];
	int i=0;
	int position[CITY_NUM];//路径序列
	int index=0;//运行次数
	unsigned long AL[CITY_NUM];//保存每个路径所在的位置，为2的幂数1，2，4，8，16----
	double len=0,minLen=10000;//保存最小路径长度
	double tempd=0;
	for(i=0;i<CITY_NUM;i++) AL[i]=1<<i;//按123456789.。。。的顺序开始计算路径长度
	if ( (f_out = fopen("result.txt", "w+")) == NULL)
	{
		fprintf(stderr, "can not create file result.txt\n");
		exit(2);
	}

    read_data("Oliver30.tsp", p);/*    print_coordinates(p); */
    caculate_distances(p);/*	print_distance(); */


	while(1)
	{
		for (i = 0; i < CITY_NUM; i++)//根据路径位置读取路径序列
		{
			tempd=log(AL[i])/log(2.0);
			position[i]=(int)(tempd);
			if( tempd > position[i] ) position[i]++;
		}
		len=0;
		for (i = 0; i < CITY_NUM-1; i++)//计算路径长度
			len += distances[position[i]+1][position[i+1]+1];
		len += distances[position[CITY_NUM-1]+1][1];
		
		index++;
		if(minLen > len )//保存路径信息到文件
		{
			printf("%d - %f-%f\t",index, minLen,len);
			minLen=len;
			    for (i = 0; i < CITY_NUM; i++)
				{
					fprintf(f_out, "%d-", position[i]+1);
				}
				fprintf(f_out, "%d----%f\n", position[0]+1,len);
				fclose(f_out);
				f_out = fopen("result.txt", "a+");
			
		}
		if(index %100000 ==0) printf("%d - %f-%f\t",index, minLen,len);
			
		if(setNewPosition(AL) == 0) break;//更新路径序列，1234--1243---1324---1342--1423---1432
	}


    return 0;
}