人工智能導(dǎo)論：狀態(tài)空間搜索實(shí)驗(yàn)—八數(shù)碼問(wèn)題求解

1、昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院學(xué)生實(shí)驗(yàn)報(bào)告（ 2014 2015 學(xué)年 第 一 學(xué)期 ）課程名稱：人工智能導(dǎo)論 開(kāi)課實(shí)驗(yàn)室： 年 月 日年級(jí)、專業(yè)、班學(xué)號(hào)姓名成績(jī)實(shí)驗(yàn)項(xiàng)目名稱狀態(tài)空間搜索實(shí)驗(yàn)八數(shù)碼問(wèn)題求解指導(dǎo)教師胡蓉教師評(píng)語(yǔ)該同學(xué)是否了解實(shí)驗(yàn)原理： A.了解 B.基本了解 C.不了解 該同學(xué)的實(shí)驗(yàn)?zāi)芰Γ?A.強(qiáng) B.中等 C.差 該同學(xué)的實(shí)驗(yàn)是否達(dá)到要求 ： A.達(dá)到 B.基本達(dá)到 C.未達(dá)到實(shí)驗(yàn)報(bào)告是否規(guī)范： A.規(guī)范 B.基本規(guī)范 C.不規(guī)范實(shí)驗(yàn)過(guò)程是否詳細(xì)記錄： A.詳細(xì) B.一般 C.沒(méi)有 教師簽名： 年 月 日一、實(shí)驗(yàn)內(nèi)容和要求八數(shù)碼問(wèn)題：在3×3的方格棋盤(pán)上，擺放著1到

2、8這八個(gè)數(shù)碼，有1個(gè)方格是空的，其初始狀態(tài)如圖1所示，要求對(duì)空格執(zhí)行空格左移、空格右移、空格上移和空格下移這四個(gè)操作使得棋盤(pán)從初始狀態(tài)到目標(biāo)狀態(tài)。例如：28312316484705765(a) 初始狀態(tài) (b) 目標(biāo)狀態(tài)圖1 八數(shù)碼問(wèn)題示意圖請(qǐng)任選一種盲目搜索算法（廣度優(yōu)先搜索或深度優(yōu)先搜索）或任選一種啟發(fā)式搜索方法（全局擇優(yōu)搜索，加權(quán)狀態(tài)圖搜索，A 算法或 A* 算法）編程求解八數(shù)碼問(wèn)題（初始狀態(tài)任選）。選擇一個(gè)初始狀態(tài)，畫(huà)出搜索樹(shù)，填寫(xiě)相應(yīng)的OPEN表和CLOSED表，給出解路徑，對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析總結(jié)，得出結(jié)論。實(shí)驗(yàn)報(bào)告內(nèi)容格式要求：XXXXXXXXXXXX（中文：宋體，小四；英文：Ti

3、mes New Roman）。二、實(shí)驗(yàn)?zāi)康?. 熟悉人工智能系統(tǒng)中的問(wèn)題求解過(guò)程；2. 熟悉狀態(tài)空間的盲目搜索和啟發(fā)式搜索算法的應(yīng)用；3. 熟悉對(duì)八數(shù)碼問(wèn)題的建模、求解及編程語(yǔ)言的應(yīng)用。三、實(shí)驗(yàn)算法啟發(fā)函數(shù)設(shè)定 由八數(shù)碼問(wèn)題的部分狀態(tài)圖可以看出，從初始節(jié)點(diǎn)開(kāi)始，在通向目標(biāo)節(jié)點(diǎn)的路徑上，各節(jié)點(diǎn)的數(shù)碼格局同目標(biāo)節(jié)點(diǎn)相比較，其數(shù)碼不同的位置個(gè)數(shù)在逐漸減少，最后為零，因此可以把數(shù)碼不同的位置個(gè)數(shù)作為標(biāo)志一個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)距離遠(yuǎn)近的一個(gè)啟發(fā)性信息，利用這個(gè)信息來(lái)擴(kuò)展節(jié)點(diǎn)的選擇，減少搜索范圍，提高搜索速度。2、數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)數(shù)碼結(jié)構(gòu)體typedef struct node /八數(shù)碼結(jié)構(gòu)體int for

4、mNN; /數(shù)碼組int evalue; /評(píng)估值，差距int udirec; /所屏蔽方向,防止往回推到上一狀態(tài),1上2下3左4右struct node *parent; /父節(jié)點(diǎn)Graph;Graph *QuMAX;/隊(duì)列Graph *StMAX;/堆棧搜索過(guò)程：（搜索采用廣度搜索方式，利用待處理隊(duì)列輔助，逐層搜索（跳過(guò)劣質(zhì)節(jié)點(diǎn)）a、把初始數(shù)碼組壓入隊(duì)列；b、從隊(duì)列中取出一個(gè)數(shù)碼組節(jié)點(diǎn)；c、擴(kuò)展子節(jié)點(diǎn)，即從上下左右四個(gè)方向移動(dòng)空格，生成相應(yīng)子節(jié)點(diǎn)：d、對(duì)子節(jié)點(diǎn)數(shù)碼組作評(píng)估，是否為優(yōu)越節(jié)點(diǎn)，即其評(píng)估值是否小于等于其父節(jié)點(diǎn)加一，是則將其壓入隊(duì)，否則拋棄。 e、判斷壓入隊(duì)的子節(jié)點(diǎn)數(shù)碼組（優(yōu)越點(diǎn)）

5、的評(píng)估值，為零則表示搜索完成，退出搜索； f、跳到步驟2；四、程序框圖起始把s放入open表失敗成功是否open表為空表？是把open表中的第一個(gè)節(jié)點(diǎn)n移入close表否擴(kuò)展節(jié)點(diǎn)n，把其后裔放入open表的前頭是否有后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？否是 五、實(shí)驗(yàn)結(jié)果及分析采用深度優(yōu)先搜索方式 并簡(jiǎn)化搜索六、結(jié)論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 目標(biāo)完成七、源程序及注釋#include <s

6、tdio.h>   /設(shè)計(jì)了搜索深度范圍，防止隊(duì)列內(nèi)存越界#include <stdlib.h>  6、運(yùn)行結(jié)果#include <time.h>    #define N 3 /數(shù)碼組大小  #define Max_Step 50 /最大搜索深度  #define MAX 50    typedef

7、0;struct node/八數(shù)碼結(jié)構(gòu)體        int formNN;/數(shù)碼組      int evalue;/評(píng)估值      int udirect;/所屏蔽方向，防止往回推到上已狀態(tài)，1上2下3左4右      struct node *parent;/父節(jié)點(diǎn)&#

8、160; /打印數(shù)碼組  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;      /評(píng)價(jià)函數(shù)  int Evaluate(Graph *The_graph,Graph *End_graph)        int valute=0;/差距數(shù)      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;      /移動(dòng)數(shù)碼組  Graph *Move(Graph *The_graph,int Dir

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

18、0;          for(i=0;i<N;i+)/獲取空格坐標(biāo)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;            /移動(dòng)空格      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)/不能移動(dòng)則返回原節(jié)點(diǎn)                return The_

30、graph;            if(CreatNew_graph=1)                New_graph=(Graph *)malloc(sizeof(Graph);/生成節(jié)點(diǎn)         &#

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

32、160;            New_graph->formxy=The_graph->formxy;/復(fù)制數(shù)碼組                             &#

33、160;       else                New_graph=The_graph;            /移動(dòng)后      New_graph->formij=N

34、ew_graph->formt_it_j;      New_graph->formt_it_j=0;      /printf("移動(dòng)產(chǎn)生的新圖:n");      /Print(New_graph);      return New_graph;     

35、0;/搜索函數(shù)  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;/隊(duì)列初始化      g=NULL;      rear+;/入隊(duì)      Qurear=Begin;      while(rear!=fr

37、ont)/隊(duì)列不空                front+;/出隊(duì)          g1=Qufront;          /printf("開(kāi)始第%d個(gè)圖:n",front);   

38、;       /Print(g1);          for(i=1;i<=4;i+)/分別從四個(gè)方向推導(dǎo)出新子節(jié)點(diǎn)                        Direct=i

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

40、   g2=Move(g1, Direct, 1);/移動(dòng)數(shù)碼組                            if(g2!=g1)/數(shù)碼組是否可以移動(dòng)         &

41、#160;                      /可以移動(dòng)                  Evaluate(g2, End);/評(píng)價(jià)新的節(jié)點(diǎn)   &#

42、160;              /printf("開(kāi)始產(chǎn)生的第%d個(gè)圖:n",i);                  /Print(g2);         

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

44、160;    /是優(yōu)越節(jié)點(diǎn)                      g2->parent=g1;                   

45、60;  /移動(dòng)空格                      switch(Direct)/設(shè)置屏蔽方向，防止往回推                    &

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;/存儲(chǔ)節(jié)點(diǎn)到待處理隊(duì)列                      if(g2->evalue=0)/為0則搜索完成  

56、60;                                             g=g2;   

57、0;                      /i=5;                          break

58、;                                                  

59、;        else                                        free(g2

60、);/拋棄劣質(zhì)節(jié)點(diǎn)                      g2=NULL;                         &

61、#160;                                                 &

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

63、             break;                                    

64、        Step+;/統(tǒng)計(jì)深度          if(Step>Max_Step)                        break;  

65、;                    return g;      /初始化一個(gè)八數(shù)碼結(jié)構(gòu)體  Graph *CR_BeginGraph(Graph *The_graph)        srand(uns

66、igned)time(0);      int M=10;/隨機(jī)移動(dòng)步數(shù)      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;/產(chǎn)生14隨機(jī)數(shù)          /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;       */            /目標(biāo)數(shù)碼組      Graph End_graph=          1,2,3,8,0,4,7,6,5,0,0,NULL     

75、60;            /初始數(shù)碼組      Graph *Begin_graph;      Begin_graph=CR_BeginGraph(&End_graph);/隨機(jī)產(chǎn)生初始數(shù)碼組      Evaluate(Begin_graph, &End_graph);/對(duì)初始的數(shù)碼組評(píng)價(jià)      printf("初始數(shù)碼組:n");      Print(Begin_graph);      printf("目標(biāo)數(shù)碼組:n");