人工智能导论：状态空间搜索实验—八数码问题求解

{
printf("---------------------\n");
for(i=0;i<N;i++)
{
printf("|\t");
for(j=0;j<N;j++)
{
printf("%d\t",The_graph->form[i][j]);//遍历打印
}
printf("\t|\n");
}
printf("|\t\t\t差距:%d\t|\n",The_graph->evalue);//差距显示
#include <stdlib.h>6、运行结果
#include <time.h>
#define N 3 //数码组大小
#define Max_Step 50 //最大搜索深度
#define MAX 50
typedefstructnode//八数码结构体
{
intform[N][N];//数码组
intevalue;//评估值
intudirect;//所屏蔽方向，防止往回推到上已状态，1上2下3左4右
structnode *parent;//父节点
/////////打印数码组
voidPrint(Graph *The_graph)
{
inti,j;
if(The_graph==NULL)
printf("图为空\n");
else
Graph *Qu[MAX];//队列
Graph *St[MAX];//堆栈
搜索过程：（搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点））
a、把初始数码组压入队列；
b、从队列中取出一个数码组节点；
c、扩展子节点，即从上下左右四个方向移动空格，生成相应子节点：
d、对子节点数码组作评估，是否为优越节点，即其评估值是否小于等于其父节点加一，是则将其压入队，否则抛弃。
printf("---------------------\n");
}
}
/////////评Leabharlann Baidu函数
intEvaluate(Graph *The_graph,Graph *End_graph)
{
intvalute=0;//差距数
inti,j;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
Graph *New_graph;//
intHasGetBlank=0;//是否获取空格位置
intAbleMove=1;//是否可移动
inti,j,t_i,t_j,x,y;
for(i=0;i<N;i++)//获取空格坐标i,j
{
for(j=0;j<N;j++)
{
if(The_graph->form[i][j]==0)
该同学的实验是否达到要求 ：A.达到□ B.基本达到□ C.未达到□
实验报告是否规范：A.规范□ B.基本规范□ C.不规范□
实验过程是否详细记录：A.详细□ B.一般 □C.没有 □
教师签名：
年 月 日
一、实验内容和要求
八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。
2、数据结构与算法设计
数码结构体
typedef struct node//八数码结构体
{
int form[N][N];//数码组
int evalue;//评估值，差距
int udirec;//所屏蔽方向,防止往回推到上一状态,1上2下3左4右
struct node *parent;//父节点
}Graph;
{
if(The_graph->form[i][j]!=End_graph->form[i][j])
{
valute++;
}
}
}
The_graph->evalue=valute;
returnvalute;
}
/////////移动数码组
Graph *Move(Graph *The_graph,intDirect,intCreatNew_graph)
昆明理工大学信息工程与自动化学院学生实验报告
（2014——2015学年第一学期）
课程名称：人工智能导论开课实验室： 年 月 日
年级、专业、班
学号
姓名
成绩
实验项目
名称
状态空间搜索实验—八数码问题求解
指导
教师
胡蓉
教师评语
该同学是否了解实验原理：A.了解□ B.基本了解□ C.不了解□ 该同学的实验能力：A.强 □B.中等 □C.差 □
实验报告内容格式要求：XXXXXXXXXXXX（中文：宋体，小四；英文：Times New Roman）。
二、实验目的
1. 熟悉人工智能系统中的问题求解过程；
2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；
3. 熟悉对八数码问题的建模、求解及编程语言的应用。
三、实验算法
启发函数设定
由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零，因此可以把数码不同的位置个数作为标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息来扩展节点的选择，减少搜索范围，提高搜索速度。
{
HasGetBlank=1;
break;
}
}
if(HasGetBlank==1)
break;
}
//printf("空格位置:%d,%d\n",i,j);
t_i=i;
t_j=j;
//移动空格
switch(Direct)
{
case1://上
t_i--;
if(t_i<0)
AbleMove=0;
e、判断压入队的子节点数码组（优越点）的评估值，为零则表示搜索完成，退出搜索；
f、跳到步骤2；
四、程序框图
五、实验结果及分析
采用深度优先搜索方式并简化搜索
六、结论
Open表close表
0
1 2 0
2 3 4 0 1
2 4 5 6 0 1 3目标完成
七、源程序及注释
#include <stdio.h>} //设计了搜索深度范围，防止队列内存越界
例如：
2
8
3
1
2
3
1
6
4
8
4
7
0
5
7
6
5
(a) 初始状态 (b) 目标状态
图1 八数码问题示意图
请任选一种盲目搜索算法（广度优先搜索或深度优先搜索）或任选一种启发式搜索方法（全局择优搜索，加权状态图搜索，A算法或A* 算法）编程求解八数码问题（初始状态任选）。选择一个初始状态，画出搜索树，填写相应的OPEN表和CLOSED表，给出解路径，对实验结果进行分析总结，得出结论。