人工智能实验报告,包括八数码问题八皇后问题和tsp问题.doc

八数码问题（一）问题描述在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题或者重排九宫问题。（二）问题分析八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。1、启发式搜索由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息就可以指导搜索。即可以利用启发信息来扩展节点的选择，减少搜索范围，提高搜索速度。 启发函数设定。对于八数码问题，可以利用棋局差距作为一个度量。搜索过程中，差距会逐渐减少，最终为零，为零即搜索完成，得到目标棋局。（三）数据结构与算法设计该搜索为一个搜索树。为了简化问题，搜索树节点设计如下：struct Chess/棋盘 int cellNN;/数码数组 int Value;/评估值 Direction BelockDirec;/所屏蔽方向 struct Chess * Parent;/父节点;int cellNN; 数码数组：记录棋局数码摆放状态。int Value; 评估值：记录与目标棋局差距的度量值。Direction BelockDirec; 所屏蔽方向：一个屏蔽方向，防止回推。Direction ：enum DirectionNone,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 DirectionNone,Up,Down,Left,Right;/方向struct Chess/棋盘 int cellNN;/数码数组 int Value;/评估值 Direction BelockDirec;/所屏蔽方向 struct Chess * Parent;/父节点;/打印棋盘void PrintChess(struct Chess *TheChess) printf(-n); for(int i=0;iN;i+) printf(t); for(int j=0;jcellij); printf(n); printf(tttt差距:%dn,TheChess-Value);/移动棋盘struct Chess * MoveChess(struct Chess * TheChess,Direction Direct,bool CreateNewChess) struct Chess * NewChess; /获取空闲格位置 int i,j; for(i=0;iN;i+) bool HasGetBlankCell=false; for(j=0;jcellij=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=N) AbleMove=false; break; case Right: t_j-; if(t_j0) AbleMove=false; break; ; if(!AbleMove)/不可以移动则返回原节点 return TheChess; if(CreateNewChess) NewChess=new Chess(); for(int x=0;xN;x+) for(int y=0;ycellxy=TheChess-cellxy; else NewChess=TheChess; NewChess-cellij=NewChess-cellt_it_j; NewChess-cellt_it_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;iM;i+) int Direct=rand()%4; /printf(%dn,Direct); NewChess=MoveChess(NewChess,(Direction) Direct,false); return NewChess;/估价函数int Appraisal(struct Chess * TheChess,struct Chess * Target) int Value=0; for(int i=0;iN;i+) for(int j=0;jcellij!=Target-cellij) 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;iBelockDirec)/跳过屏蔽方向 continue; p2=MoveChess(p1,Direct,true);/移动数码 if(p2!=p1)/数码是否可以移动 Appraisal(p2,Target);/对新节点估价 if(p2-ValueValue)/是否为优越节点 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(StepMax_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;iN;i+) for(int j=0;jParent=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(搜索不到结果.深度为%dn,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) ./随机取得各行的初始皇后位置，以Queeni表示第i行的皇后位置 for(int i=0;in;i ) Queeni=abs(rand()%n; int collision(int Queen,const int row,const int column,const int n) . /计算每个位置的冲突值 int bug=0; for(int i=0;in;i ) . if (i!=row)&(Queeni=column|(Queeni-column)=(i-row) |(Queeni-column)=(row-i)/同列，同对角线的情况 bug ; return bug; void show(int Queen,const int n) ./打印皇后图 cout; for(int k=0;kn-1;k ) cout; coutendl; for(int i=0;in-1;i ) . cout; for(int j=0;jn;j ) cout(j=Queeni)? 凤 : );/有皇后的位置用凤 coutendl; cout; for(j=0;jn-1;j ) cout; coutendl; cout; for(int j=0;jn;j ) cout(j=Queenn-1)? 凤 : );/有皇后的位置用，没有的用_ coutendl; cout; for(k=0;kn-1;k ) cout; coutendl; coutendl; 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;in;i ) . minbug=collision(Queen,i,Queeni,n);/取得当前的冲突数，不断优化 int temp=Queeni; for(int j=0;jn;j ) . int bug=collision(Queen,i,j,n); if(bugmax) max=minbug; show(Queen,n); count ; return count; void main() . int n=-1; int step=0; coutWelcome to N Queen Settlementendl; coutInput N (you would better input a interge minor to 15):n; if(n=0) . coutIllegal Input!endl; return; int* Queen=new intn; srand(time(NULL);/取得随机种子 shuffle(Queen,n); coutThe oringinal state:100) . coutCould find solution within 100 steps,Try again!endl; return; coutAfter step 1 stepsendl; coutThe goal state arrives!endl; 汉诺塔问题遗传算法求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 100000typedef int DISTANCE; /距离矩阵的数据存储类型#endif_TSP.cpp_#include #include #include #include #include #include def.h#include TSP.hvoid 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 ; /城市间的距离矩阵 /distanceij代表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 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.husing 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_GenerationGenei.reserve(_CITY_AMOUNT); for (j = 0; j _CITY_AMOUNT; +j) do temp = rand()%_CITY_AMOUNT; while (find(m_GenerationGenei.begin(), m_GenerationGenei.end(), temp) != m_GenerationGenei.end(); m_GenerationGenei.push_back(temp); /end for /*copy( m_GenerationGenei.begin(), m_GenerationGenei.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 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_GenerationGenei.begin(), m_GenerationGenei.end(), temp); if (pos != m_GenerationGenei.end() *pos = m_GenerationGeneij; m_GenerationGeneij = 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_AMO