#include<iostream>
#include<ctime>
#include<stdlib.h>
#include<math.h>
using namespace std;
#define N  30  //種群數(shù)目
#define NUM 100 //城市數(shù)目
#define CRS 0.898
#define CHG 0.9
#define RE  0.9
typedef struct AX//一個(gè)染色體
{
	int road[NUM];
	AX(){
		for(int i=0;i<NUM;i++)
			road[i]=i;
	}
}Mem;
typedef struct 
{
	int x;
	int y;
}Point;
int find_pos(Mem m,int x)
{
	for(int i=0;i<NUM;i++)
		if(m.road[i]==x)
			return i;
	return -1;
}
int s(Point a,Point b)
{
	return sqrt(float((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}
void tran(Mem &t,Mem& s)
{
	for(int i=0;i<NUM;i++)
		t.road[i]=s.road[i];
}

class Gcalc
{
public:
	Mem m[N];//染色體個(gè)數(shù);
	Point pos[NUM];
public :
	Gcalc(){
		srand(time(NULL));
		init_m();
		init_pos(950,670,10,10);
	}
	Gcalc(int cx,int cy,int x0=10,int y0=10)
	{
		srand(time(NULL));
		init_pos(cx,cy,x0,y0);
		init_m();
	}
	void init_m(void)
	{
		for(int i=0;i<N;i++)
		{
			//srand(i*5);
			for(int j=0;j<NUM;j++)
				m[i].road[j]=j;
			for(int k=0;k<NUM;k++)//對(duì)各點(diǎn)進(jìn)行輪動(dòng)運(yùn)算
			{	
				int a=rand()%(NUM*100)/100;
				//while (a==k) a=rand()%NUM;
				//if(rand()%2==0)
				int r=m[i].road[k];
				m[i].road[k]=m[i].road[a];
				m[i].road[a]=r;
			}
		}
	}
	void init_pos(int cx,int cy,int x0=0,int y0=0)
	{
		for(int i=0;i<NUM;i++)
		{
			pos[i].x=rand()%cx+x0;
			pos[i].y=rand()%cy+y0;
		}
	}
	void cross() //交叉
	{
		
		for(int i=0;i<N/2;i++)
		{
			Mem *p=new Mem,*q=new Mem;
			int u=rand()%N,v=rand()%N;
			while(u==v) u=rand()%N;
			tran(*p,m[u]);
			tran(*q,m[v]);
			if(float(rand()%1000)/1000<=CRS)
			{
				int a=rand()%NUM;
				int x=m[u].road[a];
				int y=m[v].road[a];	
				m[u].road[find_pos(m[u],y)]=x;
				m[u].road[a]=y;
				m[v].road[find_pos(m[v],x)]=y;
				m[v].road[a]=x;
			}
			if(f(*p)<f(m[u]))
				tran(m[u],*p);
			if(f(*q)<f(m[v]))
				tran(m[v],*q);
			delete p;
			delete q;
		}
	}
	void change()//變異
	{
		for(int i=0;i<N;i++)
		{
			if(float(rand()%100)/100<=CHG)
			{
				Mem* p=new Mem;
				tran(*p,m[i]);
				int a=rand()%NUM;
				int b=rand()%NUM;
				while(a==b)
					b=rand()%NUM;
				int r=m[i].road[a];
				m[i].road[a]=m[i].road[b];
				m[i].road[b]=r;
				if(f(*p)<f(m[i]))
					tran(m[i],*p);
				delete p;
			}
		}
	}
	void ret()
	{
		for(int i=0;i<N;i++)
		{
			if(float(rand()%1000)/1000<=RE)
			{
				Mem* p=new Mem;
				tran(*p,m[i]);
				int r;
				int a=rand()%NUM;
				int b=rand()%NUM;
				while(a==b)
					b=rand()%NUM;
				r=a>b?a:b;//取其最大
				if(r!=b)
				{
					a=b;
					b=r;
				}
				for(int j=a;j<=(b-a)/2+a;j++)//倒序
				{
					r=m[i].road[j];
					m[i].road[j]=m[i].road[b+a-j];
					m[i].road[b+a-j]=r;
				}
				if(f(*p)<f(m[i]))
					tran(m[i],*p);
				delete p;
			}
		}
	}
	int f(Mem m)//計(jì)算路徑長(zhǎng)度
	{
		int r=0;
		for(int i=0;i<NUM;i+=1)
			r+=s(pos[m.road[i]],pos[m.road[(i+1)%NUM]]);
		return r;
	}
	float af(Mem m)
	{
		float r=f(m);
		return 10/(r/100);
	}
	void next()//進(jìn)行繁殖
	{
		Mem m0[N];
		int i;
		float fme[N],fm=0;
		for(i=0;i<N;i++)
			fm+=fme[i]=af(m[i]);
		for(i=1;i<N;i++)
			fme[i]=fme[i]/fm+fme[i-1]/fm;
		for(i=0;i<N;i++)
		{
			float t=double(rand()%10000)/10000;
			for(int j=0;t<=fme[j]&&(j==0||fme[j]>fme[j-1])&&j<NUM;j++)//輪盤(pán)得碼
				tran(m0[i],m[j]);
		}
		for(i=0;i<N;i++)
			tran(m[i],m0[i]);
	}
	void calc(int n=1)
	{
		for(int i=0;i<n;i++)
		{
			cross();
			change();
			ret();
			//next();
		}
	}
	void display()
	{
		int min=f(m[0]),max=min;
		for(int i=0;i<N;i++)
		{
			int r=f(m[i]);
			//printf("%d  : %d \n",i,r);
			if(min>r)
				min=r;
			if(max<r)
				max=r;
		}
		cout<<"MIN:"<<min<<" MAX:"<<max<<endl;
	}
	void display(int x)
	{
		for(int i=0;i<NUM;i++)
			cout<<i<<"  : "<<m[x].road[i]<<endl;
		cout<<endl;
	}
	void out()
	{
		for(int i=0;i<NUM;i++)
		{
			cout<<i<<":"<<pos[i].x<<" "<<pos[i].y<<endl;
		}
	}
	
};