八数码实验报告

利用人工智能技术解决八数码游戏问题 1．八数码游戏问题简介 九宫排字问题（又称八数码问题）是人工智能当中有名的难题之一。问题是在 3×3方格盘上，放有八个数码，剩下第九个为空，每一空格其上下左右的数码可移至空格。问题给

定初始位置和目标位置，要求通过一系列的数码移动，将初始位置转化为目标位置。 2．八数码游戏问题的状态空间法表示 ①建立一个只含有初始节点s0的搜索图g，把s0放入open表中 ②建立closed表，且置为空表 ③判断open表是否为空表，若为空，则问题无解，退出 ④选择open表中的第一个节点，把它从open表移出，并放入closed表中，将此节点记为节点n

⑤考察节点n是否为目标节点，若是，则问题有解，成功退出。问题的解就是沿着n到

s0的路径得到。若不是转⑥ ⑥扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合m，将m中的这些

节点作为n的后继节点加入图g中 ⑦对未在g中出现过的（open和closed表中未出现过的）集合m中的节点, 设置一个指向父节点n的指针，并把这些节点放入open表中；对于已在g中出现过的m中的节点，确定是否需要修改指向父节点的指针；对于已在g中出现过并已在closed表中的m中的节点，

确定是否需要修改通向他们后继节点的指针。 ⑧ 按某一任意方式或某种策略重排open表中节点的顺序 ⑨ 转③

3．八数码游戏问题的盲目搜索技术 宽度优先搜索： 1、定义

如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索

(breadth-first search)。 2、特点

这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。

3、宽度优先搜索算法

(1) 把起始节点放到open表中(如果该起始节点为一目标节点，则求得一个解答)。 (2) 如果open是个空表，则没有解，失败退出；否则继续。 (3) 把第一个节点(节点n)从open表移出，并把它放入closed的扩展节点表中。 (4) 扩展节点n。如果没有后继节点，则转向上述第(2)步。 (5) 把n的所有后继节点放到open表末端，并提供从这些后继节点回到n的指针。 (6) 如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。

流程图： 性质：

当问题有解时，一定能找到解。 当问题为单位消耗值，且问题有解时，一定能找到最优解。 算法与问题无关，具有通用性。 时间效率和空间效率都比较低。 深度优先搜索：

1、定义

在此搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。这

种盲目(无信息)搜索叫做深度优先搜索(depth-first search)。 2、特点

首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进

行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。 3、深度界限 为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。

4、深度优先搜索算法

(1) 把起始节点放到open表中(如果该起始节点为一目标节点，则求得一个解答)。 (2) 如果open是个空表，则没有解，失败退出；否则继续。 (3) 把第一个节点(节点n)从open表移出，并把它放入closed的扩展节点表中。 (4) 考察节点n是否为目标节点，若是，则找到问题的解，用回溯法求解路径，退出 （5）如果没有后继节点，则转向上述第(2)步。 (6) 扩展节点n，把n的所有后继节点放到open表前端，并提供从这些后继节点回到n

的指针。转向第(2)步。

流程图： 性质：

一般不能保证找到最优解。 当深度限制不合理时，可能找不到解。 最坏情况时，搜索空间等同于穷举。 …… 此处隐藏：4603字，全部文档内容请下载后查看。喜欢就下载吧 ……