八数码问题

（一）问题描述

在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题或者重排九宫问题。

（二）问题分析

八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。

1、启发式搜索

由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。

由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息就可以指导搜索。即可以利用启发信息来扩展节点的选择，减少搜索范围，提高搜索速度。

  启发函数设定。对于八数码问题，可以利用棋局差距作为一个度量。搜索过程中，差距会逐渐减少，最终为零，为零即搜索完成，得到目标棋局。

（三）数据结构与算法设计

该搜索为一个搜索树。为了简化问题，搜索树节点设计如下：

struct Chess//棋盘

{

       int cell[N][N];//数码数组

       int Value;//评估值

       Direction BelockDirec;//所屏蔽方向

       struct Chess * Parent;//父节点

};

int cell[N][N];    数码数组：记录棋局数码摆放状态。

int Value;        评估值：记录与目标棋局差距的度量值。

Direction BelockDirec; 所屏蔽方向：一个屏蔽方向，防止回推。

Direction ：enum Direction{None,Up,Down,Left,Right};//方向枚举

struct Chess * Parent;  父节点：指向父亲节点。

下一步可以通过启发搜索算法构造搜索树。

1、局部搜索树样例：

2、搜索过程

  搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）。搜索过程如下：

  （1）、把原棋盘压入队列；

  （2）、从棋盘取出一个节点；

  （3）、判断棋盘估价值，为零则表示搜索完成，退出搜索；

  （4）、扩展子节点，即从上下左右四个方向移动棋盘，生成相应子棋盘；

（5）、对子节点作评估，是否为优越节点（子节点估价值小于或等于父节点则为优越节点），是则把子棋盘压入队列，否则抛弃；

  （5）、跳到步骤（2）；

3、算法的评价

完全能解决简单的八数码问题，但对于复杂的八数码问题还是无能为力。现存在的一些优缺点。

1、可以改变数码规模（N），来扩展成N*N的棋盘，即扩展为N数码问题的求解过程。

2、  内存泄漏。由于采用倒链表的搜索树结构，简化了数据结构，但有部分被抛弃节点的内存没有很好的处理，所以会造成内存泄漏；

3、  采用了屏蔽方向，有效防止往回搜索（节点的回推），但没能有效防止循环搜索，所以不能应用于复杂度较大的八数码问题；

源码：
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "string.h"
#include
#include
using namespace std;

const int N=3;//3*3棋盘
const int Max_Step=30;//最大搜索深度

enum Direction{None,Up,Down,Left,Right};//方向
struct Chess//棋盘
{
    int cell[N][N];//数码数组
    int Value;//评估值
    Direction BelockDirec;//所屏蔽方向
    struct Chess * Parent;//父节点
};

//打印棋盘
void PrintChess(struct Chess *TheChess)
{
    printf("------------------------------------------------------------------------\n");
    for(int i=0;i     {
        printf("\t");
        for(int j=0;j         {
            printf("%d\t",TheChess-＞cell[i][j]);
        }
        printf("\n");
    }
    printf("\t\t\t\t差距:%d\n",TheChess-＞Value);
}
//移动棋盘
struct Chess * MoveChess(struct Chess * TheChess,Direction Direct,bool CreateNewChess)
{
    struct Chess * NewChess;

    //获取空闲格位置
    int i,j;
    for(i=0;i     {
        bool HasGetBlankCell=false;
        for(j=0;j         {
            if(TheChess-＞cell[i][j]==0)
            {
                HasGetBlankCell=true;
                break;
            }
        }
        if(HasGetBlankCell)
            break;
    }

    //移动数字
    int t_i=i,t_j=j;
    bool AbleMove=true;
    switch(Direct)
    {
    case Up:
        t_i++;
        if(t_i＞=N)
            AbleMove=false;
        break;
    case Down:
        t_i--;
        if(t_i＜0)
            AbleMove=false;
        break;
    case Left:
        t_j++;
        if(t_j＞=N)
            AbleMove=false;
        break;
    case Right:
        t_j--;
        if(t_j＜0)
            AbleMove=false;
        break;
    };
    if(!AbleMove)//不可以移动则返回原节点
    {
        return TheChess;
    }

    if(CreateNewChess)
    {
        NewChess=new Chess();
        for(int x=0;x         {
            for(int y=0;y                 NewChess-＞cell[x][y]=TheChess-＞cell[x][y];
        }
    }
    else
        NewChess=TheChess;
    NewChess-＞cell[i][j]=NewChess-＞cell[t_i][t_j];
    NewChess-＞cell[t_i][t_j]=0;

    return NewChess;
}

//初始化一个初始棋盘
struct Chess * RandomChess(const struct Chess * TheChess)
{
    int M=30;//随机移动棋盘步数
    struct Chess * NewChess;
    NewChess=new Chess();
    memcpy(NewChess,TheChess,sizeof(Chess));
    srand((unsigned)time(NULL));
    for(int i=0;i     {   
        int Direct=rand()%4;
        //printf("%d\n",Direct);
        NewChess=MoveChess(NewChess,(Direction) Direct,false);
    }
    return NewChess;
}

//估价函数
int Appraisal(struct Chess * TheChess,struct Chess * Target)
{
    int Value=0;
    for(int i=0;i     {
        for(int j=0;j         {
            if(TheChess-＞cell[i][j]!=Target-＞cell[i][j])
                Value++;
        }
    }
    TheChess-＞Value=Value;
    return Value;
}

//搜索函数
struct Chess * Search(struct Chess* Begin,struct Chess * Target)
{
    Chess * p1,*p2,*p;
    int Step=0;//深度
    p=NULL;
    queue Queue1;
    Queue1.push(Begin);
    //搜索
    do{
        p1=(struct Chess *)Queue1.front();
        Queue1.pop();
        for(int i=1;i＜=4;i++)//分别从四个方向推导出新子节点
        {
            Direction Direct=(Direction)i;
            if(Direct==p1-＞BelockDirec)//跳过屏蔽方向
                continue;
       
            p2=MoveChess(p1,Direct,true);//移动数码
            if(p2!=p1)//数码是否可以移动
            {
                Appraisal(p2,Target);//对新节点估价
                if(p2-＞Value＜=p1-＞Value)//是否为优越节点
                {
                    p2-＞Parent=p1;
                    switch(Direct)//设置屏蔽方向,防止往回推
                    {
                    case Up:p2-＞BelockDirec=Down;break;
                    case Down:p2-＞BelockDirec=Up;break;
                    case Left:p2-＞BelockDirec=Right;break;
                    case Right:p2-＞BelockDirec=Left;break;
                    }
                    Queue1.push(p2);//存储节点到待处理队列
                    if(p2-＞Value==0)//为0则,搜索完成
                    {
                        p=p2;
                        i=5;
                    }
                }
                else
                {
                    delete p2;//为劣质节点则抛弃
                    p2=NULL;
                }
            }
        }
        Step++;
        if(Step＞Max_Step)
            return NULL;
    }while(p==NULL || Queue1.size()＜=0);

    return p;
}

main()
{
    Chess * Begin,Target,* T;
    //设定目标棋盘 [0 1 2],[3 4 5],[6 7 8]
    for(int i=0;i     {
        for(int j=0;j         {
            Target.cell[i][j]=i*N+j;
        }
    }
    //获取初始棋盘
    Begin=RandomChess(&Target);
    Appraisal(Begin,&Target);
    Begin-＞Parent=NULL;
    Begin-＞BelockDirec=None;
    Target.Value=0;
    printf("目标棋盘:\n");
    PrintChess(&Target);
    printf("初始棋盘:\n");
    PrintChess(Begin);
    //图搜索
    T=Search(Begin,&Target);
    //打印
    if(T)
    {
        /*把路径倒序*/
        Chess *p=T;
        stackStack1;
        while(p-＞Parent!=NULL)
        {
            Stack1.push(p);
            p=p-＞Parent;
        }
        printf("搜索结果:\n");
        while(!Stack1.empty())
        {
            PrintChess(Stack1.top());
            Stack1.pop();
        }
        printf("\n完成!");
    }else
        printf("搜索不到结果.深度为%d\n",Max_Step);

    scanf("%d",T);
}

八皇后问题

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

基本思想：在open表中保留已生成而未考察的结点，并用启发函数h(x)对它们全部进行估价，从中选出最优结点进行扩展，而不管这个结点出现在搜索树的什么地方。

（1）把初始结点S0放入open表中，计算h(S0);

（2）若open表为空，则搜索失败，EXIT；

（3）移出open表中第一个结点N放入closed表中,并冠以序号n

（4）若目标结点Sg=N则搜索成功，EXIT

（5）若N不可扩展，则转步骤（2）；

（6）扩展N，计算每个子结点x的函数值h(x)，并将所有子结点配以指向N的返回指针后放入open表中，再对open表中的所有子结点按其函数值大小以升序排序，转步骤2；

//采用启发式修补解N皇后问题

#include

#include

//采用启发式修补解N皇后问题

#include

#include

using ...namespace std;

void shuffle(int Queen[],const int n)

...{//随机取得各行的初始皇后位置，以Queen[i]表示第i行的皇后位置

    for(int i=0;i

  Queen[i]=abs(rand())%n;

}

int collision(int Queen[],const int row,const int column,const int n)

...{  //计算每个位置的冲突值

    int bug=0;

    for(int i=0;i

    ...{

  if ((i!=row)&&(Queen[i]==column||(Queen[i]-column)==(i-row)

      ||(Queen[i]-column)==(row-i)))//同列，同对角线的情况

            bug ;

    }

    return bug;

}

void show(int Queen[],const int n)

...{//打印皇后图

    cout＜＜"╭";

    for(int k=0;k

  cout＜＜"─┬";

    cout＜＜"─╮"＜

    for(int i=0;i

    ...{ 

  cout＜＜"│";

   for(int j=0;j

       cout＜＜((j==Queen[i])? "凤" :"  ")＜＜"│";//有皇后的位置用"凤"

       cout＜

    cout＜＜"├";

   for(j=0;j

       cout＜＜"─┼";

    cout＜＜"─┤"＜

  }

   cout＜＜"│";

   for(int j=0;j

       cout＜＜((j==Queen[n-1])? "凤" :"  ")＜＜"│";//有皇后的位置用，没有的用_

       cout＜

    cout＜＜"╰";

    for(k=0;k

  cout＜＜"─┴";

    cout＜＜"─╯"＜

 cout＜

}

int repair(int Queen[],const int n)

...{ //启发式修补  

    int max=-1;//标志行行之间冲突数

    int minbug=n;

    int count=0;

    while(max!=0&&count＜=100)

    ...{   

  max=0;

  for(int i=0;i

  ...{   

      minbug=collision(Queen,i,Queen[i],n);//取得当前的冲突数，不断优化

      int temp=Queen[i];

      for(int j=0;j

      ...{

    int bug=collision(Queen,i,j,n);

    if(bug＜=minbug&&j!=temp)

    ...{ //保持皇后在等冲突的情况下不断变更位置，有利于后面行的优化

      minbug=bug;

      Queen[i]=j;

    }

      }

      if (minbug＞max)

    max=minbug;

  }

  show(Queen,n);

  count ;

    }

    return count;

}

void main()

...{                 

    int n=-1;

    int step=0;

    cout＜＜"Welcome to N Queen Settlement"＜

    cout＜＜"Input N (you would better input a interge minor to 15):"＜

    cin＞＞n;

    if(n＜=0)

    ...{

  cout＜＜"Illegal Input!"＜

        return;

    }

    int* Queen=new int[n];

    srand(time(NULL));//取得随机种子

    shuffle(Queen,n);

    cout＜＜"The oringinal state:"＜

    show(Queen,n);

    step=repair(Queen,n);

    if(step＞100)

    ...{

  cout＜＜"Could find solution within 100 steps,Try again!"＜

     return;

    }

    cout＜＜"After "＜

    cout＜＜"The goal state arrives!"＜

}

汉诺塔问题

遗传算法求TSP问题

　　遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。

遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

遗传算法特点

　　遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点：

　　1、 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际值本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子。

　　2、 遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。

　　3、 遗传算法使用多个点的搜索信息，具有隐含并行性。

　　4、 遗传算法使用概率搜索技术，而非确定性规则。

/***********************************************************************
　　*遗传算法解决TSP问题 *
　　*code by 小白 at July.30 *
　　***********************************************************************/
　　def.h
　　－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
　　#ifndef _GENERATION_AMOUNT
　　#define _GENERATION_AMOUNT 201 //每一代的生存数
　　#define _CITY_AMOUNT 10 //城市数,等于基因数
　　//#define _XCHG_GENE_AMOUNT_WHEN_MIX 2 //每次杂交所交换的碱基数量
　　#define _TIMES 50 //定义进化次数
　　#define _DISP_INTERVAL 5 //每隔多少次显示基因中的最高适应度
　　#define _CONTAINER std::vector //定义个体基因容器类型
　　#define _CONTAINER_P std::vector //定义适应度容器类型
　　#define _P(a,x,y) *(a+(x)+(y)*_CITY_AMOUNT)
　　#define _P_GENE_ABERRANCE 10 //变异概率1%
　　#define _P_GENE_MIX (_GENERATION_AMOUNT-1)/2 //杂交次数
　　#define _INFINITE 100000
　　typedef int DISTANCE; //距离矩阵的数据存储类型
　　#endif
　　___________________________________________________________________________
　　TSP.cpp
　　____________________________________________________________________________
　　#include
　　#include
　　#include
　　#include
　　#include
　　#include "def.h"
　　#include "TSP.h"
　　void main()
　　{
　　
　　 const static DISTANCE distance[][_CITY_AMOUNT]
　　 = {
　　 0, 1, 4, 6, 8, 1, 3, 7, 2, 9,
　　 1, 0, 7, 5, 3, 8, 3, 4, 2, 4,
　　 4, 7, 0, 3, 8, 3, 7, 9, 1, 2,
　　 6, 5, 3, 0, 3, 1, 5, 2, 9, 1,
　　 8, 3, 8, 3, 0, 2, 3, 1, 4, 6,
　　 1, 8, 3, 1, 2, 0, 3, 3, 9, 5,
　　 3, 3, 7, 5, 3, 3, 0, 7, 5, 9,
　　 7, 4, 9, 2, 1, 3, 7, 0, 1, 3,
　　 2, 2, 1, 9, 4, 9, 5, 1, 0, 1,
　　 9, 4, 2, 1, 6, 5, 9, 3, 1, 0
　　 }; //城市间的距离矩阵
　　 //distance[i][j]代表i城市与j城市的距离
　　 /*
　　 const static DISTANCE distance[][_CITY_AMOUNT]
　　 ={
　　 0, 1, 4, 6, 8, 1, 3, 7, 2, 9, 7, 3, 4, 5, 8, 9, 2, 8, 2, 8,
　　 1, 0, 7, 5, 3, 8, 3, 4, 2, 4, 4, 6, 2, 8, 2, 9, 4, 5, 2, 1,
　　 4, 7, 0, 3, 8, 3, 7, 9, 1, 2, 5, 8, 1, 8, 9, 4, 7, 4, 8, 4,
　　 6, 5, 3, 0, 3, 1, 5, 2, 9, 1, 3, 5, 7, 3, 4, 7, 3, 4, 5, 2,
　　 8, 3, 8, 3, 0, 2, 3, 1, 4, 6, 3, 8, 4, 5, 2, 8, 1, 7, 4, 7,
　　 1, 8, 3, 1, 2, 0, 3, 3, 9, 5, 4, 5, 2, 7, 3, 6, 2, 3, 7, 1,
　　 3, 3, 7, 5, 3, 3, 0, 7, 5, 9, 3, 4, 5, 9, 3, 7, 3, 2, 8, 1,
　　 7, 4, 9, 2, 1, 3, 7, 0, 1, 3, 4, 5, 2, 7, 6, 3, 3, 8, 3, 5,
　　 2, 2, 1, 9, 4, 9, 5, 1, 0, 1, 3, 4, 7, 3, 7, 5, 9, 2, 1, 7,
　　 9, 4, 2, 1, 6, 5, 9, 3, 1, 0, 3, 7, 3, 7, 4, 9, 3, 5, 2, 5,
　　 7, 4, 5, 3, 3, 4, 3, 4, 3, 3, 0, 5, 7, 8, 4, 3, 1, 5, 9, 3,
　　 3, 6, 8, 5, 8, 5, 4, 5, 4, 7, 5, 0, 8, 3, 1, 5, 8, 5, 8, 3,
　　 4, 2, 1, 7, 4, 2, 5, 2, 7, 3, 7, 8, 0, 5, 7, 4, 8, 3, 5, 3,
　　 5, 8, 8, 3, 5, 7, 9, 7, 3, 7, 8, 3, 5, 0, 8, 3, 1, 8, 4, 5,
　　 8, 2, 9, 4, 2, 3, 3, 6, 7, 4, 4, 1, 7, 8, 0, 4, 2, 1, 8, 4,
　　 9, 9, 4, 7, 8, 6, 7, 3, 5, 9, 3, 5, 4, 3, 4, 0, 4, 1, 8, 4,
　　 2, 4, 7, 3, 1, 2, 3, 3, 9, 3, 1, 8, 8, 1, 2, 4, 0, 4, 3, 7,
　　 8, 5, 4, 4, 7, 3, 2, 8, 2, 5, 5, 5, 3, 8, 1, 1, 4, 0, 2, 6,
　　 2, 2, 8, 5, 4, 7, 8, 3, 1, 2, 9, 8, 5, 4, 8, 8, 3, 2, 0, 4,
　　 8, 1, 4, 2, 7, 1, 1, 5, 7, 5, 3, 3, 3, 5, 4, 4, 7, 6, 4, 0
　　 };
　　*/
　　 Csga＜_CONTAINER, _CONTAINER_P＞ CUnit((DISTANCE *)distance); //初始化
　　
　　 //开始遗传算法
　　 if(!CUnit.fnCreateRandomGene()) //产生随机的基因
　　 {
　　 exit(0);
　　 }
　　
　　 //循环基因编译,杂交,淘汰过程
　　 CUnit.fnEvalAll();
　　 for ( int i = 0; i ＜ _TIMES; ++i )
　　 {
　　 //CUnit.fnDispProbability();
　　 CUnit.fnGeneAberrance(); //基因变异
　　 //CUnit.fnDispProbability();
　　 CUnit.fnGeneMix(); //基因杂交
　　
　　 CUnit.fnEvalAll();
　　
　　 //每隔_DISP_INTERVAL显示一次结果
　　 if ( (i+1)%_DISP_INTERVAL == 0 || i == 0)
　　 {
　　 cout ＜＜ "第" ＜＜ i+1 ＜＜ "代" ＜＜ std::endl;
　　 CUnit.fnDispProbability();
　　 CUnit.fnDispHistoryMin();
　　 }
　　
　　 }
　　 CUnit.fnDispHistoryMin();
　　
　　
　　}
　　___________________________________________________________________________
　　tsp.h
　　___________________________________________________________________________
　　#include "def.h"
　　using namespace std;
　　template
　　class Csga
　　{
　　
　　public:
　　 Csga();
　　 Csga(DISTANCE *lpDistance); //构造函数
　　 ~Csga(); //析构函数
　　
　　 bool fnCreateRandomGene(); //产生随机基因
　　 bool fnGeneAberrance(); //基因变异
　　 bool fnGeneMix(); //基因交叉产生新的个体测试并淘汰适应度低的个体
　　
　　 bool fnEvalAll(); //测试所有基因的适应度
　　 int fnEvalOne(T &Gene); //测试某一个基因的适应度
　　 void fnDispProbability(); //显示每个个体的权值
　　 void fnDispHistoryMin();
　　
　　private:
　　 bool fnGeneAberranceOne(const int &i, const int &j);//变异某个基因
　　 T m_GenerationGene[_GENERATION_AMOUNT]; //定义每个群体的基因
　　 P m_vProbability; //定义每个群体的适应度
　　 DISTANCE *lpCityDistance;
　　 int HistoryMin;
　　 T HistoryMinWay;
　　 T m_GenerationGeneBk[_GENERATION_AMOUNT];
　　
　　
　　};
　　//构造函数
　　template
　　Csga::Csga()
　　{
　　}
　　template
　　Csga::Csga(DISTANCE *lpDistance)
　　{
　　 lpCityDistance = lpDistance;
　　 m_vProbability.reserve(_CITY_AMOUNT);
　　 HistoryMin = _INFINITE;
　　
　　 //cout ＜＜ _P(lpCityDistance, 3, 2); //调试用
　　}
　　//析构函数
　　template
　　Csga::~Csga()
　　{
　　}
　　//产生随机基因
　　template
　　bool Csga::fnCreateRandomGene()
　　{
　　 srand( time(0) ); //初始化随机数
　　 //cout ＜＜ "\t基因序列" ＜＜ std::endl; //调试用
　　
　　 //生成随机基因
　　 for(int j, temp, i = 0; i ＜ _GENERATION_AMOUNT; ++i)
　　 {
　　 m_GenerationGene[i].reserve(_CITY_AMOUNT);
　　
　　 for (j = 0; j ＜ _CITY_AMOUNT; ++j)
　　 {
　　 do
　　 {
　　 temp = rand()%_CITY_AMOUNT;
　　 }while (find(m_GenerationGene[i].begin(), m_GenerationGene[i].end(), temp)
　　 != m_GenerationGene[i].end());
　　 m_GenerationGene[i].push_back(temp);
　　
　　 }//end for
　　 /*copy( m_GenerationGene[i].begin(), m_GenerationGene[i].end(),
　　 std::ostream_iterator(cout," ") );
　　 cout ＜＜ std::endl; */ //调试用
　　 }
　　 return true;
　　}
　　//基因变异
　　template
　　bool Csga::fnGeneAberrance()
　　{
　　 int i, j;
　　 int temp;
　　 srand(time(0));
　　
　　 //抽选一代中的某个基因进行变异
　　 for (i = 0; i ＜ _GENERATION_AMOUNT; ++i)
　　 {
　　 for (j = 0; j ＜ _CITY_AMOUNT; ++j)
　　 {
　　 temp = rand()%10000;
　　 if ( temp ＞ 0 && temp ＜= _P_GENE_ABERRANCE)
　　 {
　　 //随机抽选到的基因进行变异
　　 if(!fnGeneAberranceOne(i, j)) {exit(0);}
　　 }//end if
　　 }//end for j
　　 }//end for i
　　 return true;
　　}
　　//变异第i个基因的第j位染色体
　　template
　　bool Csga::fnGeneAberranceOne(const int &i, const int &j)
　　{
　　 int temp; //基因变异结果
　　 srand(time(0));
　　 T::iterator pos;
　　 //找到变异位与另外一位交换
　　 pos = std::find(m_GenerationGene[i].begin(), m_GenerationGene[i].end(), temp);
　　 if (pos != m_GenerationGene[i].end())
　　 {
　　 *pos = m_GenerationGene[i][j];
　　 m_GenerationGene[i][j] = temp;
　　 return true;
　　 }
　　 return false;
　　}
　　inline int fnRndBoundary(int iBegin, int iEnd)
　　{
　　
　　 return rand()%(iEnd-iBegin) + iBegin;
　　}
　　//基因交叉产生新的个体并淘汰适应度低的个体
　　template
　　bool Csga::fnGeneMix()
　　{
　　 srand(time(0));
　　 std::vector temp; //选择池
　　 P vProbabilityBk; //临时保存适应度
　　 vProbabilityBk = m_vProbability;
　　 temp.reserve( ((_GENERATION_AMOUNT+1)*_GENERATION_AMOUNT)/2 );
　　
　　 P::iterator pos;
　　
　　 for (int i = _GENERATION_AMOUNT; i ＞ 0; --i)
　　 {
　　 pos = std::min_element(vProbabilityBk.begin(), vProbabilityBk.end());
　　 temp.insert( temp.end(), i, (int)(pos-vProbabilityBk.begin()) );
　　 *pos = _INFINITE;
　　 }
　　
　　 /**************************************************************************
　　 fnDispProbability();
　　 cout ＜＜ "\ttemp\n" ＜＜ std::endl; //调试用
　　 copy( temp.begin(), temp.end(), std::ostream_iterator(cout," ") );
　　 cout ＜＜ std::endl; //调试用
　　 **************************************************************************/
　　 #define _MIN_ELEMENT std::min_element(m_vProbability.begin(), m_vProbability.end())
　　 m_GenerationGeneBk[_GENERATION_AMOUNT-1] = m_GenerationGene[_MIN_ELEMENT - m_vProbability.begin()];
　　
　　 int iFather; //父亲的代号
　　 int iMother; //母亲的代号
　　 T Child1, Child2; //父亲与母亲杂交出的子女的基因
　　 T::iterator tempIter;
　　 int LowBoundary;
　　 int HighBoundary;
　　 //int iChild1Probability,iChild2Probability;
　　 T fatherBk,motherBk;
　　 T::iterator V_iter;
　　 P::iterator P_iter;
　　 int iDistance;
　　 srand(time(0));
　　#ifndef _ITEMP
　　#define _ITEMP rand()%(((_GENERATION_AMOUNT+1)*_GENERATION_AMOUNT)/2)
　　#endif
　　 for (i = 0; i ＜ _P_GENE_MIX; ++i) //杂交_P_GENE_MIX/10次
　　 {
　　 iFather = temp[_ITEMP];
　　 do
　　 {
　　 iMother = temp[_ITEMP];
　　 }while(iMother == iFather);
　　
　　 Child1.reserve(_CITY_AMOUNT); //初始化子女的碱基数
　　 Child2.reserve(_CITY_AMOUNT);
　　 Child1.clear();
　　 Child2.clear();
　　
　　 LowBoundary = fnRndBoundary(0, _CITY_AMOUNT-2);
　　 HighBoundary= fnRndBoundary(LowBoundary+1, _CITY_AMOUNT-1);
　　 /**********************************************************************
　　 cout ＜＜ "iMother:" ＜＜ iMother ＜＜ std::endl;
　　 cout ＜＜ "iFather:" ＜＜ iFather ＜＜ std::endl;
　　 cout ＜＜ "LowBoundary:" ＜＜ LowBoundary ＜＜ std::endl;
　　 cout ＜＜ "HighBoundary:" ＜＜ HighBoundary ＜＜ std::endl;
　　 **********************************************************************/
　　
　　 fatherBk = m_GenerationGene[iFather];
　　 motherBk = m_GenerationGene[iMother];
　　 std::copy (fatherBk.begin()+LowBoundary, fatherBk.begin()+HighBoundary+1,
　　 std::back_inserter(Child1));
　　
　　 std::copy (motherBk.begin()+LowBoundary, motherBk.begin()+HighBoundary+1,
　　 std::back_inserter(Child2));
　　 /**********************************************************************
　　 cout ＜＜ "Child1:" ;
　　 for (tempIter=Child1.begin(); tempIter!=Child1.end(); ++tempIter)
　　 cout ＜＜ *tempIter ＜＜ " ";
　　 cout ＜＜ std::endl;
　　 cout ＜＜ "Child2:" ;
　　 for (tempIter=Child2.begin(); tempIter!=Child2.end(); ++tempIter)
　　 cout ＜＜ *tempIter ＜＜ " ";
　　 cout ＜＜ std::endl;
　　 **********************************************************************/
　　 std::rotate (fatherBk.begin(), fatherBk.begin()+HighBoundary+1, fatherBk.end());
　　 std::rotate (motherBk.begin(), motherBk.begin()+HighBoundary+1, motherBk.end());
　　 /**********************************************************************
　　 cout ＜＜ "fatherBk:" ;
　　 copy (fatherBk.begin(),fatherBk.end(), std::ostream_iterator(cout, " "));
　　 cout ＜＜ std::endl;
　　 cout ＜＜ "motherBk:" ;
　　 copy (motherBk.begin(), motherBk.end(), std::ostream_iterator(cout, " "));
　　 cout ＜＜ std::endl;
　　 **********************************************************************/
　　 for (V_iter = m_GenerationGene[iFather].begin()+LowBoundary;
　　 V_iter != m_GenerationGene[iFather].begin()+HighBoundary+1; ++V_iter)
　　 {
　　 motherBk.erase(std::remove(motherBk.begin(), motherBk.end(), *V_iter),
　　 motherBk.end());
　　 }
　　
　　 for (V_iter = m_GenerationGene[iMother].begin()+LowBoundary;
　　 V_iter != m_GenerationGene[iMother].begin()+HighBoundary+1; ++V_iter)
　　 {
　　
　　 fatherBk.erase(std::remove(fatherBk.begin(), fatherBk.end(), *V_iter),
　　 fatherBk.end());
　　 }
　　 /**********************************************************************
　　 cout ＜＜ "fatherBk:" ;
　　 copy (fatherBk.begin(),fatherBk.end(), std::ostream_iterator(cout, " "));
　　 cout ＜＜ std::endl;
　　 cout ＜＜ "motherBk:" ;
　　 copy (motherBk.begin(), motherBk.end(), std::ostream_iterator(cout, " "));
　　 cout ＜＜ std::endl;
　　 **********************************************************************/
　　 iDistance = _CITY_AMOUNT -HighBoundary - 1;
　　 std::copy(motherBk.begin(), motherBk.begin()+iDistance, std::back_inserter(Child1));
　　 std::copy(motherBk.begin()+iDistance, motherBk.end(), std::inserter(Child1,Child1.begin()));
　　 std::copy(fatherBk.begin(), fatherBk.begin()+iDistance, std::back_inserter(Child2));
　　 std::copy(fatherBk.begin()+iDistance, fatherBk.end(), std::inserter(Child2,Child2.begin()));
　　
　　 /**********************************************************************
　　 cout ＜＜ "Child1:";
　　 copy (Child1.begin(), Child1.end(), std::ostream_iterator(cout, " "));
　　
　　 cout ＜＜ "iChild1Probability:" ＜＜ iChild1Probability ＜＜ std::endl;
　　 cout ＜＜ "Child2:" ;
　　 copy (Child2.begin(), Child2.end(), std::ostream_iterator(cout, " "));
　　 cout ＜＜ "iChild2Probability:" ＜＜ iChild2Probability ＜＜ std::endl;
　　 **********************************************************************/
　　 /*iChild1Probability = fnEvalOne(Child1);
　　 //iChild2Probability = fnEvalOne(Child2);
　　
　　
　　 P_iter = std::max_element(m_vProbability.begin(), m_vProbability.end());
　　 if (iChild1Probability ＜ *P_iter)
　　 {
　　 m_GenerationGene[P_iter-m_vProbability.begin()] = Child1;
　　 *P_iter = iChild1Probability;
　　 }
　　 P_iter = std::max_element(m_vProbability.begin(), m_vProbability.end());
　　 if (iChild2Probability ＜ *P_iter)
　　 {
　　 m_GenerationGene[P_iter-m_vProbability.begin()] = Child2;
　　 *P_iter = iChild2Probability;
　　 }
　　 */
　　 m_GenerationGeneBk[2*i] = Child1;
　　 m_GenerationGeneBk[2*i+1] = Child2;
　　 }
　　 for (i = 0; i ＜ _GENERATION_AMOUNT; ++i)
　　 {
　　 m_GenerationGene[i] = m_GenerationGeneBk[i];
　　 }
　　
　　
　　 return true;
　　}
　　//测试基因的适应度
　　template
　　bool Csga::fnEvalAll()
　　{
　　 int i, j;
　　 m_vProbability.assign( _GENERATION_AMOUNT, 0);
　　 //cout ＜＜ "\t基因适应度\n";
　　
　　 //测试每组基因的适应性
　　 for (i = 0; i ＜ _GENERATION_AMOUNT; ++i)
　　 {
　　 for (j = 0; j ＜ _CITY_AMOUNT-1; ++j)
　　 {
　　 m_vProbability[i] += _P(lpCityDistance,
　　 m_GenerationGene[i][j], m_GenerationGene[i][j+1]);
　　 }//end for (j = 0; j ＜ _CITY_AMOUNT; ++j);
　　 m_vProbability[i] += _P(lpCityDistance,
　　 m_GenerationGene[i][_CITY_AMOUNT-1], m_GenerationGene[i][0]);
　　 if (m_vProbability[i] ＜ HistoryMin)
　　 {
　　 HistoryMin = m_vProbability[i];
　　 HistoryMinWay = m_GenerationGene[i];
　　 }
　　
　　 }//end for (int j, i = 0; i ＜ _GENERATION_AMOUNT; ++i)
　　 //copy (m_vProbability.begin(), m_vProbability.end(), std::ostream_iterator(cout," "));
　　 //cout ＜＜ std::endl;
　　 //m_vProbability[_GENERATION_AMOUNT-1] = fnEvalOne(m_GenerationGeneBk[_GENERATION_AMOUNT-1]);
　　 return true;
　　}
　　//测试某个基因的适应度并返回适应度
　　template
　　int Csga::fnEvalOne(T &Gene)
　　{
　　 int iResult = 0;
　　
　　 for (int i = 0; i ＜ _CITY_AMOUNT-1; ++i)
　　 {
　　 iResult += _P(lpCityDistance, Gene[i], Gene[i + 1]);
　　 }
　　
　　 return iResult;
　　}
　　template
　　void Csga::fnDispProbability()
　　{
　　
　　 /*cout ＜＜ "\t个体基因序列" ＜ 　　 for (int i = 0; i ＜ _GENERATION_AMOUNT; ++i)
　　 {
　　 cout ＜＜ " 个体" ＜＜ i+1 ＜＜ "的基因:";
　　 copy( m_GenerationGene[i].begin(), m_GenerationGene[i].end(),
　　 std::ostream_iterator(cout," ") );
　　 if (i%2 == 1)
　　 cout ＜＜ std::endl;
　　 }
　　 */
　　 cout ＜＜ "\t最小开销为:";
　　#define _VECT_TEMP std::min_element(m_vProbability.begin(), m_vProbability.end())
　　
　　
　　 cout ＜＜ *_VECT_TEMP ＜＜ std::endl;//+_GENERATION_AMOUNT
　　
　　 //cout ＜＜ "各个方案的路程分别为:" ;
　　 //copy (m_vProbability.begin(), m_vProbability.end(), std::ostream_iterator(cout, " "));
　　 cout ＜＜ std::endl;
　　 cout ＜＜ "*******************************************************" ＜＜ std::endl;
　　
　　
　　}
　　template
　　void Csga::fnDispHistoryMin()
　　{
　　 cout ＜＜ "历史上最短开销为:"＜＜ HistoryMin ＜＜ " 路径为:" ;
　　 std::copy (HistoryMinWay.begin(), HistoryMinWay.end(), std::ostream_iterator(cout, " -＞"));
　　 cout ＜＜ *HistoryMinWay.begin();
　　 cout ＜ 　　}