内容发布更新时间 : 2024/10/13 2:18:55星期一 下面是文章的全部内容请认真阅读。
人工智能基础
大作业
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);