人工智能导论：状态空间搜索实验—八数码问题求解

昆明理工大学信息工程与自动化学院学生实验报告 （ 2 0 1 4 —— 2 0 1 5 学年 第 一 学期 ） 课程名称：人工智能导论 开课实验室： 年 月 日 年级、专业、班 学号 姓名 成绩 实验项目 名称 状态空间搜索实验—八数码问题求解 指导 教师 胡蓉 教师评语 该同学是否了解实验原理： A.了解□ B.基本了解□ C.不了解□ 该同学的实验能力： A.强 □ B.中等 □ C.差 □ 该同学的实验是否达到要求 ： A.达到□ B.基本达到□ C.未达到□ 实验报告是否规范： A.规范□ B.基本规范□ C.不规范□ 实验过程是否详细记录： A.详细□ B.一般 □ C.没有 □ 教师签名： 年 月 日 一、实验内容和要求 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 例如： 2 8 3 1 2 3 1 6 4 8 4 7 0 5 7 6 5 (a) 初始状态 (b) 目标状态 图 1 八数码问题示意图 请任选一种盲目搜索算法（广度优先搜索或深度优先搜索）或任选一种启发式搜索方法（全局择优搜索，加权状态图搜索，A 算法或 A * 算法）编程求解八数码问题（初始状态任选）。选择一个初始状态，画出搜索树，填写相应的OPEN表和CLOSED表，给出解路径 ，对实验结 果 进 行分 析 总 结 ，得出结 论。 实验报告内 容 格式要求：XXXXXXXXXXXX（中文 ：宋 体 ，小 四； 英 文 ：Times New Roman）。 二、实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 三、实验算法 启发函数设定 由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零，因此可以把数码不同的位置个数作为标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息来扩展节点的选择，减少搜索范围，提高搜索速度。 2、数据结构与算法设计 数码结构体 typedef struct node //八数码结构体 { int form[N][N]; //数码组 int evalue; //评估值，差距 int udirec; //所屏蔽方向,防止往回推到上一状态,1 上 2 下3 左4右 struct node *paren...