八数码问答求解实验报告.doc

实验报告一、实验问题八数码问题求解二、、;;、求解及编程语言的应用。四、实验数据及步骤(一、)实验内容八数码问题:在3×3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。2831231484765765(a)初始状态(b)目标状态图1八数码问题示意图(二、){intdigit[ROW][COL];intdist;//distancebetweenonestateandthedestination一个表和目的表的距离intdep;//thedepthofnode深度//mentfunction=dist+;//pointtothelocationofparent父节点的位置}Node;:(1)将当前状态的空格上移Nodenode_up;Assign(node_up,index);//向上扩展的节点intdist_up=MAXDISTANCE;(2)将当前状态的空格下移Nodenode_down;Assign(node_down,index);//向下扩展的节点intdist_down=MAXDISTANCE;(3)将当前状态的空格左移Nodenode_left;Assign(node_left,index);//向左扩展的节点intdist_left=MAXDISTANCE;(4)将当前状态的空格右移Nodenode_right;Assign(node_right,index);//向右扩展的节点intdist_right=MAXDISTANCE;通过定义结点状态和发生器函数,就解决了8数码问题的隐式图的生成问题。接下来就是搜索了。,8数码问题中可采用的搜速策略共有:、、、、,一共五种。其中,广度优先搜索法是可采纳的,有界深度优先搜索法是不完备的,最好优先和局部择优搜索法是启发式搜索法。实验时,采用了广度(宽度)优先搜索来实现。(三、)广度(宽度)——宽度优先搜索其基本思想是,从初始节点开始,向下逐层对节点进形依次扩展,并考察它是否为目标节点,再对下层节点进行扩展(或搜索)之前,必须完成对当层的所有节点的扩展。再搜索过程中,未扩展节点表OPEN中的节点排序准则是:先进入的节点排在前面,后进入的节点排在后面。其搜索过程如图(1)所示。SABCFDEGHIJ图2、:步1把初始结点S0放入OPEN表中步2若OPEN表为空,则搜索失败,问题无解步3取OPEN表中最前面的结点N放在CLOSE表中,并冠以顺序编号n步4若目标结点Sg=N,则搜索成功,问题有解步5若N无子结点,则转步2步6扩展结点N,将其所有子结点配上指向N的放回指针,依次放入OPEN表的尾部, 起始把S放入OPEN表Fangru否是OPEN是否为空表?失败把第一个节点n,从OPEN表移出,并把它放入CLOSED表扩展n,把它的后继节点放入OPEN表的末端,提供回到n的指针是否有任何后继节点为目标节点?否是成功图3、。搜索树上的所有节点都标记它们所对应的状态描述,每个节点旁边的数字表示节点扩展的顺序(按顺时针方向移动空格)。图中有26个节点,也就是源程序运行结果。、实验结果及分析上机试验时,,经多次程序调试,最后得一下结果。此结果所得节点(状态图)很多,可知宽度优先搜索