《人工智能导论：状态空间搜索实验—八数码问题求解.docx》由会员分享，可在线阅读，更多相关《人工智能导论：状态空间搜索实验—八数码问题求解.docx（14页珍藏版）》请在三一文库上搜索。
1、昆明理工大学信息工程与自动化学院学生实验报告（20142015学年第一学期）课程名称：人工智能导论开课实验室：年 月 日年级、专业、 班学 号姓名成绩实验项目 名称状态空间搜索实验一八数码问题求解指导 教师胡蓉教 师 评 语该同学是否了解实验原理：A. 了解口 B.基本了解口 C.不了解口该同学的实验能力：A.强口 B.中等口 C.差口该同学的实验是否达到要求 ： A.达到口 B.基本达到口 C.未达到口 实验报告是否规范：A.规范匚B.基本规范匚C.不规范匚实验过程是否详细记录：A.详细口 B.一般 C.没有口教师签名：年月日、实验内容和要求八数码问题：在3X3的方格棋盘上，摆放着1到8这八
2、个数码，有1个方格是 空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移 和空格下移这四个操作使得棋盘从初始状态到目标状态。例如：283164705（a）初始状态图1八数码问题示意图请任选一种盲目搜索算法（广度优先搜索或深度优先搜索） 或任选一种启发式搜索方法（全局择优搜索，加权状态图搜索，A算法或A*算法）编程求解八数码问题（初始状态任选）。选择一个初始状态，画出搜索树，填写相应的OPEN 表和CLOSED,给出解路径，对实验结果进行分析总结，得出结论。实验报告内容格式要求：XXXXXXXXXXXX文：宋体，小四；英文：Times NewRoman。二、实验目的1. 熟悉
3、人工智能系统中的问题求解过程；2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；3. 熟悉对八数码问题的建模、求解及编程语言的应用。三、实验算法启发函数设定由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上， 各节点的数码格局同目标节点相比较， 其数码不同的位置个数在逐渐减少， 最后为零， 因此可以把数码不同的位置个数作为标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息来扩展节点的选择，减少搜索范围， 提高搜索速度。4. 数据结构与算法设计数码结构体typedef struct node/八数码结构体int formNN;int evalue;int udi
4、rec;/数码组/评估值，差距/所屏蔽方向,防止往回推到上一状态,1 上 2下 3左 4struct node *parent;/父节点Graph;Graph *QuMAX;/ 队列Graph *StMAX;/ 堆栈搜索过程： （搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点） ）a、把初始数码组压入队列；b、从队列中取出一个数码组节点；c、扩展子节点，即从上下左右四个方向移动空格，生成相应子节点：d、对子节点数码组作评估，是否为优越节点，即其评估值是否小于等于其 父节点加一，是则将其压入队，否则抛弃。e、判断压入队的子节点数码组（优越点）的评估值，为零则表示搜索完成,退出搜
5、索；f 、跳到步骤 2；四、程序框图把s放入open表是五、实验结果及分析采用深度优先搜索方式并简化搜索六、结论1 202 3 40 12 4 5 60 1 3目标完成close 表Open 表 0七、源程序及注释6、运行结果/设计了搜索深度范围，防止队列内存越#include 界#include #include # define N 3 /数码组大小# define Max_Step 50 /最大搜索深度# define MAX 50typedef struct node/ 八数码结构体int formNN;/ 数码组int evalue;/ 评估值int udirect;/所屏蔽方向，防
6、止往回推到上已状态，1上2下3左4右struct node *parent;/ 父节点/打印数码组void Print(Graph *The_graph) .int i,j; if (The_graph=NULL) printf(图为空 n);else printf(n);for (i=0;iN;i+) printf(|t); for (j=0;jformij);/遍历打 printf(t|n);printf(|ttt差距 :%dt|n,The_graph-evalue);/差距显示printf(n);/ 评价函数int Evaluate(Graph *The_graph,Graph *End
7、_graph) int valute=0;/ 差距数int i,j;for (i=0;iN;i+)for (j=0;jformij!=End_graph-formij)valute+;The_graph-evalue=valute;return valute;/ 移动数码组Graph *Move(Graph *The_graph, int Direct, int CreatNew_graph) Graph *New_graph;/int HasGetBlank=0;/ 是否获取空格位置int AbleMove=1;/ 是否可移动int i,j,t_i,t_j,x,y;for (i=0;iN;i
8、+)/ 获取空格坐标i,jfor (j=0;jformij=0)HasGetBlank=1;break ;if (HasGetBlank=1) break ;/printf( 空格位置 :%d,%dn,i,j);t_i=i;t_j=j;/ 移动空格switch (Direct)case 1:/ 上t_i-;if (t_i=N)AbleMove=0;break ;case 3:/ 左t_j-;if (t_j=N)AbleMove=0; break ;if (AbleMove=0)/ 不能移动则返回原节点return The_graph;if (CreatNew_graph=1)New_graph
9、=(Graph *)malloc(sizeof (Graph);/ 生成节点for (x=0;xN;x+)for (y=0;yformxy=The_graph-formxy;/ 复制数码组elseNew_graph=The_graph;/ 移动后New_graph-formij=New_graph-formt_it_j;New_graph-formt_it_j=0;/printf( 移动产生的新图 :n);/Print(New_graph);return New_graph;/ 搜索函数Graph *Search(Graph *Begin,Graph *End)Graph *g1,*g2,*g
10、;int Step=0;/ 深度int Direct=0;/ 方向int i;int front,rear;front=rear=-1;/ 队列初始化g=NULL;rear+;/ 入队Qurear=Begin;while (rear!=front)/ 队列不空front+;/出队g1=Qufront;/printf(开始第 d个图:n,front);/Print(g1);for (i=1;iudirect)/跳过屏蔽方向continue ;g2=Move(g1, Direct, 1);/移动数码组if (g2!=g1)/ 数码组是否可以移动/可以移动Evaluate(g2, End);/评价新
11、的节点/printf(开始产生的第d个图:n,i);/Print(g2);if (g2-evalueevalue+1)/是优越节点g2-parent=g1;/移动空格switch (Direct)/ 设置屏蔽方向，防止往回推case 1:/ 上g2-udirect=2;break ;case 2:/ 下g2-udirect=1;break ;case 3:/ 左g2-udirect=4;break ;case 4:/ 右g2-udirect=3;break ;rear+;Qurear=g2;/存储节点到待处理队列if (g2-evalue=0)/ 为 0 则搜索完成g=g2;/i=5;brea
12、k ;elsefree(g2);/抛弃劣质节点g2=NULL;if (g!=NULL)/ 为 0 则搜索完成if (g-evalue=0) break ;Step+;/ 统计深度 if (StepMax_Step) break ;return g;/ 初始化一个八数码结构体Graph *CR_BeginGraph(Graph *The_graph)srand(unsigned)time(0);int M=10;/ 随机移动步数int Direct;int i,x,y;Graph *New_graph;New_graph=(Graph *)malloc( sizeof (Graph); for
13、(x=0;xN;x+)for (y=0;yformxy=The_graph-formxy;for (i=0;ievalue=0;New_graph-udirect=0;New_graph-parent=NULL;return New_graph;int main ( int argc, const char * argv)/ insert code here./*Graph Begin_graph= 2,8,3,1,6,4,0,7,5,0,0,NULL;Graph Begin_graph= 2,8,3,1,0,4,7,6,5,0,0,NULL;Graph Begin_graph= 2,0,1,
14、4,6,5,3,7,8,0,0,NULL;*/ 目标数码组Graph End_graph= 1,2,3,8,0,4,7,6,5,0,0,NULL;/ 初始数码组Graph *Begin_graph;Begin_graph=CR_BeginGraph(&End_graph);/ 随机产生初始数码组Evaluate(Begin_graph, &End_graph);/对初始的数码组评价printf(初始数码组:n);Print(Begin_graph);printf(目标数码组:n);Print(&End_graph);Graph *G,*P;int top=-1;/ 图搜索G=Search(Begin_graph, &End_graph);/ 打印if (G)(/把路径倒序P=G;/压栈while (P!=NULL)( top+; Sttop=P; P=P-parent;printf(n);/ 弹栈打印while (top-1)( P=Sttop; top-;Print(P);printf(n); else(printf(搜索不到结果,深度为dn,Max_Step);/设计搜索深度范围主要是防止队列内存越界return 0;