九宫格问题人工智能应用技术.doc

实验报告
课程名称《人工智能应用技术》
实验项目搜索技术程序设计
实验仪器微机
学院信息管理学院
专业信息管理与信息系统
班级/学号
学生姓名
实验日期
成绩
指导教师杨孔雨
XXXXXXXX
信息管理学院
(课程上机)实验报告
实验课程名称:《人工智能应用技术》专业: 信息管理与信息系统班级: XXX 学号: 2010012020 姓名: XXX 成绩:
实验名称
搜索技术程序设计
实验地点
计算中心
实验时间
2012-5-11
实验目的:
通过实验可以使学生面向实际的应用问题而着手进行设计,提高学生的动手能力,丰富其软件设计经验,为学生今后从事人工智能应用技术的设计工作打下基础。本实验使学生掌握搜索技术中重点方法的程序设计能力,加强对搜索技术主要技术的理解,提高对相关人工智能技术的认识。
实验内容:(任选一题)
1、传教士和野人问题(The Missionaries and Cannibals Problem)。寻找过河方案。
2、重排九宫问题。如书139页图6-12所示,在3´3的方格棋盘上,分别放置标有数字1、2、3、4、5、6、7、8共8个棋子,初始状态为S0,目标状态为Sg。要求寻找出从初始状态到达目标状态的搜索路径。
分别用宽度搜索或深度搜素和一种启发式搜索实现寻找该问题搜索路径的程序设计。
实验要求:
(1)认真阅读教材相关实例求解步骤,作为实验内容,并准备好实验预习报告;
(2)要求须课前编好程序代码;
(3)独立完成实验过程,认真回答教师的随堂提问。并做好相关实验记录。
实验准备:(画出求解问题的程序流程图和相关数据结构)
广度优先搜索的基本思想:
从初始节点S0开始,逐层地对节点进行扩展,并考察它是否为目标节点。在第n层的节点没有全部扩展并考察之前,不对第n+1层的节点进行扩展。
OPEN表中节点总是按进入的先后顺序排列,先进入的节点排在前面,后进入的排在后面。
算法描述:
1. 把初始节点S0放入OPEN表。
2. 如果OPEN表为空,则问题无解,退出。
3. 把OPEN表的第一个节点(记为节点n)取出放入CLOSE表。
4. 考察节点n是否为目标节点。若是,则求得了问题的解,退出。
5. 若节点n不可扩展,则转第2步。
6. 扩展节点n,将其子节点放入OPEN表的尾部,并为每一个子节点都配置指向父节点的指针,然后转第2步。
A*搜索:
如果一般搜索过程满足如下限制,则它就称为A*算法:
(1) 把OPEN表中的节点按估价函数:
f(x)=g(x)+h(x)
f(x)的值从小至大进行排序(一般搜索过程的第7步)。
(2) g(x)是从初始节点S0到节点x的路径的代价,g(x)是对g*(x)的估计,g(x)>0。
(3) h(x)是h*(x)的下界,即对所有的x均有:h(x)≤h*(x)。
其中,g*(x)是从初始节点S0到节点x的最小代价;h*(x)是从节点x到目标节点的最小代价。
算法描述:
1. 把初始节点S0放入OPEN表,并建立目前只包含S0的图,记为G;
2. 检查OPEN表是否为空,若为空则问题无解,退出;
3. 把OPEN表的第一个节点取出放入CLOSE表,并计该节点为n;
4. 考察节点n是否为目