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

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

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

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

3、，然后判断扩展出的结点是否是目标结点，如果是则显示路径，程序结束。否则如果队列头的结点可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步，知道扩展出的结点是目标结点结束，并显示路径。代码如下，#include#include#include#include#indudeusingnamespacestd;#defineHashTableSize362881#defineNOT!#defineUP0#defineDOWN1#

4、defineLEFT2#defineRIGHT3#defineBitchartypedefstructmaps{Bitdetail[9];intmyindex;//记录自己节点在hash表中的位置Bitposition;//记录空格（0）在序列中的位：}Map,*PMap;Maporg;//初始状态intEndlndex;//目标，上移，下移，左移，右移intconstderection[4]={-3//可移动的四个方向1}；intconstFactorial[9]={40320，5040，720，120，24，6，2，1，1

5、};intHashTablerHashTableSizel={O};录的是上一个父节点对应的位置//hash表，其中记/****八数码的输入（在这里不做任何输入检查，均认为输入数据是正确的）水氺本/voidinput()intij;intsum，count，index;printf("输入九个数:”);//必须输入一个0作为空for(i=0;i<9;i++){scanf(’’％ld”，&org.detail[i]);org.detail[i]

6、

7、(org.position=i);}for(i=0;i<9;i++)//计算逆

8、序if(0==org.detail[i])continue;for(j=0;jorg.detail[i];index+=Factorial[org.detail[i]]*count;}org.myindex=index+1;Endlndex=

9、sum%2?161328:322561;//目标状态的hash值return;}/***hash值的计父状态的hash移动的方向#7inlineintHashValue(Map&Parent,int&direct){inti=Parentposition;intnewindex=Parent.myindex;Bit*p=Parent.detail;switch(direct){caseUP:{newindex-=3*40320;newindex+=(p[i-2]>p[i■3])?(Factorialp[i-3]]):(-Fac

10、torial[p[i-2]]);newindex+=(p[i-1]>p[i-3])?(Factorial[p[i-3]]):(■Factorial[p[i-1]]);break;}caseDOWN:{newindex+=3*40320;newindex-=(p[i+2]>p[