人工智能实验报告.doc

Forpersonaluseonlyinstudyandresearch;mercialuse人工智能九宫格重移——搜索成员::八数码问题也称为九宫问题。在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格,与空格相邻的棋子可以移到空格中。要求解决的问题是:给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后,状态就会发生改变。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。(逆序数)我们把每个9宫格横向展开,如第一个9,我们把左边数大于右边数的组数称为这个九宫格的逆序数,显然9的逆序数为0;考虑横向平移,那么逆序数的增量为2或0或-2;纵向平移,逆序数的增量为4或0或-4;但9的逆序数为奇数。所以9是无解的情况。由此也可以类推当将9宫格展开后,如果数据序列的逆序数为奇数,则此数据序列对应的九宫格是无解的。:Queueopen=newQueue();存放待扩展的节点List:List<Bfstr>closed=newList<Bfstr>();存放已被扩展过的节点ArrayListmap=newArrayList();//存放答案HashTale:Hashtabletable=newHashtable();:从图中某顶点v出发,逐层对节点进行拓展,并考察是否为目标节点,在第n层节点没有全部扩展并考察前,不对第n+1层节点进行扩展。对九宫重排问题,即构造广度优先搜索树,从初始状态,利用广度优先搜索算法逐步找到目标状态的节点。,每个节点存放在Bfstr结构体中的字符now中,从第一行开始从左往右给九宫格标号0……8,字符串now元素下标代表格子位置,而now数组中对应数组的值代表九宫格中存放的数码,用数值9代表空格。**********.:(1)把初始节点S0放入OPEN表。(2)如果OPEN表为空,则问题无解,退出。(3)把OPEN表的第一个节点(记为节点n)取出放入CLOSE表。(4)考察节点n是否为目标节点。若是,则求得了问题的解,退出。(5)若节点n不可扩展,则转第2步。(6)扩展节点n,将其子节点放入OPEN表的尾部,并为每一个子节点都配置指向父节点的指针,然后转第2步。扩展fun():(1)取open中第一个节点a加入到closed中(2)找到a[9]中值为9(空格)的位置i;(3)当open中元素个数不为0时,循环执行(3)到()(状态),并加入到closed中,对这个状态扩展;、3列,向左移动得到新状态;新状态不是目标状态,就加入open中;新状态是目标状态,就加入closed中,编号加1,结束算法;、3行,向上移动得到新状态新状态不是目标状态,就加入open中,新状态是目标状态,就加入closed中,编号加1,结束算法;、2列,向右移动得到新状态新状态不是目标状态,就加入open中,新状态是目标状态,就加入closed中,编号加1,结束算法;,向下移动得到新状态新状态不是目标状态,就加入open中,新状态是目标状态,就加入closed中,编号加1,结束算法;?YNn=0,初始节点送入open队列搜索失败,算法结束,从open中取出节点到closed中并编号加1扩展编号为n的节点,*算法队列:Queueopen=newQueue();存放待扩展的节点List:List<Bfstr>closed=newList<Bfstr>();存放已被扩展过的节点ArrayListmap=newArrayList();//存放答案HashTale:Hashtabletable=newHashtable();,一定能找到它,而A*中评估函数f*(n)=g*(n)+f*(n)保证路径存在时,一定能找到。算法A中,g(n)和