/*
說明：對于論文中給出的算法 存在這樣一個問題：如果c和a只有一條路徑，而ab之間沒有路徑，
      那么當螞蟻從從c到a后該如何處理呢，因為螞蟻不能重復原路（文中假設），估計要出問題了，
	  不妨我們假設無路徑時 路徑為一個很大的值，但多大是一個合適的值呢，又不好確定。
	  此處取自身到自身為-1，無路徑為某個很大的值32767，要求對輸入的個路徑進行合理縮放
缺陷：1.當無法求解時會求得一個很大的值。2.在這里城市數量要在程序里修改，但這點不影響體現算法的的實質。
*/
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>

#define Infinite 32767//路經無窮大

const int m=1000;//count of ant
const int n=6;//城市數
const double To=0.2;//初始信息素

const double alfa=0.8;//參數
const double beta=1;//參數
const double row=0.2;//信息遺失參數

double edge[n][n];//初始時各城市之間的距離
double ph[n][n];//各邊的信息素值
int Just[m][n];//螞蟻未訪問的城市，此處我們這樣處理 當可訪問第i個城市時我們計Just[m][i]=1
                   //否則即為0
int start[m];//螞蟻的初始位置
int Locate[m];//記錄螞蟻的當前位置

int Tour[m][n];//螞蟻的路徑
double g[n][n];//啟發函數此處在初始時設為1/distict
double Len[m];//螞蟻的路徑長度

double q;//公式3中的參數
double q0=0.8;
int sk[m];//下一個待選擇的城市

/*初始化城市和路經以及各個螞蟻的初始位置 */
void IntiNode()
{
	//輸入各城市之間的路徑
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			edge[i][j]=Infinite;
	printf("共%d城市請輸入各城市之間的距離\n",n);
	for(i=0;i<n-1;i++)
		for(int j=i+1;j<n;j++)
		{
			printf("%d-->%d:",i,j);
			scanf("%lf",&edge[i][j]);
			printf("\n");
		}
   
	for(i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(i>j)
				edge[i][j]=edge[j][i];	
  
	//輸入螞蟻的初始位置
    for(i=0;i<m;i++)
		start[i]=i%n;
	
	//設置啟發函數g	
	for(i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			if(i!=j)
			{
				g[i][j]=(double)1/edge[i][j];				
			}
		}	
}
/*初始化信息素*/
void IntiPh()
{
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			if(i!=j)
			{
				ph[i][j]=To;
			}
		}
}
/*初始化螞蟻*/
void IntiAnt()
{
	//設置Just
	for(int i=0;i<m;i++)
		for(int j=0;j<n;j++)
			Just[i][j]=1;

   for(i=0;i<m;i++)
	   Len[i]=0;

	for(int k=0;k<m;k++)
	{		
		Just[k][start[k]]=0;//開始位置設置為不可訪問
		Locate[k]=start[k];
	}
}
/*根據T獲得sk*/
int getsk(int k)//k已在數組范圍內
{
	double temp=0.0;
	int sk=0;
	int lk=Locate[k];//當前位置
	for(int i=0;i<n;i++)
	{
		//if(Just[k][i]==1 && lk!=i && edge[lk][i]!=Infinite && temp < pow(ph[lk][i],alfa)*pow(g[lk][i],beta))
		if(Just[k][i]==1 && lk!=i && temp < pow(ph[lk][i],alfa)*pow(g[lk][i],beta))
		{
			temp=pow(ph[lk][i],alfa)*pow(g[lk][i],beta);
			sk=i;
		}
	}
	return sk;
}
/*產生0-1之間的一個隨機數*/
double drand()
{	
	return ((double)rand())/(double)Infinite;
}
/*根據p獲得sk 可以這樣來實現根據概率確定sk 對0-1按概率進行劃分成若干段，
 產生一個0-1之間的隨機數，根據該數值所在的范圍來確定sk 這樣既體現了概率又唯一確定一個值 */
int getSK(int k)
{
	double sum=0;
	int lk=Locate[k];	
	int count=0;
	double r=drand();
	
	for(int i=0;i<n;i++)//計算總量
	{
		//if(Just[k][i]==1&&edge[lk][i]!=Infinite)
		if(Just[k][i]==1&&lk!=i)//未訪問且有路徑
		{
			sum=sum+pow(ph[lk][i],alfa)*pow(g[lk][i],beta);
			count++;
		}
	}	
	double x=0;
	double y=0;
	for(i=0;i<n;i++)
	{
		//if(Just[k][i]==1&&edge[lk][i]!=Infinite)
		if(Just[k][i]==1&&lk!=i)//判斷隨機時的路徑
		{		
			y=y+pow(ph[lk][i],alfa)*pow(g[lk][i],beta);		
			if(r>=x/sum &&r<y/sum)
				break;
			else
				x=y;
		}
	}
	return i;
}
void main()
{	
	int b=0;//記錄最佳螞蟻
	srand((unsigned)time(NULL));//設置隨機數種子
	double Lbest=100000000;
	double Lbest0=100000000;//此處只是一個無窮大的值
	/*初始化城市和路經*/
	IntiNode();
    IntiPh();
label:
	/*建立每只螞蟻的路徑存入tourk*/
	IntiAnt();
	for(int i=0;i<n;i++)
	{
		if(i<n-1)
		{
			for(int k=0;k<m;k++)
			{
				q=drand();
				//確定下一個城市sk			
				if(q<=q0)
				{			
					sk[k]=getsk(k);
				}
				else
				{			
					sk[k]=getSK(k);
				}
				Just[k][sk[k]]=0;
				Tour[k][i]=sk[k];			
				Len[k]=Len[k]+edge[Locate[k]][sk[k]];			
			}
		}
		else
		{
			for(int k=0;k<m;k++)
			{
				sk[k]=start[k];				
				Tour[k][i]=sk[k];
				Len[k]=Len[k]+edge[Locate[k]][sk[k]];			
			}
		}
		//利用公式5更新局部信息素
		for(int k=0;k<m;k++)
		{
			int x,y;
			x=Locate[k];
			y=sk[k];
			ph[x][y]=(1-row)*ph[x][y]+row*To;
			Locate[k]=sk[k];			
		}
	}
	//更新全局信息素
	for(int k=0;k<m;k++)
	{
		if(Lbest>=Len[k])
		{
			Lbest=Len[k];
			b=k;
		}
	}
	for(i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			if(edge[i][j]!=Infinite)
			{
				ph[i][j]=(1-row)*ph[i][j]+row/(double)Lbest;			
			}
		}
	
	if(Lbest0>Lbest)//判斷是否還可優化,  此處這樣處理如果下一次的比上一次的小則認為還可優化
	{
		Lbest0=Lbest;
		goto label;
	}
	if(Lbest<Infinite)
	{
		for(i=0;i<n;i++)
			printf("%d->",Tour[b][i]);
		printf("\n%f\n",Lbest);
	}
	else
	{
		printf("no solution\n");
	}
	
}