人工智能A算法九宫格

1、 人工智能原理与方法A宕算法实现八数码搜索问题模式识别与智能系统SY1003113游遵文题目：编程实现8数码问题初始状态：38215764目标状态:12384765要求：1、报告：给出状态表示，编码规则，搜索算法A4简单程序说明，最优路径。2、调通的程序（语言不限）状态表示用一个3X3的数组來表示状态，数组中的各个元素对应状态位置的数字。其中空格用0表示。二、编码规则在程序实现过程中，只有移动0的位置，即可生成新的节点。规则库then上移then下移then左移then右移设数组中0的位置为aij,其中0WiW2,0WjW2Rl：if(i21)Rl：if(iWl)Rl：Rl：if(jWl)三、

2、搜索算法A*用于度量节点的“希望”的量度f),即用來衡量到达目标节点的路径的可能性大小。A算法：基本思想：定义一个评价函数，对当前的搜索状态进行评估，找出一个最有希望的节点进行扩展：f(n)=g(n)+h(n),n为被评价节点g*(n)：从s到口的最优路径的实际代价h*(n)：从n到g的最优路径的实际代价fic(n)=g*(n)+h*(n)：从s经过n到g的最优路径的实际代价g(n)h(n)f(n)分别是g*(n)h*(n)f*(n)的估计值g(n)通常为从S到到n这段路径的实际代价，则有g(n)2g*(n)h(n):是从节点n到目标节点Sg的最优路径的估计代价.它的选择依赖于有关问题领域的启

3、发信息，叫做启发函数A算法：在图搜索的一般算法中，在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序表中的节点进行排序，找出一个最有希望的节点作为下一次扩展的节点。在A算法中，如果满足条件：h(n)h*(n)，则A算法称为A*算法。在本算法中，为实现八数码的搜索问题，定义估价函数为：f(n)=g(n)+h(n),其中g(n)表示节点11在搜索树中的深度；h(n)表示节点11的各个数码到目标位置的曼哈顿距离和。四、程序说明1、算法实现的步骤：把初始节点SO放入Open表中，置SO的代价g(SO)=O；如果Open表为空，则问题无解，失败退出；把Open表的第一个

4、节点取出放入Closed表，并记该节点为n考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；若节点11不可扩展，则转第(2)步；扩展节点11,生成其子节点ni,(其中1=1,2,3,),将这些子节点放入Open表中，并为每一个子节点设置指向父节点的指针；按公式g(ni)=g(n)+c(n,ni)(i=l,2,)计算Open表中的各子节点的代价，并根据各节点的代价对Open表中的全部节点按照从小到大顺序重新进行排序；然后转第(2)步。2、思路通过代价函数对Open表中的节点进行排序，代价小的先扩展。 五、搜索算法得出的最优路径如下图所示，搜索算法从初始节点到目标节点经历了18个状态。

5、7结论通过这次的实验，深入了解了启发式搜索算法的内涵，尤其是A*算法的优越性。然而在实际工程中，选择合适、优异的估价函数存在一定困难，特别要注意其信息量的强度不能超过其上限值，否则A*算法会变成A算法；而A算法是非充分的，即可能不在其最优路径上，从而导致不能找到目标节点。同时，在实验过程中，也熟悉了C+编程和VC的开发环境；但编程能力还是极其有限，急需提升。附录：A*算法代码的核心部分pnodemove(pnodep,intdir)pnodeUnode=(pnode)malloc(sizeof(node);for(inti=0;i=2;i+)for(intj=0;jai0=p-aij；swit

6、ch(dir)case1:/upUnode-x=p-x-1;Unode-y=p-y;Unode-aUnode-xUnode-y=0;Unode-aUnode-x+1Unode-y=p-aUnode-xUnode-y);break;case2:/downUnode-father=p;Unode-g=p-g+1;深度增加一层Unode-h=hvalue(Unode-a,final);更新h函数值Unode-f二Unode-h+Unode-g;returnUnode;intmain(intargc,char*argv)pnodeA0=(pnode)malloc(sizeof(node);pnodeo

7、pen,/open表头close,/close表头now,当前节点Lnode,Rnode,Unode,Dnode,下一个左，右，上，下节点fnode;终节点initial(AO,start);open=A0;close=NULL;while(1)/Open表为空，未找到解，结束搜索程序/open表中第一个节点是解，结束搜索把finalnode从open表中拿出，放到close表中if(open=NULL)fnode=NULL;coutM未能找到解”;return0;if(open-h=0)fnode=open;open=opennext;fnode-next=NULL;fnodeclnext=

8、close;close=fnode;break;now=open;intX,Y;X二now-x;Y=now-y;if(X0)&(now-father=NULL|now-father-x!=X-1) # #Unode=move(now,1);空格上移，得到新节点 # #insert(Unode,open);/把新节点插入open表中 # #if(Xfather=NULL|now-father-x!=X+1)空格下移Dnode=move(now,2);insert(Dnode,open);if(Y0)&(now-father=NULL|now-father-y!=Y-1)Lnode=move(now,3);insert(Lnodefopen);if(Yfather=NULL|now-father-y!=Y+1) Rnode=move(now,4);insert(Rnode,open);now-clnext二close;close二now;open=opennext;while(fnode-father!=NULL)fnode-father-next=fnode;fnode=fnode-father;while(fnode!=NULL)disp(fnode);f