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

1、昆明理工大学信息工程与自动化学院学生实验报告（20142015学年第一学期）课程名称：人工智能导论开课实验室：年 月 日年级、专业、 班学 号姓名成绩实验项目 名称状态空间搜索实验一八数码问题求解指导 教师胡蓉教 师 评 语该同学是否了解实验原理：A.了解口 B.基本了解口 C.不了解该同学的实验能力：A.强 B.中等口 C.差该同学的实验是否达到要求： A.达到口 B.基本达到口 C.未达到实验报告是否规范：A.规范口 B.基本规范口 C.不规范实验过程是否详细记录：A.详细口 B. 一般 C.没有口教师签名：年月日、实验内容和要求八数码问题：在3X 3的方格棋盘上，摆放着1到8这八个数码，

2、有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移 和空格下移这四个操作使得棋盘从初始状态到目标状态。例如:283164705（a）初始状态|12|38r4目标状态(b)图1八数码问题示意图请任选一种盲目搜索算法（广度优先搜索或深度优先搜索） 或任选一种启发 式搜索方法（全局择优搜索，加权状态图搜索，A算法或A*算法）编程求解八数码问题（初始状态任选）。选择一个初始状态，画出搜索树，填写相应的OPEN 表和CLOSE表，给出解路径，对实验结果进行分析总结，得出结论。实验报告内容格式要求：XXXXXXXXXXX中文：宋体，小四；英文：Times NewRoma)、

3、实验目的1. 熟悉人工智能系统中的问题求解过程；2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；3. 熟悉对八数码问题的建模、求解及编程语言的应用。三、实验算法启发函数设定由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较， 其数码不同的位置个数在逐渐减 少，最后为零，因此可以把数码不同的位置个数作为标志一个节点到目标节点距2、数据结构与算法设计 数码结构体 typedef struct node int formNN;int evalue;int udirec;右/八数码结构体离远近的一个启发性信息，利用这个信息来扩展节点的选择，减

4、少搜索范围， 提 高搜索速度。/数码组/评估值，差距/所屏蔽方向 ,防止往回推到上一状态 ,1上 2下 3左 4struct node *parent;/父节点Graph;Graph *QuMAX;/ 队列Graph *StMAX;/ 堆栈搜索过程：（搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣 质节点）a把初始数码组压入队列；b、从队列中取出一个数码组节点；c、扩展子节点，即从上下左右四个方向移动空格，生成相应子节点：d、对子节点数码组作评估，是否为优越节点，即其评估值是否小于等于其 父节点加一，是则将其压入队，否则抛弃。e、判断压入队的子节点数码组（优越点）的评估值，为零则表

5、示搜索完成, 退出搜索；f、跳到步骤2；四、程序框图五、实验结果及分析采用深度优先搜索方式并简化搜索六、结论123804765Open 表01 22 3 42 4 5 6close 表00 10 1 3目标完成七、源程序及注释&运行结果/设计了搜索深度范围，防止队列内存越#include <stdio.h> 界#include <stdlib.h> #in clude <time.h>#defi ne N 3 II数码组大小#defi ne Max_Step 50 II最大搜索深度#defi ne MAX 50 typedef struct n od

6、e/ 八数码结构体int formNN;数码组int evalue;/ 评估值int udirect;/所屏蔽方向，防止往回推到上已状态，1上2下3左4右struct node *pare nt;父节点/ 打印数码组void Print(Graph *The_graph) _int i,j;if (The_graph=NULL)prin tf("图为空 n");elseprintf("n");for (i=0;i<N;i+)prin tf("|t");for (j=O;j<N;j+)prin tf("%dt&qu

7、ot;,The_graph->formij);遍历打印_prin tf("t|n");差距printf("|ttt差距 :%dt|n",The_graph->evalue);/显示printf("n");/ 评价函数int Evaluate(Graph *The_graph,Graph *End_graph)int valute=0;/ 差距数int i,j;for (i=0;i<N;i+)for (j=0;j<N;j+)if (The_graph->formij!=End_graph->formi

8、j)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;i<N;i+)/ 获取空格坐标 i,jfor (j=0;j<N;j+)if (The_graph->formij=0)HasGetBlank=1;br

9、eak ;if (HasGetBlank=1) break ;/printf(" 空格位置 :%d,%dn",i,j);t_i=i; t_j=j;/ 移动空格 switch (Direct)case 1:/ 上 t_i-;if (t_i<0)AbleMove=0; break ;case 2:/ 下 t_i+;if (t_i>=N)AbleMove=0; break ;case 3:/ 左 t_j-;if (t_j<0)AbleMove=0; break ;case 4:/ 右 t_j+;if (t_j>=N)AbleMove=0; break ;i

10、f (AbleMove=0)/ 不能移动则返回原节点return The_graph;if (CreatNew_graph=1)生成节点New_graph=(Graph *)malloc( sizeof (Graph);/ for (x=0;x<N;x+)for (y=0;y<N;y+)New_graph->formxy=The_graph->formxy;/ 复制数码组elseNew_graph=The_graph;/ 移动后 New_graph->formij=New_graph->formt_it_j; New_graph->formt_it_j

11、=0;/printf(" 移动产生的新图 :n"); /Print(New_graph);return New_graph;/ 搜索函数Graph *Search(Graph *Begin,Graph *End)Graph *g1,*g2,*g;intStep=0;/深度intDirect=0;/方向inti;intfront,rear;front=rear=-1;/ 队列初始化 g=NULL;rear+;/ 入队Qurear=Begin;while (rear!=front)/ 队列不空front+;/出队g1=Qufront;/printf("开始第 d个图:

12、n",front);/Print(g1);for (i=1;i<=4;i+)/ 分别从四个方向推导出新子节点 Direct=i;if (Direct=g1->udirect)/跳过屏蔽方向continue ;g2=Move(g1, Direct, 1);/移动数码组if (g2!=g1)/ 数码组是否可以移动/ 可以移动Evaluate(g2, End);/ 评价新的节点/printf("开始产生的第d个图:n",i);/Print(g2);if (g2->evalue<=g1->evalue+1)/是优越节点g2->paren

13、t=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;break ;elsefree(g2);/抛弃劣质节点g2=NULL;if (g!=NULL)/ 为 0 则搜

14、索完成if (g->evalue=0)break ;Step+;/ 统计深度if (Step>Max_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 (x=0;x<N;x+)for (y=0;y<N;y+)New_graph->

15、;formxy=The_graph->formxy;for (i=0;i<M;i+)Direct=rand()%4+1;/产生 1 4 随机数/printf("Direct:%dn",Direct);New_graph=Move(New_graph, Direct, 0); /Print(New_graph);New_graph->evalue=0;New_graph->udirect=0;New_graph->parent=NULL;return New_graph;int main ( int argc, const char * argv

16、)/ 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,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);/ Eva

17、luate(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 (to