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

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

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

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

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

5、的评估值，为零则表示搜索完成，退出搜索； f、跳到步骤2；四、程序框图起始把s放入open表失败成功是否open表为空表？是把open表中的第一个节点n移入close表否扩展节点n，把其后裔放入open表的前头是否有后继节点为目标节点？否是 五、实验结果及分析采用深度优先搜索方式 并简化搜索六、结论813204765 (2)103824765 (3)813024 （0）765813024765 (4)123804765 (5)013824765 (1)Open表 close表01 2 02 3 4 0 12 4 5 6 0 1 3 目标完成七、源程序及注释#include <s

6、tdio.h>   /设计了搜索深度范围，防止队列内存越界#include <stdlib.h>  6、运行结果#include <time.h>    #define N 3 /数码组大小  #define Max_Step 50 /最大搜索深度  #define MAX 50    typedef

7、0;struct node/八数码结构体        int formNN;/数码组      int evalue;/评估值      int udirect;/所屏蔽方向，防止往回推到上已状态，1上2下3左4右      struct node *parent;/父节点&#

8、160; /打印数码组  void Print(Graph *The_graph)        int i,j;      if(The_graph=NULL)          printf("图为空n");     

9、0;else                printf("-n");          for(i=0;i<N;i+)                &

10、#160;       printf("|t");              for(j=0;j<N;j+)                     &#

11、160;          printf("%dt",The_graph->formij);/遍历打印                            printf("t|n&q

12、uot;);                    printf("|ttt差距:%dt|n",The_graph->evalue);/差距显示          printf("-n");     &#

13、160;      /评价函数  int Evaluate(Graph *The_graph,Graph *End_graph)        int valute=0;/差距数      int i,j;      for(i=0;i<N;i+) &#

14、160;              for(j=0;j<N;j+)                        if(The_graph->formij!=End_graph->formij)

15、0;                               valute+;                 &#

16、160;                  The_graph->evalue=valute;      return valute;      /移动数码组  Graph *Move(Graph *The_graph,int Dir

17、ect,int CreatNew_graph)        Graph *New_graph;/      int HasGetBlank=0;/是否获取空格位置      int AbleMove=1;/是否可移动      int i,j,t_i,t_j,x,y; 

18、0;          for(i=0;i<N;i+)/获取空格坐标i,j                for(j=0;j<N;j+)                

19、        if(The_graph->formij=0)                                HasGetBlank=1;   &#

20、160;              break;                                  if

21、(HasGetBlank=1)              break;            /printf("空格位置:%d,%dn",i,j);            t_i=i; &#

22、160;    t_j=j;            /移动空格      switch(Direct)                case 1:/上     

23、;         t_i-;              if(t_i<0)                  AbleMove=0;    &

24、#160;         break;          case 2:/下              t_i+;            

25、  if(t_i>=N)                  AbleMove=0;              break;          case&#

26、160;3:/左              t_j-;              if(t_j<0)                  

27、;AbleMove=0;              break;          case 4:/右              t_j+;      

28、;        if(t_j>=N)                  AbleMove=0;              break;     

29、;                           if(AbleMove=0)/不能移动则返回原节点                return The_

30、graph;            if(CreatNew_graph=1)                New_graph=(Graph *)malloc(sizeof(Graph);/生成节点         &#

31、160;for(x=0;x<N;x+)                        for(y=0;y<N;y+)                   &#

32、160;            New_graph->formxy=The_graph->formxy;/复制数码组                             &#

33、160;       else                New_graph=The_graph;            /移动后      New_graph->formij=N

34、ew_graph->formt_it_j;      New_graph->formt_it_j=0;      /printf("移动产生的新图:n");      /Print(New_graph);      return New_graph;     

35、0;/搜索函数  Graph *Search(Graph *Begin,Graph *End)        Graph *g1,*g2,*g;      int Step=0;/深度      int Direct=0;/方向      int i

36、;      int front,rear;      front=rear=-1;/队列初始化      g=NULL;      rear+;/入队      Qurear=Begin;      while(rear!=fr

37、ont)/队列不空                front+;/出队          g1=Qufront;          /printf("开始第%d个图:n",front);   

38、;       /Print(g1);          for(i=1;i<=4;i+)/分别从四个方向推导出新子节点                        Direct=i

39、;              if(Direct=g1->udirect)/跳过屏蔽方向                  continue;           

40、   g2=Move(g1, Direct, 1);/移动数码组                            if(g2!=g1)/数码组是否可以移动         &

41、#160;                      /可以移动                  Evaluate(g2, End);/评价新的节点   &#

42、160;              /printf("开始产生的第%d个图:n",i);                  /Print(g2);         

43、60;        if(g2->evalue<=g1->evalue+1)                                   &#

44、160;    /是优越节点                      g2->parent=g1;                   

45、60;  /移动空格                      switch(Direct)/设置屏蔽方向，防止往回推                    &

46、#160;                           case 1:/上                    

47、;          g2->udirect=2;                              break;      

48、                    case 2:/下                           

49、0;  g2->udirect=1;                              break;              

50、;            case 3:/左                              g2->udirect=4;  

51、0;                           break;                     

52、0;    case 4:/右                              g2->udirect=3;          

53、60;                   break;                             

54、60;                                            rear+;    

55、60;                 Qurear=g2;/存储节点到待处理队列                      if(g2->evalue=0)/为0则搜索完成  

56、60;                                             g=g2;   

57、0;                      /i=5;                          break

58、;                                                  

59、;        else                                        free(g2

60、);/抛弃劣质节点                      g2=NULL;                         &

61、#160;                                                 &

62、#160;if(g!=NULL)/为0则搜索完成                        if(g->evalue=0)                   

63、             break;                                    

64、        Step+;/统计深度          if(Step>Max_Step)                        break;  

65、;                    return g;      /初始化一个八数码结构体  Graph *CR_BeginGraph(Graph *The_graph)        srand(uns

66、igned)time(0);      int M=10;/随机移动步数      int Direct;      int i,x,y;      Graph *New_graph;      New_graph=(Graph *)malloc(s

67、izeof(Graph);      for(x=0;x<N;x+)                for(y=0;y<N;y+)                    

68、;    New_graph->formxy=The_graph->formxy;                      for(i=0;i<M;i+)              

69、;  Direct=rand()%4+1;/产生14随机数          /printf("Direct:%dn",Direct);          New_graph=Move(New_graph, Direct, 0);         &

70、#160;/Print(New_graph);                  New_graph->evalue=0;      New_graph->udirect=0;      New_graph->parent=NULL;    

71、        return New_graph;      int main (int argc, const char * argv)              / insert code here.

72、60;     /*     Graph Begin_graph=         2,8,3,1,6,4,0,7,5,0,0,NULL               Graph Begin_graph=   &

73、#160;     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  

74、0;       */            /目标数码组      Graph End_graph=          1,2,3,8,0,4,7,6,5,0,0,NULL     

75、60;            /初始数码组      Graph *Begin_graph;      Begin_graph=CR_BeginGraph(&End_graph);/随机产生初始数码组      Evaluate(Begin_graph, &End_graph);/对初始的数码组评价      printf("初始数码组:n");      Print(Begin_graph);      printf("目标数码组:n");