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

八数码问题（一）问题描述在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题或者重排九宫问题。（二）问题分析八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。1、启发式搜索由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息就可以指导搜索。即可以利用启发信息来扩展节点的选择，减少搜索范围，提高搜索速度。启发函数设定。对于八数码问题，可以利用棋局差距作为一个度量。搜索过程中，差距会逐渐减少，最终为零，为零即搜索完成，得到目标棋局。（三）数据结构与算法设计该搜索为一个搜索树。为了简化问题，搜索树节点设计如下：structChess//棋盘{intcell[N][N];//数码数组intValue;//评估值DirectionBelockDirec;//所屏蔽方向structChess*Parent;//父节点};intcell[N][N];数码数组：记录棋局数码摆放状态。intValue;评估值：记录与目标棋局差距的度量值。DirectionBelockDirec;所屏蔽方向：一个屏蔽方向，防止回推。Direction：enumDirection{None,Up,Down,Left,Right};//方向枚举structChess*Parent;父节点：指向父亲节点。下一步可以通过启发搜索算法构造搜索树。1、局部搜索树样例：2、搜索过程搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）。搜索过程如下：（1）、把原棋盘压入队列；（2）、从棋盘取出一个节点；（3）、判断棋盘估价值，为零则表示搜索完成，退出搜索；（4）、扩展子节点，即从上下左右四个方向移动棋盘，生成相应子棋盘；（5）、对子节点作评估，是否为优越节点（子节点估价值小于或等于父节点则为优越节点），是则把子棋盘压入队列，否则抛弃；（5）、跳到步骤（2）；3、算法的评价完全能解决简单的八数码问题，但对于复杂的八数码问题还是无能为力。现存在的一些优缺点。1、可以改变数码规模（N），来扩展成N*N的棋盘，即扩展为N数码问题的求解过程。!--[if!supportLists]--2、!--[endif]--内存泄漏。由于采用倒链表的搜索树结构，简化了数据结构，但有部分被抛弃节点的内存没有很好的处理，所以会造成内存泄漏；!--[if!supportLists]--3、!--[endif]--采用了屏蔽方向，有效防止往回搜索（节点的回推），但没能有效防止循环搜索，所以不能应用于复杂度较大的八数码问题；源码：#includestdio.h#includestdlib.h#includetime.h#includestring.h#includequeue#includestackusingnamespacestd;constintN=3;//3*3棋盘constintMax_Step=30;//最大搜索深度enumDirection{None,Up,Down,Left,Right};//方向structChess//棋盘{intcell[N][N];//数码数组intValue;//评估值DirectionBelockDirec;//所屏蔽方向structChess*Parent;//父节点};//打印棋盘voidPrintChess(structChess*TheChess){printf(------------------------------------------------------------------------\n);for(inti=0;iN;i++){printf(\t);for(intj=0;jN;j++){printf(%d\t,TheChess-cell[i][j]);}printf(\n);}printf(\t\t\t\t差距:%d\n,TheChess-Value);}//移动棋盘structChess*MoveChess(structChess*TheChess,DirectionDirect,boolCreateNewChess){structChess*NewChess;//获取空闲格位置inti,j;for(i=0;iN;i++){boolHasGetBlankCell=false;for(j=0;jN;j++){if(TheChess-cell[i][j]==0){HasGetBlankCell=true;break;}}if(HasGetBlankCell)break;}//移动数字intt_i=i,t_j=j;boolAbleMove=true;switch(Direct){caseUp:t_i++;if(t_i=N)AbleMove=false;break;caseDown:t_i--;if(t_i0)AbleMove=false;break;caseLeft:t_j++;if(t_j=N)AbleMove=false;break;caseRight:t_j--;if(t_j0)AbleMove=false;break;};if(!AbleMove)//不可以移动则返回原节点{returnTheChess;}if(CreateNewChess){NewChess=newChess();for(intx=0;xN;x++){for(inty=0;yN;y++)NewChess-cell[x][y]=TheChess-cell[x][y];}}elseNewChess=TheChess;NewChess-cell[i][j]=NewChess-cell[t_i][t_j];NewChess-cell[t_i][t_j]=0;returnNewChess;}//初始化一个初始棋盘structChess*RandomChess(conststructChess*TheChess){intM=30;//随机移动棋盘步数structChess*NewChess;NewChess=newChess();memcpy(NewChess,TheChess,sizeof(Chess));srand((unsigned)time(NULL));for(inti=0;iM;i++){intDirect=rand()%4;//printf(%d\n,Direct);NewChess=MoveChess(NewChess,(Direction)Direct,false);}returnNewChess;}//估价函数intAppraisal(structChess*TheChess,structChess*Target){intValue=0;for(inti=0;iN;i++){for(intj=0;jN;j++){if(TheChess-cell[i][j]!=Target-cell[i][j])Value++;}}TheChess-Value=Value;returnValue;}//搜索函数structChess*Search(structChess*Begin,structChess*Target){Chess*p1,*p2,*p;intStep=0;//深度p=NULL;queuestructChess*Queue1;Queue1.push(Begin);//搜索do{p1=(structChess*)Queue1.front();Queue1.pop();for(inti=1;i=4;i++)//分别从四个方向推导出新子节点{DirectionDirect=(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)//设置屏蔽方向,防止往回推{caseUp:p2-BelockDirec=Down;break;caseDown:p2-BelockDirec=Up;break;caseLeft:p2-BelockDirec=Right;break;caseRight:p2-BelockDirec=Left;break;}Queue1.push(p2);//存储节点到待处理队列if(p2-Value==0)//为0则,搜索完成{p=p2;i=5;}}else{deletep2;//为劣质节点则抛弃p2=NULL;}}}Step++;if(StepMax_Step)returnNULL;}while(p==NULL||Queue1.size()=0);returnp;}main(){Chess*Begin,Target,*T;//设定目标棋盘[012],[345],[678]for(inti=0;iN;i++){for(intj=0;jN;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;stackChess*Stack1;while(p-Parent!=NULL){Stack1.push(p);p=p-Parent;}printf(搜索结果:\n);while(!Stack1.empty()){PrintChess(Stack1.top());Stack1.pop();}printf(\n完成!);}elseprintf(搜索不到结果.深度为%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，