内容发布更新时间 : 2024/12/23 22:31:01星期一 下面是文章的全部内容请认真阅读。
人工智能基础
大作业
2016.12.20
----八数码难题
:数学与计算机科学学院
学院
一、 实验名称
八数码难题的启发式搜索
二、 实验目的
八数码问题:在3×3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。
要求:1.熟悉人工智能系统中的问题求解过程;
2.熟悉状态空间的启发式搜索算法的应用;
3.熟悉对八数码问题的建模、求解及编程语言的应用。
三、 实验设备及软件环境
1. 2.
实验编程工具:VC++ 6.0 实验环境:Windows7 64位
四、 实验方法:启发式搜索
1.算法描述
1. 将S放入open表,计算估价函数f(s)
2. 判断open表是否为空,若为空则搜索失败,否则,将open表中的第一
个元素加入close表并对其进行扩展(每次扩展后加入open表中的元素按照代价的大小从小到大排序,找到代价最小的节点进行扩展) 注:代价的计算公式f(n)=d(n)+w(n).其中f(n)为总代价,d(n)为节点的度,w(n)用来计算节点中错放棋子的个数。
判断i是否为目标节点,是则成功,否则拓展i,计算后续节点f(j),利用f(j)对open表重新排序
2.算法流程图:
3.程序源代码:
# include
int i,cost,degree,exp,father; int a[3][3];
struct node *bef,*late; struct node *son;
}treenode;
int flag=0,count=1,num=0,i=0;
void set(treenode *s);
void cpynode(treenode *s1,treenode *s2);
void add1(treenode *s,treenode *open);