1、實驗一：八數碼游戲問題一、八數碼游戲問題簡介 九宮排字問題（又稱八數碼問題）是人工智能當中有名的難題之一。問題是在 3×3方格盤上，放有八個數碼，剩下第九個為空，每一空格其上下左右的數碼可移至空格。問題給定初始位置和目標位置，要求通過一系列的數碼移動，將初始位置轉化為目標位置。 2 8 31 2 31 6 48 47 57 6 5 （a）初始狀態 （b）目標狀態 圖 八數碼游戲 二、實驗目的  1. 熟悉人工智能系統中的問題求解過程；  2. 熟悉狀態空間的盲目搜索和啟發式搜索算法的應用； 3. 

2、;熟悉對八數碼問題的建模、求解及編程語言的應用。三、實驗的思路八數碼問題：在3×3的方格棋盤上，擺放著1到8這八個數碼，有1個方格是空的，其初始狀態如圖1所示，要求對空格執行空格左移、空格右移、空格上移和空格下移這四個操作使得棋盤從初始狀態到目標狀態。例如：28312316484705765(a) 初始狀態 (b) 目標狀態圖1 八數碼問題示意圖1. 啟發函數設定 由八數碼問題的部分狀態圖可以看出，從初始節點開始，在通向目標節點的路徑上，各節點的數碼格局同目標節點相比較，其數碼不同的位置個數在逐漸減少，最后為零，因此可以把數碼不同的位置個數作為標志一個節點到目標節點距離遠近的一個啟發

3、性信息，利用這個信息來擴展節點的選擇，減少搜索范圍，提高搜索速度。2. 搜索過程：（搜索采用廣度搜索方式，利用待處理隊列輔助，逐層搜索（跳過劣質節點）a、把初始數碼組壓入隊列；b、從隊列中取出一個數碼組節點；c、擴展子節點，即從上下左右四個方向移動空格，生成相應子節點：d、對子節點數碼組作評估，是否為優越節點，即其評估值是否小于等于其父節點加一，是則將其壓入隊，否則拋棄。 e、判斷壓入隊的子節點數碼組（優越點）的評估值，為零則表示搜索完成，退出搜索； f、跳到步驟2；四、數據結構的設計數碼結構體typedef struct node /八數碼結構體int formNN; /數碼組int eva

4、lue; /評估值，差距int udirec; /所屏蔽方向,防止往回推到上一狀態,1上2下3左4右struct node *parent; /父節點Graph;Graph *QuMAX;/隊列Graph *StMAX;/堆棧起始把s放入open表失敗成功是否open表為空表？是把open表中的第一個節點n移入close表否擴展節點n，把其后裔放入open表的前頭是否有后繼節點為目標節點？否是 五、實驗過程及代碼#include <stdio.h> /設計了搜索深度范圍，防止隊列內存越界#include <stdlib.h> #include <time.h>

5、; #define N 3 /數碼組大小 #define Max_Step 50 /最大搜索深度 #define MAX 50 typedef struct node/八數碼結構體 int formNN;/數碼組 int evalue;/評估值 int udirect;/所屏蔽方向，防止往回推到上已狀態，1上2下3左4右 struct node *parent;/父節點 Graph;Graph *QuMAX; /隊列Graph *StMAX; /堆棧/打印數碼組 void Print(Graph *The_graph) int i,j; if(The_graph=NULL) printf(&q

6、uot;圖為空n"); else printf("-n"); for(i=0;i<N;i+) printf("|t"); for(j=0;j<N;j+) printf("%dt",The_graph->formij);/遍歷打印 printf("t|n"); printf("|ttt差距:%dt|n",The_graph->evalue);/差距顯示 printf("-n"); /評價函數 int Evaluate(Graph *The_gr

7、aph,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->formij) valute+; The_graph->evalue=valute; return valute; /移動數碼組 Graph *Move(Graph *The_graph,int Direct,int CreatNew_graph) Graph *New_graph; int HasGetBlank=0;/是否獲取空格位置

8、int AbleMove=1;/是否可移動 int i,j,t_i,t_j,x,y; for(i=0;i<N;i+)/獲取空格坐標i,j for(j=0;j<N;j+) if(The_graph->formij=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<0) AbleMove=0; break; case 2:/下 t_i+

9、; 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; if(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->formx

10、y=The_graph->formxy;/復制數碼組 else New_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; int Step=0;/深度 int Direct=0;/方向

11、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;i<=4;i+)/分別從四個方向推導出新子節點 Direct=i; if(Direct=g1->udirect)/跳過屏蔽方向 continue; g2=Move(g1, Direct, 1);/移動數碼組 if(g2!=g1

12、)/數碼組是否可以移動 /可以移動 Evaluate(g2, End);/評價新的節點 /printf("開始產生的第%d個圖:n",i); /Print(g2); if(g2->evalue<=g1->evalue+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

13、4:/右 g2->udirect=3; break; rear+; Qurear=g2;/存儲節點到待處理隊列 if(g2->evalue=0)/為0則搜索完成 g=g2; /i=5; break; else free(g2);/拋棄劣質節點 g2=NULL; if(g!=NULL)/為0則搜索完成 if(g->evalue=0) break; Step+;/統計深度 if(Step>Max_Step) break; return g; int main (int argc, const char * argv) / insert code here. Graph Be

14、gin_graph= 2,8,3,1,6,4,7,0,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 ; Evaluate(&Begin_graph, &End_graph);/對初始的數碼組評價 printf("初始數碼組:n"); Print(&Begin_graph

15、); 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("&l