人工智能实验报告 题目：用A*搜索求解n数码问题 姓名： 班级： 学号： 学院：计算机科学与信息 专业：计算机科学与技术 指导教师： 日期：2011 年 12 月 6 日 2 一、实验目的： 熟悉和掌握深度搜索，宽度搜索，启发式搜索的定义、估价函数和算法过程，并利用深度搜索，宽度搜索，A*算法求解 8 数码难题，理解求解流程和搜索顺序。 二、实验原理： 1、A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择 f 值最小的节点作为扩展节点。因此，f 是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点 n 的估价函数值为两个分量：从起始节点到节点n 的代价以及从节点 n 到达目标节点的代价。 2、深度优先搜索(breadth-first search)的定义：首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后 n 步，而且保持n 尽可能小。 3、宽度优先搜索(breadth-first search)的定义：如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-first search). 三、实验内容： ① 以 8数码为例实际求解 A*算法。 ② 画出 A*算法求解框图。 ③ 分析估价函数对搜索算法的影响。 ④ 分析 A*算法的特点。 ⑤ 宽度求 8 数码 ⑥ 深度求 8 数码 四、实验描述及要求： 4.1 维护搜索图的 A *算法 （1）创建一个搜索图 G，只包含开始节点 n0。把 n0 放到 OPEN 表中。 （2）创建 CLOSED 表：初始为空。 （3）如果 OPEN 表空，算法以失败退出。 （4）选 OPEN 表中的首节点，从 OPEN 表中移走，放到 CLOSED 表中。称该节点为 n。 （5）如果 n 是目标节点，算法以成功退出：通过跟踪沿着图 G 中从 n 指向 n0 的指针获得解。 （6）扩展节点 n，产生后继集合 M，M 不包含图 G 中 n 的祖先。把 M 的成员作为 n的后继安装到图 G 中。把 M 的成员放到 OPEN 表中。 （7）建立从 M 的没有在 G 中出现过的成员到 n 的指针。对 M 的已经在 OPEN 表或CLOSED 表中的每个成员 m，如果目前发现的到达 m 的最佳路径经过 n，则把它的指针改为指向 n。对 M 的每个已经在 CLOSED 表中的成员，修改它在图 G ...
