#include<iostream>
#include<ctime>
#include<stdlib.h>
#include<math.h>
using namespace std;
#define N  10  //種群數目
#define NUM 50 //城市數目
#define CRS 0.898
#define CHG 0.9
#define RE  0.9
typedef struct P
{
	int x;
	int y;
	P():x(0),y(0){}
}Point;

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)));
}
class Gcalc
{
public:
	int n;
	int num;
	float crs,re,chg;
	typedef struct AX//一個染色體
	{
		int *road;
		AX()
		{
			road=NULL;
		}
		AX(int nu){
			road=new int[nu];
			for(int i=0;i<nu;i++)
				road[i]=i;
		}
		AX operator =(AX& mx)
		{
			road=mx.road;
			return mx;
		}
		//~AX(){delete []road;}
	}Mem;
	Mem *m;//染色體數組;
	Point *pos;
public :
	void Mmalloc(Mem*& mx,int n0,int num0)
	{
		mx=new Mem[n0];
		for(int i=0;i<n0;i++)
			mx[i]=*(new Mem(num0));
	}
	/*~Gcalc()
	{
		delete  []m;
		delete  []pos;
	}
	*/
	Gcalc(int n0=N,int num0=NUM,float crs0=CRS,float re0=RE,float chg0=CHG)
		:n(n0),num(num0),crs(crs0),re(re0),chg(chg0)
	{
		srand(time(NULL));
		Mmalloc(m,n,num);
		pos=new Point[num];
		init_m();
		init_pos(950,670,10,10);
	}
	Gcalc(int cx,int cy,int x0=10,int y0=10,int n0=N,int num0=NUM,float crs0=CRS,float re0=RE,float chg0=CHG)
		:n(n0),num(num0),crs(crs0),re(re0),chg(chg0)
	{
		srand(time(NULL));
		Mmalloc(m,n,num);
		pos=new Point[num];
		init_pos(cx,cy,x0,y0);
		init_m();
	}
	void reset(int cx,int cy,int x0=10,int y0=10,int n0=N,int num0=NUM,float crs0=CRS,float re0=RE,float chg0=CHG)
	{
		n=n0,num=num0,crs=crs0,re=re0,chg=chg0;
		Mem *ptr=m;
		Mmalloc(m,n,num);
	/*	pos=new Point[num];
		if(ptr!=NULL)
			delete []ptr;
		Point *po=pos;
		if(po!=NULL)
		{
			delete []po;
		}
		*/
		init_pos(cx,cy,x0,y0);
		init_m();
	}
	int find_pos(Mem m,int x)
	{
		for(int i=0;i<num;i++)
			if(m.road[i]==x)
				return i;
		return -1;
	}
	void tran(Mem &t,Mem& s)
	{
		int *ptr=t.road;
		t.road=new int[num];
		delete []ptr;
		for(int i=0;i<num;i++)
			t.road[i]=s.road[i];
	}

	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++)//對各點進行輪動運算
			{	
				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)//計算路徑長度
	{
		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()//進行繁殖
	{
		Mem *m0;
		Mmalloc(m0,n,num);
		int i;
		float *fme=new float[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++)//輪盤得碼
				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;
		}
	}
	
};