基于人工智能的状态空间搜索策略研究 八数码问题求解 （一）实验软件 或编程语言或其它编程语言 （二）实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 （三）需要的预备知识 1. 熟悉 或编程语言或者其它编程语言； 2. 熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法； 3. 熟悉计算机语言对常用数据结构如链表、队列等的描述应用； 4. 熟悉计算机常用人机接口设计。 （四）实验数据及步骤 1. 实验内容 八数码问题：在 33的方格棋盘上，摆放着 1到8这八个数码，有 1个方格是 空的，其初始状态如图 1所示，要求对空格执行空格左移、空格右移、空格上移 和空格下移这四个操作使得棋盘从初始状态到目标状态。 254123 3784 186765 (a) 初始状态 (b) 目标状态 图 1 八数码问题示意图 请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或任选一种启 发式搜索方法（ A 算法或 A* 算法）编程求解八数码问题（初始状态任选）， 并对实验结果进行分析，得出合理的结论。 2. 实验步骤 （1）分析算法基本原理和基本流程； 程序采用宽度优先搜索算法，基本流程如下： 2 （2）确定对问题描述的基本数据结构，如 Open 表和 Closed 表等； 起 把s放 入 失 成 是 否open 表为空表 是 把 open表中的第一个节 点 n 移入 close 表 否 扩展节点n， 把其后裔放 入 open 表的前头 是 否 有 后 继 节点为目标节点 否 是 3 OPENCLOSED S A,B,CS B,C, D, E, FS,A C,D,E,F, GS,A, B D,E,F,G, HS,A,B, C E,F,G,H, I , JS,A,B,C, D F,G,H,I,J K, LS,A,B,C,D, E G,H,I,J K,L,M , NS,A,B,C,D,E, F H,I,J K,L,M,N,O,PS,A,B,C,D,E,F,G （3）编写算符运算、目标比较等函数； （4）编写输入、输出接口； （5）全部模块联调； （6）撰写实验报告。 （五）实验报告要求 所撰写的实验报告必须包含以下内容： 1. 算法基本原理和流程框图； 2. 基本数据结构分析和实现； 3. 编写程序的各个子模块，按模块编写文档，含每个模块的建立时间、功 能、输入输出参数意义和与其它模块联系等； 4. 程序运行结果，含使用的搜索算法及搜索路径等； 5. 实验结果分析； 6. 结论； 7. 提供全部源程序及软件的可执行程序。 附：实验报告格式 一、实验问题 二、实验目的 三、实验原理 四、程序框图 五、实验结果及分析 六、结论