#include "iostream.h"
#include "stdlib.h"
#include "stdio.h"
struct Edge
{
	int cost;
	int width;
	int delay;
    double inform;
} Net[9][9];

struct tEdge
{
	int cost;
	int delay;
    double inform;
	bool fupdate;
};
 
struct Node 
{
	int delay;
    double loss;
	int jitter;
}Point[9];	
//定義自我
void InitiateEdge( Edge  a[9][9])
{
	int i,j;
	for( i=0;i<9;i++)   
		for( j=0;j<9;j++)
		{
			a[i][j].cost=10000;
			a[i][j].delay=100;
			a[i][j].width=0;
			a[i][j].inform=100;
		}
	a[2][1].cost= a[1][2].cost=2;
	a[2][1].width= a[1][2].width=90;  //1
	a[2][1].delay=a[1][2].delay=3;

	a[3][1].cost=a[1][3].cost=3;
	a[3][1].width=a[1][3].width=80 ;//2
	a[3][1].delay=a[1][3].delay=3;

	a[5][1].cost=a[1][5].cost=1 ;
	a[5][1].width=a[1][5].width=100 ;//3
	a[5][1].delay=a[1][5].delay=4 ;

	a[3][2].cost=a[2][3].cost=4;
	a[3][2].width=a[2][3].width=20 ;//4
	a[3][2].delay=a[2][3].delay=3 ;

	a[4][2].cost=a[2][4].cost=3 ;
	a[4][2].width=a[2][4].width=80 ; //5
	a[4][2].delay=a[2][4].delay= 1;

	a[8][2].cost=a[2][8].cost=2 ;
	a[8][2].width=a[2][8].width=90 ;//6
	a[8][2].delay=a[2][8].delay=1 ;

	a[4][3].cost=a[3][4].cost=2;
	a[4][3].width=a[3][4].width=90 ;// 7
	a[4][3].delay=a[3][4].delay=1 ;

	a[5][3].cost=a[3][5].cost=2 ;
	a[5][3].width=a[3][5].width=90 ;//8
	a[5][3].delay=a[3][5].delay=1 ;

	a[6][4].cost=a[4][6].cost=3 ;
	a[6][4].width=a[4][6].width=80 ;//9
	a[6][4].delay=a[4][6].delay=1 ;

	a[6][5].cost=a[5][6].cost=1 ;
	a[6][5].width=a[5][6].width=110;//10
	a[6][5].delay=a[5][6].delay=3;

	a[7][6].cost=a[6][7].cost=1 ;
	a[7][6].width=a[6][7].width=100 ;//11
	a[7][6].delay=a[6][7].delay=3 ;

	a[8][7].cost=a[7][8].cost=2 ;
	a[8][7].width=a[7][8].width=90;//12
	a[8][7].delay=a[7][8].delay=4;
} //定義自我

//定義自我
void InitiateEdge(Node b[])
{
	b[1].delay=1;
	b[1].loss=0.00001;
	b[1].jitter=2;

	b[2].delay=1;
	b[2].loss=0.000001;
	b[2].jitter=1;

	b[3].delay=1;
	b[3].loss=0.01;
	b[3].jitter=1;

	b[4].delay=1;
	b[4].loss=0.00001;
	b[4].jitter=0;


	b[5].delay=1;
	b[5].loss=0.000001;
	b[5].jitter=1;

	b[6].delay=1;
	b[6].loss=0;
	b[6].jitter=2;

	b[7].delay=1;
	b[7].loss=0.00001;
	b[7].jitter=1;


	b[8].delay=1;
	b[8].loss=0.000001;
	b[8].jitter=0;
}//定義自我

//產(chǎn)生下一跳
bool CreatNext(int pr,int& next,int flag[9],tEdge a[9][9])
{
	int n,inform,page;
	double random,trand;
	double tinform=0.0;
	for(n=1;n<9;n++)
		if(!flag[n])
			tinform+=a[pr][n].inform;
    if(tinform==0.0)
		return false;
    page=1;
	while(tinform<100)
	{
		tinform*=10;
		page*=10;
	}

	inform=int(tinform);
	trand=double(rand()%inform);
	random=trand/page;
	
    for( n=1;n<9;n++)  
	{
		if(!flag[n])
			if(random<a[pr][n].inform)
			{
				next=n;flag[n]=1;break;
			}
			 else
				 random-=a[pr][n].inform;
	 }
	return true;
}//產(chǎn)生下一跳

//調(diào)整信息素
void ChangeInformation(tEdge aa[9][9],int c[],double cons,double a)
{
	int i,m,n;
	for(i=1;c[i+1];i++)
	{
		m=c[i],n=c[i+1];
		if(!n)
			break;
		else
		aa[m][n].fupdate=true;
	}

	for(m=1;m<9;m++)  
		for(n=1;n<9;n++)
			if(aa[m][n].inform!=0)
				if(aa[m][n].fupdate)
				{
					aa[m][n].inform=aa[m][n].inform=(1-a)*aa[m][n].inform+a*cons;
				    aa[m][n].fupdate=false;
				}
				else
					aa[m][n].inform=aa[m][n].inform=(1-a)*aa[m][n].inform+0.05*a*cons;
}//調(diào)整信息素


//判斷當(dāng)前路徑是否比以前的好
void JudgeSuperexcellence(int& mincost,int& mindelay,
						  double& minloss,int delay,double loss,
						  int& tcost,int& tdelay,double& tloss,int tant[],
						  bool& froad,int exceroad[],int& execstep,int step,bool& fexec )
{
	int i,j,m;
	double ttloss;
    tdelay=0;tcost=0;ttloss=1.0;
	for(int k=1;tant[k+1]!=0;k++)
	{
		i=tant[k];j=tant[k+1];
		tdelay+=Net[i][j].delay;
		tcost+=Net[i][j].cost;
		tdelay+=Point[j].delay;
		ttloss=ttloss*(1-Point[j].loss);
	}
	if(k>2)
	{
		tdelay-=Point[j].delay;
		ttloss=ttloss/(1-Point[j].loss);
	}
	 if(k<3)
		 tloss=0.0;
	 else tloss=1-ttloss;

	 if((mincost>tcost && tdelay<=delay && tloss<=loss)|| (mincost==tcost && tdelay<mindelay && tloss<=loss))
	 {
		 mincost=tcost;
		 mindelay=tdelay;
		 minloss=tloss;
		 int m=1;
		 if(!froad)
		 {
			 froad=true;
			 cout<<"step    road                   cost    delay      loss         "<<endl;
		 }	
		 for(m=0;m<10;m++)
			 exceroad[m]=0;
		 execstep=step;fexec=true;
		 m=1;
		 cout<<step<<'\t';
		 while(tant[m])
		 {
			 exceroad[m]=tant[m];
			 cout<<tant[m++]<<"  ";
		 }
		 while(m++<9)
			 cout<<"   ";   
		 cout<<mincost<<"     "<<'\t'<<mindelay<<"    "<<'\t'<<tloss<<"     "<<endl;
		 
	 }
	 else if(tdelay<=delay && tloss<=loss)
	 {
		 if(!froad)
		 {
			 froad=true;
			 cout<<"step   road                   cost    delay      loss         "<<endl;
		 }	

		 m=1;
		 cout<<step<<'\t';
		 while(tant[m])
			 cout<<tant[m++]<<"  ";
		 while(m++<9)
			 cout<<"   ";   
		 cout<<tcost<<"    "<<'\t'<<tdelay<<"     "<<'\t'<<tloss<<"     "<<endl;
		 
	 }
}//判斷當(dāng)前路徑是否比以前的好

//傳遞原始矩陣
void  Deliver(struct tEdge t[9][9],int width)
{
	int i,j;
	for(i=0;i<9;i++)  
		for(j=0;j<9;j++)
		{
			t[i][j].cost=Net[i][j].cost;
			t[i][j].delay=Net[i][j].delay;
			t[i][j].fupdate=false;
			if(width<Net[i][j].width)
				t[i][j].inform=Net[i][j].inform;
			else 
				t[i][j].inform=0;
		}
}//傳遞原始矩陣

//主函數(shù)
void  main()
{                                               //1
	int j,m,tstep,next,pr,g;	
	int from,aim,width,delay;
    int mincost,mindelay,step,stepin,tcost,tdelay;
	int flag[10],exceroad[10],execstep;
	int tant[10];                 //
    double a0=0.069,a1=0.079,cons=0.32,tloss,loss,minloss;
	bool froad,finitiate,fexec;
	struct tEdge t[9][9];
    char  request;
    InitiateEdge(Net);//定義自我
    InitiateEdge(Point);//定義自我
    request='y';
	
	while(request=='y'||request=='Y')
	{
		cout<<endl<<"請輸入要求解的路由的有關(guān)信息:";
		cout<<endl<<"源節(jié)點(diǎn):";  	cin>>from;
		cout<<endl<<"目的節(jié)點(diǎn):";	cin>>aim;
		cout<<endl<<"所需帶寬:";	cin>>width;
		cout<<endl<<"最大時(shí)延:";	cin>>delay;
		cout<<endl<<"最大丟失率:";  cin>>loss;
		cout<<endl<<"允許迭代次數(shù):"; cin>>stepin;
        mincost=mindelay=100;execstep=step=0;froad=false;minloss=1.0;finitiate=fexec=false;
     	srand(7);//4
		Deliver(t,width);//濾掉一些無效的自我
		if(t[from][aim].inform>50)//分辨自我與非自我
		{
			if(t[from][aim].delay<=delay)
			{
				mincost=t[from][aim].cost;
				mindelay=t[from][aim].delay;
				execstep=0;finitiate=true;
				minloss=0;
			}
		}

		while(step++<stepin)                           //while step
		{
			for(g=0;g<10;g++)
                tant[g]=flag[g]=0;  //
			pr=from;next=0;j=1; tant[j]=from;  //  
			tstep=1;flag[from]=1;  
			while(next!=aim  && j++<9)
			{
				if(CreatNext( pr, next, flag,t))//產(chǎn)生下一跳
				{
					pr=next;tstep++;
					tant[tstep]=next;//
				}
				else break;
			}
			if(next==aim)
			{
				ChangeInformation(t,tant,cons,a0);//調(diào)整信息素
                JudgeSuperexcellence( mincost,mindelay,minloss,delay,
					loss,tcost,tdelay,tloss,tant,froad,
					exceroad,execstep,step,fexec );//判斷當(dāng)前路徑是否比以前的好
			}

		}    //while step
		if(finitiate)
			cout<<"網(wǎng)絡(luò)存在直接通路:    road:  "<<from<<"  "<<aim<<"    cost: "<<mincost<<"   delay: "<<mindelay<<"   loss: "<<minloss<<endl;
		else if(fexec)
		{
			cout<<"最優(yōu)路徑為:"<<endl<<"step:"<<execstep<<"   road: ";
			m=1;
			while(exceroad[m])
				cout<<exceroad[m++]<<"   ";
			cout<<"    cost: "<<mincost<<"   delay: "<<mindelay<<"   loss: "<<minloss<<endl;
		}
		else
			cout<<"很遺憾，沒有找到合適的路徑！"<<endl;

		cout<<"如果還有路由請求，請按 y，否則請 n,y/n:";
		cin>>request;
	}   
}//1//