#include <math.h>
#include <stdlib.h>
#include <fstream>
#include <time.h>
#include <stdio.h>
using namespace std;

const int iAntCount = 34;//螞蟻數量
const int iCityCount = 51;//城市數量
const int iItCount = 2000;//最大跌代次數
const double Q = 100;//每只螞蟻周游一遍留下的信息素總量
const double alpha = 1;//信息素濃度所起作業的程序
const double beta = 5;//期望值所起作用的程度
double rou = 0.5;//揮發系數
int besttour[iCityCount];//最優路徑列表
int count=0;//記錄連續多少代沒有產生更優的解
double  rnd(double low,double uper)//獲得隨機數, 范圍為 [low, uper]
{
	double p = (rand()/(double)RAND_MAX)*((uper)-(low))+(low);
	return p;
};

int rnd(int uper)	//返回[0,uper]之間的整數
{
	return (rand()%uper);
};
class GInfo {//tsp地圖信息，包含了信息素，城市距離，和信息素變化矩陣
public: 
	double m_dDeltTrial[iCityCount][iCityCount]; //信息素變化矩陣
	double m_dTrial[iCityCount][iCityCount]; //信息素
	double distance[iCityCount][iCityCount]; //城市距離
};
GInfo Map;	//地圖
class ant {	//螞蟻類
private:
	int ChooseNextCity();//選擇城市
	int m_iCityCount;	//已走過的城市個數
	int AllowedCity[iCityCount];//沒有走過的城市
public:
	void addcity(int city); //把城市放到已走過的路數組中
	int tabu[iCityCount];/*記錄螞蟻行走順序*/
	void Reset();  //重置
	void UpdateLength(); //更新路徑長度
	double m_dLength;	//路徑長度
	void mov();			//直到下一步
	ant();
	double AntProduct( int from, int to );	//螞蟻在from和to城市之間的路線上撒下的信息素
};
void ant::Reset()
{
	int i;
	m_dLength=0;

	for(i=0; i<iCityCount;i++) {
		AllowedCity[i]=1;
	}

	i=tabu[iCityCount-1];  //從終點城市返回
	m_iCityCount=0;
	addcity(i);
}
ant::ant()
{
	int i;
	m_dLength=0;
	m_iCityCount=0;

	for(i=0;i<iCityCount;i++) {
		AllowedCity[i]=1;/*一開始每個城市都可訪問*/
	}
}
void ant::addcity(int city)
{
	tabu[m_iCityCount]=city; //記錄city為走過的城市
	m_iCityCount++;
	AllowedCity[city]=0;
}
double ant::AntProduct(int from, int to )
{
	double p;
	p=pow((1.0/Map.distance[from][to]),beta)*pow((Map.m_dTrial[from][to]),alpha);	//轉移期望
	if( p<=0)p=rnd(0,1)*pow( (1.0 / Map.distance[from][to]), beta);  //如果沒有其他螞蟻走過，就按距離選擇
	return p;
}
int ant::ChooseNextCity()
{
	int i,to=-1;	//to為下一個要到的城市
	double hormone=0;	//信息總量
	int curCity=tabu[m_iCityCount-1];	//當前城市

	if(count<6)	//如果沒有產生最優解的代數不超過6，則斷續按信息素的濃度選擇城市
	{
		for (i=0;i<iCityCount;i++) {
			if((AllowedCity[i]==1)) {
				hormone += AntProduct(curCity,i);//計算信息總量
			}
		}

		if(hormone==0.0)
		{
			to=rnd(iCityCount);	//如果所有的城市都走完一遍，則隨意先一個城市
		}
		else
		{
			for(to=0;to<iCityCount;to++)
			{
				double p;
				if(AllowedCity[to]==1)
				{
					p=AntProduct(curCity,to)/hormone;
					if(rnd(0,1)<p)	//按轉移概率大小選擇下一個城市，同時也避免了局部最優解
						break;
				}
			}
		}
		if(to==iCityCount)
		{
			hormone=-1;
			for(i=0;i<iCityCount;i++)
				if(AllowedCity[i]==1)
				{
					if (hormone<AntProduct(curCity,i)) {
						hormone=AntProduct(curCity,i);	//如果上一步選擇失敗，則選擇具有最大信息量的城市
						to=i;
					}
				}
		}
	}
	
	if(count>=6)	//當連續6代都沒有產生更短的路徑，則
	{
		for ( i=0;i<iCityCount;i++) {
			if((AllowedCity[i]==1)) {
				to=i;
				count=0;
				rou=0.5;
				if(rnd(0.0,1.0)>0.5)	//隨機選擇一個還沒訪問的城市
				{
					break;
				}
			}
		}
	}
	return to;
}
void ant::UpdateLength()
{
	// Update the length of tour
	int i;
	for(i=0;i<iCityCount-1;i++) {
		m_dLength+=Map.distance[tabu[i]][tabu[i+1]];	//計算路徑長度
	}
	m_dLength+=Map.distance[tabu[iCityCount-1]][tabu[0]]; //加上第一個與最后一個城市之間的距離
}
void ant::mov()
{
	addcity(ChooseNextCity());
}
class AntProj
{
public:
	void UpdateTrial();	//更新信息素
	double m_dLength;	//記錄最佳路徑長度
	void initmap();		//初始化地圖
	ant ants[iAntCount];//蟻群
	void GetAnt();		//初始蟻群
	void StartSearch();	//搜索路徑
	AntProj();
	struct city {
		int num;//城市號
		int x; //城市坐標
		int y;
	}cc[iCityCount];
};
void AntProj::UpdateTrial()
{
	int i;
	int j;
	int from,to;
	for(i=0;i<iAntCount;i++) {
		for (j=0;j<iCityCount-1;j++) { 
			from=ants[i].tabu[j];
			to=ants[i].tabu[j+1];
			Map.m_dDeltTrial[from][to]+=Q/ants[i].m_dLength ;   //增加的信息量
			Map.m_dDeltTrial[to][from]=Map.m_dDeltTrial[from][to]; //兩個方向的信息量相等
		}
		from=ants[i].tabu[iCityCount-1];
		to=ants[i].tabu[0];
		Map.m_dDeltTrial[from][to]+=Q/ants[i].m_dLength ;	//加上起點和終點之間的信息量
		Map.m_dDeltTrial[to][from]=Map.m_dDeltTrial[from][to]; //兩個方向的信息量相等
	}

	for (i=0;i<iCityCount;i++) {
		for (j=0;j<iCityCount;j++) {
			Map.m_dTrial[i][j]=(rou*Map.m_dTrial[i][j]+Map.m_dDeltTrial[i][j] );  //計算新的信息量
			Map.m_dDeltTrial[i][j]=0;
		}
	}
}
void AntProj::initmap()
{
	int i;
	int j;

	for(i=0;i<iCityCount;i++) {
		for (j=0;j<iCityCount;j++) {
			Map.m_dTrial[i][j] = 1; //信息素初始化為1，信息素變化量初始化為0
			Map.m_dDeltTrial[i][j] = 0;
		}
	}
}
AntProj::AntProj()/*intialize pheromone, delta-pheromone, distance */
{
	initmap();	//初始化地圖
	m_dLength=10e9;

	ifstream in("eil51.tsp");/*打開測試文件 */

	for (int i=0;i<iCityCount;i++) {
		in>>cc[i].num>>cc[i].x>>cc[i].y; //調入城市數據
		besttour[i]=0;
	}
	int j;

	for(int i=0;i<iCityCount;i++) {
		for (j=0;j<iCityCount;j++) {//計算兩城市之間的距離
			Map.distance[i][j]=sqrt(pow((double)(cc[i].x-cc[j].x),2)+pow((double)(cc[i].y-cc[j].y),2));
		}
	}
}
void AntProj::GetAnt()
{
	int i=0;
	int city;
	/* 
	本句的作用就是以系統時鐘產生的隨機數作為srand的一個種子
	*/
	srand( (unsigned)time( NULL ));

	for ( i=0; i<iAntCount; i++) {/* 把一只螞蟻隨機地放在一個城市上 */
		city = rnd(iCityCount);
		ants[i].addcity(city);
	}
}
void AntProj::StartSearch()
{
	int max=0;//當前的代數
	int i;
	int j;
	double temp;

	FILE * outresult=fopen("result.txt","w+");
	fprintf(outresult," 代數   最短路徑\n");
	while (max<iItCount) {  
		for(i=0;i<iCityCount-1;i++)  { //總共前進iCityCount-1步遍歷完所有城市
			for (j=0;j<iAntCount;j++) {//所有的螞蟻都前進一步
				ants[j].mov(); 
			}
		}

		for(j=0;j<iAntCount;j++) {
			ants[j].UpdateLength ();	//更新螞蟻的路徑長度
		}
		int t,minant;

		temp=ants[0].m_dLength; //臨時的最優路徑長度
		minant=0;

		for(j=1;j<iAntCount;j++) {
			if (temp>ants[j].m_dLength) {
				temp=ants[j].m_dLength;
				minant=j;				//找出周游路徑最短的螞蟻
			}
		}
		if(temp<m_dLength){
			count=0;	
			rou+=0.1;	//如果產生了更短的路徑，則減慢信息素的揮發，獲得更多的啟發信息
			if(rou>=0.9)
				rou=0.9;
			m_dLength=temp;	//記錄更優的路徑長度
			for ( t=0;t<iCityCount;t++) {
				besttour[t]=ants[minant].tabu[t];//記錄周游路徑
			}
		}
		else
			count++;
		if(count>=2) //如果連續兩代都沒有產生更好的路徑，則加快信息素的揮發，減少信息素的作用
		{
			rou-=0.1;
			if(rou<=0.1)
				rou=0.1;
		}
		printf("%d : %f\n",max,m_dLength);
		fprintf(outresult,"  %d  :  %f\n",max,m_dLength);
		UpdateTrial(); //更新信息素
		for(j=0;j<iAntCount;j++) {
			ants[j].Reset();	//重置螞蟻的數據
		}
		max++;
	}

	printf("The shortest toure is : %f\n",m_dLength);	//輸出當代最小路徑值
	fprintf(outresult,"最短周游路徑為：%f\n",m_dLength);
	fprintf(outresult,"最優路徑為：\n");
	for ( int t=0;t<iCityCount;t++) {
		printf(" %d ",cc[besttour[t]]);	//輸出當代最代路徑
		fprintf(outresult," %d ",cc[besttour[t]]);
	}
	fclose(outresult);
}
int main()
{
	AntProj TSP; //聲明一個測試對象
	TSP.GetAnt();//初始化蟻群
	TSP.StartSearch();//尋找最短路徑
	printf("\n");

	char c;
	scanf("%c",&c);
	return 0;
}