人工智能8位数码难题的问题求解.pdf

《人工智能8位数码难题的问题求解.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告实验名称：8位数码难题的问题求解实验目的和要求：目的：1.理解和掌握解决实际问题的搜索算法或策略；2.能够用选定的编程语言实现搜索算法；要求：1.随机输入1-8数字；2.采用所学过的搜索算法（算法不限，但需要有注释，采用算法之一，或几种算法实现）；3.要求输出算法执行的过程结果；4.按顺序输出1-8数字；实验软硬件要求：网络计算机，c++编程环境实验内容、方法和步骤（可附页）我们将八数码难题分布在3×3方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态S0，目标状态如图所示，可以使用的操作有:空格上移，空格左移，空格右移，空格下移。

2、我们将是用广度优先搜索算法来解决这一问题。我们先拟定初始数列为035214876（0表示空位）1算法流程图：初始状态35214876123结果84765数据结构：本实验使用的数据结构是队列，应用队列先进先出的特点来实现对节点的保存和扩展。首先建立一个队列，将初始结点入队，并设置队列头和尾指，然后取出队列（头指针所指）的结点进行扩展，从它扩展出子结点，并将这些结点按扩展的顺序加入队列，然后判断扩展出的新结点与队列中的结点是否重复，如果重复则，否则记录其父结点，并将它加入队列，更新队列尾指针，然后判断扩展出的结点是否是目标结点，如果是则显示路径，程序结束。否则如果队列头的

3、结点可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步，知道扩展出的结点是目标结点结束，并显示路径。2代码如下：#include#include#include#include#includeusingnamespacestd;#defineHashTableSize362881#defineNOT!#defineUP0#defineDOWN1#defineLEFT2#defineRIGHT3#defineBitchartypedefstructmaps{Bitd

4、etail[9];intmyindex;//记录自己节点在hash表中的位置Bitposition;//记录空格（0）在序列中的位置}Map,*PMap;Maporg;//初始状态3intEndIndex;//目标,上移，下移，左移，右移intconstderection[4]={-3,3,-1,1};//可移动的四个方向intconstFactorial[9]={40320,5040,720,120,24,6,2,1,1};intHashTable[HashTableSize]={0};//hash表,其中记录的是上一个父节点对应的位置/****八数码的输入（在这里

5、不做任何输入检查，均认为输入数据是正确的）***/voidinput(){inti,j;intsum,count,index;printf("输入九个数：");//必须输入一个0作为空值for(i=0;i<9;i++){scanf("%1d",&org.detail[i]);org.detail[i]

6、

7、(org.position=i);}for(i=0;i<9;i++)//计算逆序4{if(0==org.detail[i])continue;for(j=0;j

8、ail[i]);}for(i=0,index=0;i<9;i++)//计算初始状态的hash值{for(j=0,count=0;jorg.detail[i];index+=Factorial[org.detail[i]]*count;}org.myindex=index+1;EndIndex=sum%2?161328:322561;//目标状态的hash值return;}/***hash值的计算*Parent:父状态的hash值*direct:移动的方向**/inlineintHashValue(Map&Pare

9、nt,int&direct){inti=Parent.position;intnewindex=Parent.myindex;5Bit*p=Parent.detail;switch(direct){caseUP:{newindex-=3*40320;newindex+=(p[i-2]>p[i-3])?(Factorial[p[i-3]]):(-Factorial[p[i-2]]);newindex+=(p[i-1]>p[i-3])?(Factorial[p[i-3]]):(-Factorial[p[i-1]]);break;}caseDOWN:{ne