目录1.设计任务1.1 设计题目1.2设计要求1.3设计任务2．方案设计2.1原理2.2 具体设计方法3．系统实施3.1 系统开发环境3.2系统主要功能介绍3.3处理流程图3.4 核心源程序3.5系统运行结果4．开发心得4.1设计存在的问题4.2进一步改进提高的设想4.3经验和体会5．参考文献1. 设计任务1.1 设计题目在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。
这些数码可以在棋盘上移动，该问题称八数码难题或者重排九宫问题。
1.2 设计要求其移动规则是：与空格相邻的数码方格可以移入空格。
现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。
1.3 设计任务利用人工智能的图搜索技术进行搜索，解决八数码问题来提高在推理中的水平，同时进行新方法的探讨。
2. 方案设计2.1 原理八数码问题是个典型的状态图搜索问题。
搜索方式有两种基本的方式，即树式搜索和线式搜索。
搜索策略大体有盲目搜索和启发式搜索两大类。
盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。
2.2 具体设计方法启发式搜索由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。
所以引入启发式搜索策略。
启发式搜索就是利用启发性信息进行制导的搜索。
它有利于快速找到问题的解。
由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。
所以，这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息就可以指导搜索。
即可以利用启发信息来扩展节点的选择，减少搜索范围，提高搜索速度。
启发函数设定。
对于八数码问题，可以利用棋局差距作为一个度量。
搜索过程中，差距会逐渐减少，最终为零，为零即搜索完成，得到目标棋局。
3. 系统实施3.1 系统开发环境Windows操作系统、SQL Server 200X3.2 系统主要功能介绍该搜索为一个搜索树。
为了简化问题，搜索树节点设计如下：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）、从棋盘取出一个节点；（3）、判断棋盘估价值，为零则表示搜索完成，退出搜索；（4）、扩展子节点，即从上下左右四个方向移动棋盘，生成相应子棋盘；（5）、对子节点作评估，是否为优越节点（子节点估价值小于或等于父节点则为优越节点），是则把子棋盘压入队列，否则抛弃；（6）、跳到步骤（2）；3.3 处理流程图3.4 核心源程序#include "stdio.h"#include "stdlib.h"#include "time.h"#include "string.h"#include <queue>#include <stack>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<N;i++){printf("\t");for(int j=0;j<N;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<N;i++){bool HasGetBlankCell=false;for(j=0;j<N;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;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<N;x++){for(int y=0;y<N;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;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<M;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<N;i++){for(int j=0;j<N;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<struct Chess *> 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<N;i++){for(int j=0;j<N;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;stack<Chess *>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);}3.5 系统运行结果4. 开发心得4.1 设计存在的问题完全能解决简单的八数码问题，但对于复杂的八数码问题还是无能为力。