#include
#include
#include
#include
#include

#define?CITY_COUNT?51
#define?AntCount?30?
#define?NCMAX?300?
#define?alfa?1.0???//啟發因子，信息素的重要程度
#define?beta?2.0???//期望因子，城市間距離的重要程度
#define?rou?0.5??//信息素殘留參數
#define?Q?100.0????//總的信息素
double?distance[CITY_COUNT][CITY_COUNT];??//兩城市間距離矩陣//
double?tao[CITY_COUNT][CITY_COUNT];???//兩城市間信息素矩陣//?
int?bestTour[CITY_COUNT];??//存儲最佳路徑經過的城市//?

int?rnd（int?nLowint?nUpper）
{
	?return?nLow+（nUpper-nLow）*rand（）/（RAND_MAX+1）;
}
double?rnd_d（double?Lowdouble?Upper）
{
	double?Temp=rand（）/（（double）RAND_MAX+1.0）;
????return?Low+Temp*（Upper-Low）;

}
typedef?struct
{
	double?x;
	double?y;
}Location;
typedef?struct
{
	Location?*city;
}City;
typedef?struct?
{
	int?Path[CITY_COUNT];
	double?PathLength;
	int?AllowedCity[CITY_COUNT];
	int?CurCityN;
	int?MovedCityCount;
}Ant;
typedef?struct
{
	Ant?*?Ants;
	double???bestLength;
}?TSP;
void?Init_City（City?*Ci）
{
	Ci->city=（Location*）malloc（CITY_COUNT*sizeof（Location））;
	if（!Ci->city）??exit（OVERFLOW）;
}
void?InitList_TSP（TSP?*tsp）?????????????????????????
{
	tsp->Ants=（Ant*）malloc（AntCount*sizeof（Ant））;
	if（!tsp->Ants）?exit（OVERFLOW）;?????????????????????
	tsp->bestLength=1000000000;
}
void?Init_S（）
{
	int?ij;
	for（i=0;i	????for（j=0;j	????{
	????	tao[i][j]=1.0;??????//設置為1//?
	????}
}
void?CreateAnts（TSP?*tsp）
{

????int?ij;
????for（i=0;i????{
????	for（j=0;j????	{
????	????tsp->Ants[i].AllowedCity[j]=1;
????	????tsp->Ants[i].Path[j]=0;
????	}
????????tsp->Ants[i].PathLength=0.0;
????????tsp->Ants[i].CurCityN=rnd（0CITY_COUNT）;???//隨機選擇一個城市，編號0-50//?
????????tsp->Ants[i].Path[0]=tsp->Ants[i].CurCityN;
????????tsp->Ants[i].AllowedCity[tsp->Ants[i].CurCityN]=0;
????????tsp->Ants[i].MovedCityCount=1;
????}
}
void?GetLoc（City?*Ci）
{
	int?inumber;
	FILE?*fp;
	
	fp=fopen（“tsp.txt““r“）;
	if（fp==NULL）
	{
		printf（“無法打開數據文件.\n“）;
		exit（0）;
	}
	for（i=0;i	{
		fscanf（fp“%d%lf%lf“&number&Ci->city[i].x&Ci->city[i].y）;
????}
	fclose（fp）;
}

void?GetDistance（City?*Ci）
{
	int?ij;
	double?temp=0.0;
	for（i=0;i	{
	????for（j=0;j	????{
	????	temp=（Ci->city[i].x-Ci->city[j].x）*（Ci->city[i].x-Ci->city[j].x）+（Ci->city[i].y-Ci->city[j].y）*（Ci->city[i].y-Ci->city[j].y）;
	????	temp=pow（temp0.5）;
	????	distance[i][j]=temp;
	????}
????????distance[i][i]=0.0000000001;
	}?
}

void?updatetrial（TSP?*tsp）
{
	double?Temptao[CITY_COUNT][CITY_COUNT];
	int?m=0;
	int?n=0ij;
	memset（Temptao0sizeof（Temptao））;
	
	
	for（i=0;i	{
		for（j=1;j		{
			m=tsp->Ants[i].Path[j];
			n=tsp->Ants[i].Path[j-1];
			Temptao[n][m]=Temptao[n][m]+Q/tsp->Ants[i].PathLength;
			Tempt