人工智能实验报告 八数码问题

实验一 启发式搜索算法姓名：徐维坚 学号：2220103484 日期：2012/6/29一、实验目的：熟练掌握启发式搜索A*算法及其可采纳性。二、实验内容：使用启发式搜索算法求解8 数码问题。1) 编制程序实现求解8数码问题A*算法，采用估价函数f (n)= d(n)+，其中：d(n)是搜索树中结点n的深度；w(n)为结点n的数据库中错放的棋子个数；p(n)为 结点n的数据库中每个棋子与其目标位置之间的距离总和。2) 分析上述中两种估价函数求解8数码问题的效率差别，给出一个是p(n)的上界 的h(n)的定义，并测试使用该估价函数是否使算法失去可采纳性。三、实验原理：1. 问题描述：八数码问题也称为九宫问题。在3X3的棋盘，摆有八个棋子，每个棋子上标有1至8 的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格(以数字0 来表示)，与空 格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状 态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初 始状态到达目标状态所经过的一系列中间过渡状态。2. 原理描述：2.1 有序搜索算法：(1) 原理：在搜索过程中，OPEN表中节点按照其估价函数值以递增顺序排列，选择OPEN表中具 有最小估价函数值的节点作为下一个待扩展的节点，这种搜索方法称为有序搜索。在本例中，估价函数中的g(n)取节点深度d(n)，h(n)为节点n的状态与目标状态之 间错放的个数，即函数 (n)。(2) 算法描述： 把起始节点S放到OPEN表中，并计算节点S的f (S)； 如果OPEN是空表，则失败退出，无解； 从OPEN表中选择一个f值最小的节点i。如果有几个节点值相同，当其中有一个 为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i ； 把节点i从OPEN表中移出，并把它放入CLOSED的已扩展节点表中； 如果i是个目标节点，则成功退出，求得一个解； 扩展节点i，生成其全部后继节点。对于i的每一个后继节点j :计算f ( j);如果j既不在OPEN表中，又不在CLOCED表中，则用估价函数f把 它添入OPEN表中。从j加一指向其父节点i的指针，以便一旦找到目标节点时记住一个解 答路径；如果j已在OPEN表或CLOSED表中，则比较刚刚对j计算过的f和前面计算过 的该节点在表中的f值。如果新的f较小，则以此新值取代旧值。(II) 从j指向i，而不是指向他的父节点。(III) 如果节点j在CLOSED表中，则把它移回OPEN表中。 转向，即GOTO。(3) 算法流程图：选舰OPEN表中/悄剝啲节点j,A CLOSED 表扩展h得后雉节点计算“几賊返回的指曲 利用九/)对OPEN表重新排序，凋整亲子关系及指针2.2启发式搜索技术(1) 原理启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置， 再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发 式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。(2) 估价函数计算一个节点的估价函数，可以分成两个部分：1、已经付出的代价(起始节点到当前节点)；2、将要付出的代价(当前节点到目标节点)。节点n的估价函数f (n)定义为从初始节点、经过n、到达目标节点的路径的最小代价 的估计值，即 f *(n) = g*(n)+ h*(n) 。g*(n)是从初始节点到达当前节点n的实际代价；h*(n)是从节点n到目标节点的最佳路径的估计代价，体现出搜索过程中采用的启发式 信息(背景知识)，称之为启发函数。g*(n)所占的比重越大，越趋向于宽度优先或等代价搜索；反之，h*(n)的比重越大， 表示启发性能就越强。本实验中我们使用函数p(n)，其值是节点n与目标状态节点相比较，每个错位棋牌在 假设不受阻拦的情况下，移动到目标状态相应位置所需走步(移动次数)的总和。显然 p(n) 比 (n)更接近于h*(n)，因为p(n)不仅考虑了错位因素，还考虑了错位的距离。(3) 算法描述：参考有序搜索算法描述，基本相同。流程图亦参考有序算法流程图。四、实验程序及其说明：1) int goalNN， struct Chessboard：试验中我定义goal数组为目标状态 1,2,3,8,0,4,7,6,5。结构体Chessboard记录棋盘 信息，其中变量pos数组坐标记录每个数码a的位置，其值为数码a。d表示该棋盘的深度， f 为启发函数值， move 为父节点移动到该节点的方式，以便在输出时告诉用户该如何移动 棋子知道目标状态。2) struct LNode：定义节点LNode结构体，存放该节点状态时的棋盘信息board，和指向父节点、下一节 点的指针(*parent,*next)，以及标记量flag值为true时表示该节点是最佳路径上的节点。3) int* Findzero(LNode* &Node)：为方便找到空格，我设计了找到该函数Findzero(*&Node),以便找到当前节点空格所在 位置以利于接下来的程序执行。返回值为空格所在的行和列。4) int Wrong(LNode *Node)和 int pick(LNode *Node)：分别为函数(n)和p(n)。5) LNode* extend(LNode *Node,int depth,int zero2,int moveflag,int Choose)树形方式扩展节点。Node为要扩展的当前节点，depth为当前深度，zero存放该节点空 格位置信息，moveflag即扩展节点的移动方式，Choose为选择函数(n)还是p(n)。6) void InitList(LNode* &Open,LNode* &Close) 和 int ListInsert(List &L,LNode* NewNode)分别为表OPEN、CLOSE的创建和表的插入操作。7) LNode* Getminf(List &L)主要是实现从OPEN表中选择一个f值最小的节点i。如果有几个节点值相同，当其中 有一个为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i。五、实验小结通过本次试验，我对启发式搜索有了更加深入的了解。在实验中，通过对两种启发式搜索所扩在的节点数来看，p(n)看来比 (n)更加有效， 能在复杂情况下求得更加优质的解，避免不必要的节点的扩展。但是对于估价函数h*(n)来 说，它的定义趋向多元化，p(n)只是它的一个比较好的特例，对一复杂的搜索问题，如国 际象棋问题，他就显得较简单。所以，要更好地定义一个估价函数还有待深入讨论。在寻找最佳扩展路径的过程中我发现，最佳扩展路基上的节点均在CLOSED表中，利 用标志flag，以及它们之间的父子关系，我很容易的就找到了扩展路径，避免了再用一个路 径指针 path 来找到路径，这样节省了存储空间，更利于搜索。通过实验结果来看，这两个函数都是可采纳的，尽管n)存在不必要的扩展。六、实验代码及输出结果1. 源代码：#include#include#include#define Overflow 1#define N 3int goalNN=1,2,3,8,0,4,7,6,5;int zero2,NodeQTY=0;int *z=zero;记录 0 的位置，zero0:r 行；zerol:c 列 typedef int Piece;struct Chessboard 棋盘信息Piece posNN;/记录每个数码a的位置r行c列int d,f,move;/d:深度；f:启发函数值；move:父节点移动到该节点的方式;struct LNodeChessboard board;LNode *parent,*next;bool flag;typedef LNode* List;int* Findzero(LNode* &Node)int i,j,zr2;int *z=zr;for(i=0;iN;i+)for(j=0;jboard.posij=0)zr0=i+1;zr1=j+1;break;return z;int Wrong(LNode *Node)int w=0,i,j;for(i=0;iN;i+)for(j=0;jboard.posij!=goalij&Node-board.posij!=0) w+;return w;int pick(LNode *Node)int w=0,i,j,ii,jj;for(i=0;iN;i+)for(j=0;jboard.posij!=goalij&Node-board.posij!=0) for(ii=0;iiN;ii+)for(jj=0;jjboard.posij=goaliijj) w=w+abs(ii-i)+abs(jj-j);break;return w;LNode* extend(LNode *Node,int depth,int zero2,int moveflag,int Choose)LNode* NewNode=new LNode;for(int i=0;iN;i+)for(int j=0;jboard.posij=Node-board.posij;switch(moveflag)case 1: 向左移，不能出界：zerol=2NewNode-board.poszero0-1zero1-1=NewNode-board.poszero0-1zero1-2;NewNode-board.poszero0-1zero1-2=0;break;case 2: /向右移，不能出界： zero1board.poszero0-1zero1-1=NewNode-board.poszero0-1zero1;NewNode-board.poszero0-1zero1=0;break;case 3: /向上移，不能出界： zero0=2NewNode-board.poszero0-1zero1-1=NewNode-board.poszero0-2zero1-1; NewNode-board.poszero0-2zero1-1=0;break;case 4: /向下移，不能出界： zero0board.poszero0-1zero1-1=NewNode-board.poszero0zero1-1;NewNode-board.poszero0zero1-1=0;break;NewNode-board.d=depth+1; switch(Choose)case 1:NewNode-board.f=NewNode-board.d+Wrong(NewNode);break;case 2:NewNode-board.f=NewNode-board.d+pick(NewNode);break;NewNode-board.move=moveflag;NewNode-parent=Node;NodeQTY+;return NewNode;void InitList(LNode* &Open,LNode* &Close)Open=(List)malloc(sizeof(LNode);Close=(List)malloc(sizeof(LNode); if(!Open&!Close)exit(Overflow);Open-next=NULL;Close-next=NULL;int ListInsert(List &L,LNode* NewNode)List p=L;while(p-next)p=p-next;NewNode-next=p-next;p-next=NewNode;return true;LNode* Getminf(List &L)List p=L,q=L-next,r=L,min;min=q;/p,q寻找f最小值的指针，r指向表L中min前一个元素if(!q)return NULL;while(q)if(min-board.fq-board.f)r=p; min=q;p=q;q=q-next;r-next=min-next; min-next=NULL; return min;int main()int i,j,choose;List Open,Close;LNode *Best,*current;LNode *Start=new LNode;printf(ttt八 数 码 问 题 求 解n);printf(n请输入初始状态：); for(i=0;iN;i+)for(j=0;jboard.posij);printf(注:The flag of movement-】:左移;2 :右移;3:上移;4:下移)n); printf(初始棋盘状态：n);for(i=0;iN;i+)for(j=0;jboard.posij);printf(|n);InitList(Open,Close);printf(请选择(1:A 算法;2:A*算法):)；scanf(%d,&choose);Start-board.d=0;switch(choose)case 1:Start-board.f=Start-board.d+Wrong(Start);break;case 2:Start-board.f=Start-board.d+pick(Start);break; / Start-board.f=0+Wrong(Start);Start-board.move=0;Start-parent=NULL;Start-next=NULL;Start-flag=1;ListInsert(Open,Start);/将 S 加入到 Open 表中 while(Open-next)Best=Getminf(Open);ListInsert(Close,Best); if(!(Best-board.f-Best-board.d)printf(”$*有解！ *$n);break;z=Findzero(Best);zero0=*(z+0);zero1=*(z+1); if(zero1=N-1&Best-board.move!=2)ListInsert(Open,extend(Best,Best-board.d,zero,1,choose);if(zero1board.move!=1)ListInsert(Open,extend(Best,Best-board.d,zero,2,choose); if(zero0=N-1&Best-board.move!=4)ListInsert(Open,extend(Best,Best-board.d,zero,3,choose); if(zero0board.move!=3)ListInsert(Open,extend(Best,Best-board.d,zero,4,choose);printf（本算法搜索图中总共扩展的节点数为：dn,NodeQTY）; printf（t最佳路径如下所示：n）;if(Open-next)while(Best-parent)Best-flag=1;Best=Best-parent;List p=Close-next,q=Close-next; if(p=Start) q=p-next;else exit(1);int Step=0;while(p&q)在Close表中依标记找到路径 if(q-flag=1&q-parent=p) printf(Step %d:0 move asthe %d-flag of movement.n,+Step,q-board.move); for(i=0;iN;i+)for(j=0;jboard.posij);printf(|n);p=q;记住父节点q=q-next;printf(到达目标状态！ n);else printf(该问题无法求解！ n);2. 输出结果2.1 A 算法：ofofas4|达八数码BO八 数 码问 题 求 解请输zM刃始狀态：10 3 7 2 4 G 8 5：The flaj of movencnt1.=左齐多詔匸右移泊=上多沖=下币多 初始棋盘状态：!1 |J3!3 I!7f2I4E：6 S3 IE :雪華吟严具袪八士K. 4*1 Fl :i I HMiCXX靳右主古 亠r的节点数为：士工i?tai4i ：6 m :E i?18 1/41!?I6 IE !：7 ffi：E 亦狀态!；7 ；8 1-1 ；沛!0!&!tep 3:0 noue as the 1-flag of nfluement !1 !2 13 1；S ；645 ； tep 4 = 0 move a.s the 3f laf of movement;. ；1 ；2 ：31!0 !8 14 !mfluementmoueStep 5：9!i !2 J3!；8 10H1!7 !6 ：5 I到达目标収态！ 请按SB继续E: ?人工智蓋篇裁龛B示袁植苹虫!金5誉基W盍我的H戯阳exo2.2 A*算法:b： *人二智翹！莪為疽示丈垢-邙宝主甲s草基r 素i豆的擞Step 1：0 move as the ：1 ：2 ：3 !movernent Step 2 :R vnoue11 12 !3 Imouenent.16 1015 IKtep 3 sIS move i：l ：2 ：3 !movenentStep 4:0 moue !1 !2 !3 !mauenent.Step 5：M noye：1 ；2 ：3 :!S !0!4!青输入初贻状态；1H372 4faB 5,fT.iThe flag- of nouenient1 ：移;2=冇移营3 =上移；4： 初始棋盘状态；19SI3I：7 ：2 1=4：；G 38 ；51F靑选择，谊法；2 :叶算法“ 23 $ $ X-X-MM M 3*- 6 前羊 I aeXXMXXj 专古氐算法搜索图审总共扩展的节点数为；“最佳路径如下所示：I mnueiriu venient themouenient： 一mnuement-