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

《八数码问题求解__实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、word格式实验报告一、实验问题八数码问题求解二、实验软件VC6.0编程语言或其它编程语言三、实验目的1.熟悉人工智能系统中的问题求解过程；2.熟悉状态空间的盲目搜索和启发式搜索算法的应用；3.熟悉对八数码问题的建模、求解及编程语言的应用。四、实验数据及步骤（一、）实验内容八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。2831231484765765(a)初始状态(b)目标状态图1八数

2、码问题示意图（二、）基本数据结构分析和实现1.结点状态我采用了structNode数据类型typedefstruct_Node{....word格式intdigit[ROW][COL];intdist;//distancebetweenonestateandthedestination一个表和目的表的距离intdep;//thedepthofnode深度//Sothecommentfunction=dist+dep.估价函数值intindex;//pointtothelocationofparent父节点的位置}Node;2.

3、发生器函数定义的发生器函数由以下的四种操作组成：(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=MAXDI

4、STANCE;(4)将当前状态的空格右移Nodenode_right;Assign(node_right,index);//向右扩展的节点intdist_right=MAXDISTANCE;通过定义结点状态和发生器函数，就解决了8数码问题的隐式图的生成问题。接下来就是搜索了。3.图的搜索策略经过分析，8数码问题中可采用的搜速策略共有：1.广度优先搜索、2.深度优先搜索、2.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索，一共五种。其中，广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发

5、式搜索法。实验时,采用了广度(宽度)优先搜索来实现。（三、）广度(宽度)优先搜索原理1.状态空间盲目搜索——宽度优先搜索其基本思想是，从初始节点开始，向下逐层对节点进形依次扩展，并考察它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面。其搜索过程如图（1）所示。....word格式SABCFDEGHIJ图2、宽度优先搜索示意图2.宽度优先算法如下：步1把初始结点S0放入OPEN表中步2若OPEN表

6、为空，则搜索失败，问题无解步3取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n步4若目标结点Sg=N，则搜索成功，问题有解步5若N无子结点，则转步2步6扩展结点N，将其所有子结点配上指向N的放回指针，依次放入OPEN表的尾部，转步23.宽度优先算法流程图 起始把S放入OPEN表Fangru否是OPEN是否为空表?失败....word格式把第一个节点n,从OPEN表移出,并把它放入CLOSED表扩展n,把它的后继节点放入OPEN表的末端,提供回到n的指针是否有任何后继节点为目标节点?否是成功图3、宽度优先算法流程

7、图4．8数码难题用宽度优先搜索所生成的搜索树如图4。搜索树上的所有节点都标记它们所对应的状态描述，每个节点旁边的数字表示节点扩展的顺序（按顺时针方向移动空格）。图中有26个节点，也就是源程序运行结果。2831047651So2831407652031847652830147652831647052345678910111213083214765023184765230184765283145760280143765283164750283164065283714065141516171819202112308476520321

8、4765283714605234180765283160754283064175283145706208143756....word格式2223242526123804765283714650283704615830214765883204765图4.八数码题宽度优先搜索树五