人工智能实验报告

昆明理工大学信息工程与自动化学院学生实验报告

（ 2014—— 2015 学年 第 一 学期 ）

课程名称：人工智能导论 开课实验室：信自楼234室 年 月 日 年级、专业、 学 姓名 成绩 班 号 实验项目 状态空间搜索实验—八数码问题求解 指导 名称 教师 该同学是否了解实验原理： 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 7 0 5

8 4 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 *parent; //父节点 }Graph;

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

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

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

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

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

e、判断压入队的子节点数码组（优越点）的评估值，为零则表示搜索完成，退出搜索；

f、跳到步骤2； 四、程序框图

起始 把s放入open表 是否open表为空表？ 否 把open表中的第一个节点n移入close表 是 失败 扩展节点n，把其后裔放入open表的前头 否 是 是否有后继节点为目标节点？ 成功

五、实验结果及分析

采用深度优先搜索方式 并简化搜索

六、结论

0 1 2 8 4 3 7 6 5 1 0 2 8 4 3 7 6 5 8 1 2 0 4 3 7 6 5 1 2 0 8 4 3 7 6 5 1 4 2 8 0 3 7 6 5 1 2 3 8 4 0 7 6 5 1 0 2 8 4 3 7 6 5 1 2 3 8 0 4 7 6 5

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库人工智能实验报告在线全文阅读。