人工智能导论实验报告(学生)

实用

《人工智能导论》上机实验

八数码问题求解

专业班级： 姓 名： 学 号： 指导教师：

实用

基于人工智能的状态空间搜索策略研究

——八数码问题求解

一、实验软件

VC6.0 编程语言或其它编程语言

二、实验目的

1. 熟悉人工智能系统中的问题求解过程；

2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3. 熟悉对八数码问题的建模、求解及编程语言的应用。

三、需要的预备知识

1. 熟悉VC6.0 编程语言；

2. 熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法；

3. 熟悉计算机语言对常用数据结构如链表、队列等的描述应用； 4. 熟悉计算机常用人机接口设计。 四、实验数据及步骤

1. 实验内容

八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。

例如：

图1 八数码问题示意图

请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或 任选一种启发式搜索方法（A 算法或 A* 算法）编程求解八数码问题（初始状态任选），并对实验结果进行分析，得出合理的结论。

2. 实验步骤

（1）分析算法基本原理和基本流程；

（2）确定对问题描述的基本数据结构，如 Open 表和 Closed 表等； （3）编写算符运算、目标比较等函数； （4）编写输入、输出接口； （5）全部模块联调；

实用

（6）撰写实验报告。

五、实验报告要求

所撰写的实验报告必须包含以下内容： 1. 算法基本原理和流程框图； 2. 基本数据结构分析和实现；

3. 编写程序的各个子模块，按模块编写文档，含每个模块的建立时间、功能、输入输出参数意义和与其它模块联系等；

4. 程序运行结果，含使用的搜索算法及搜索路径等； 5. 实验结果分析； 6. 结论； 7. 提供全部源程序及软件的可执行程序。

六、操作实现

该设计采用启发式搜索方法编写程序。

该程序是自动产生一组随机数（0至8）填在3×3数组中，然后对该组随机数进行评估，距离目标状态的差距，具体内容如下：

1、启发函数设定

由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零，因此可以把数码不同的位置个数作为标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息来扩展节点的选择，减少搜索范围，提高搜索速度。

2、数据结构与算法设计 数码结构体

typedef struct node //八数码结构体 {

int form[N][N]; //数码组

int evalue; //评估值，差距

int udirec; //所屏蔽方向,防止往回推到上一状态,1上2下3左4右 struct node *parent; //父节点 }Graph;

Graph *Qu[MAX];//队列 Graph *St[MAX];//堆栈 搜索过程：（搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点））

a、把初始数码组压入队列；

b、从队列中取出一个数码组节点；

c、扩展子节点，即从上下左右四个方向移动空格，生成相应子节点：

d、对子节点数码组作评估，是否为优越节点，即其评估值是否小于等于其父节点加一，是则将其压入队，否则抛弃。

e、判断压入队的子节点数码组（优越点）的评估值，为零则表示搜索完成，退出搜索； f、跳到步骤2； 3、程序结构图

实用

4、程序流程框图 5、源程序 6、运行结果

实用

七、总结

以上算法对一些简单的八数码问题是解决了，但对于复杂的八数码问题还是无能为力。当中采用了屏蔽方向，虽然能有效地防止了往回搜索（节点的回推），但没能有效防止循环搜索，所以不能应用于复杂度较大的八数码问题。