//用次序表示法来表示个体编码
#include<iostream>
#include<fstream>
#include<stdlib.h>
#include<time.h>
using namespace std;


struct individual{
    int DNA[25];
    int p;    //1-p为可以进行杂交的概率
};

int n;    //城市的数量
int dist[25][25];    //城市之间的距离
individual group[11];    //总群，保持总群数量在10以内
individual nextGroup[11];    //总群备份
int size;    //总群大小
int varyP=8;    //变异概率(总概率为10)
int season;
#define MAX 9999

void show(int season)
{    
    //打印总群
    cout<<"time"<<season<<":"<<endl;
    for(int i=1;i<=size;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<group[i].DNA[j]<<" ";
        }
        cout<<MAX-group[i].p<<endl;
    }
    cout<<endl;
}

//获取相关数据
void getInfo()
{
    ifstream input("input.txt");
    input>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            input>>dist[i][j];
        }
    }
}

//产生初始总群
void original()
{
    //用次序表示法来表示个体编码
    srand(unsigned(time(0)));
    for(int i=1;i<=size;i++)
    {
        group[i].DNA[1]=1;
        for(int j=2;j<=n;j++)
        {
            group[i].DNA[j]=rand()%(n-j+1)+1;    //根据定义，编码的第i位为1~n-j+1的数
        }
    }
}

//计算个体的适应度
int adaption(individual individual)
{
    //城市集合的顺序排列
    int *t=new int[n];
    for(int i=1;i<=n;i++)
    {
        t[i]=i;
    }

    //根据个体的编码计算巡游城市的顺序
    int *order=new int[n];
    for(int i=1;i<=n;i++)
    {
        //得到下一个要巡游的城市
        order[i]=t[individual.DNA[i]];
        //在t中将该城市删除
        for(int j=individual.DNA[i]+1;j<=n;j++)
        {
            t[j-1]=t[j];
        }
    }

    //根据巡游的顺序计算所需要的代价
    int cost=0;    //代价总数
    cost+=dist[1][order[1]];
    for(int i=1;i<n;i++)
    {
        cost+=dist[order[i]][order[i+1]];
    }
    cost+=dist[order[n]][1];

    return MAX-cost;
}

//杂交
void hybrid(int individual1,int individual2)
{
    //随机选择基因交换位置
    srand(unsigned(time(0)));
    int p=rand()%n+1;//只能在长度范围内进行交换
    int t;
    for(int i=p;i<=n;i++)
    {
        t=group[individual1].DNA[i];
        group[individual1].DNA[i]=group[individual2].DNA[i];
        group[individual2].DNA[i]=t;
    }
}

//变异
void vary(int individual)
{
    //随机选择一个基因变异位置
    srand(unsigned(time(0)));
    int p=rand()%(n-1)+2;//只能在长度范围内变异
    group[individual].DNA[p]=rand()%(n-p+1)+1;
}

//选择接下来进行杂交的个体
void choose()
{
    int total=0;    //代价总和
    for(int i=1;i<=n;i++)
    {
        total+=group[i].p;
    }

    //根据概率选择n个个体
    srand(unsigned(time(0)));
    for(int i=1;i<=n;i++)
    {
        for(int j=1,p=0,pointer=rand()%total+1;j<=n;j++)
        {
            p+=group[j].p;
            if(p>=pointer)
            {
                nextGroup[i]=group[j];
                break;
            }
        }
    }

    //将下一代总群作为当前总群
    for(int i=1;i<=n;i++)
    {
        group[i]=nextGroup[i];
    }
}

//美丽的大自然
void nature()
{
    srand(unsigned(time(0)));

    //输入种群大小
    cout<<"please input the size of the group:";
    cin>>size;
    //输入将进行的杂次数
    cout<<"input the time:";
    cin>>season;

    //获取大自然的信息
    getInfo();
    //初始化第一代
    original();



    for(int i=1;i<=season;i++)
    {//在时间限内发生的事
        show(i);
        for(int j=1;j<size;j++)
        {
            //第 j 个个体和第 j+1 个个体进行杂交
            hybrid(j,j+1);

            //有一定的几率个体会发生变异
            int p=rand()%10+1;
            if(p>=varyP) vary(j);

            //计算个体被选中的概率
            group[j].p=adaption(group[j]);

            //选择优良的个体
            choose();
        }
    }
    show(season);
}

void main()
{
    nature();
    system("pause");
}