人工智能實(shí)驗(yàn)報(bào)告-八數(shù)碼問題(共11頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)一 啟發(fā)式搜索算法姓名：徐維堅(jiān) 學(xué)號(hào)： 日期：2012/6/29一、實(shí)驗(yàn)?zāi)康模菏炀氄莆諉l(fā)式搜索算法及其可采納性。二、實(shí)驗(yàn)內(nèi)容：使用啟發(fā)式搜索算法求解8數(shù)碼問題。1) 編制程序?qū)崿F(xiàn)求解8數(shù)碼問題算法，采用估價(jià)函數(shù)，其中：是搜索樹中結(jié)點(diǎn)的深度；為結(jié)點(diǎn)的數(shù)據(jù)庫(kù)中錯(cuò)放的棋子個(gè)數(shù)；為結(jié)點(diǎn)的數(shù)據(jù)庫(kù)中每個(gè)棋子與其目標(biāo)位置之間的距離總和。2) 分析上述中兩種估價(jià)函數(shù)求解8數(shù)碼問題的效率差別，給出一個(gè)是的上界的的定義，并測(cè)試使用該估價(jià)函數(shù)是否使算法失去可采納性。三、實(shí)驗(yàn)原理：1. 問題描述：八數(shù)碼問題也稱為九宮問題。在33的棋盤，擺有八個(gè)棋子，每個(gè)棋子上標(biāo)有1至8的某一數(shù)字，不同

2、棋子上標(biāo)的數(shù)字不相同。棋盤上還有一個(gè)空格（以數(shù)字0來表示），與空格相鄰的棋子可以移到空格中。要求解決的問題是：給出一個(gè)初始狀態(tài)和一個(gè)目標(biāo)狀態(tài)，找出一種從初始轉(zhuǎn)變成目標(biāo)狀態(tài)的移動(dòng)棋子步數(shù)最少的移動(dòng)步驟。所謂問題的一個(gè)狀態(tài)就是棋子在棋盤上的一種擺法。解八數(shù)碼問題實(shí)際上就是找出從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)所經(jīng)過的一系列中間過渡狀態(tài)。2. 原理描述：2.1 有序搜索算法：（1）原理：在搜索過程中，OPEN表中節(jié)點(diǎn)按照其估價(jià)函數(shù)值以遞增順序排列，選擇OPEN表中具有最小估價(jià)函數(shù)值的節(jié)點(diǎn)作為下一個(gè)待擴(kuò)展的節(jié)點(diǎn)，這種搜索方法稱為有序搜索。在本例中，估價(jià)函數(shù)中的取節(jié)點(diǎn)深度，為節(jié)點(diǎn)n的狀態(tài)與目標(biāo)狀態(tài)之間錯(cuò)放的個(gè)數(shù)，即

3、函數(shù)。（2）算法描述： 把起始節(jié)點(diǎn)S放到OPEN表中，并計(jì)算節(jié)點(diǎn)S的； 如果OPEN是空表，則失敗退出，無解； 從OPEN表中選擇一個(gè)值最小的節(jié)點(diǎn)。如果有幾個(gè)節(jié)點(diǎn)值相同，當(dāng)其中有一個(gè)為目標(biāo)節(jié)點(diǎn)時(shí)，則選擇此目標(biāo)節(jié)點(diǎn)；否則就選擇其中任一個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn)； 把節(jié)點(diǎn)從 OPEN 表中移出，并把它放入 CLOSED 的已擴(kuò)展節(jié)點(diǎn)表中； 如果是個(gè)目標(biāo)節(jié)點(diǎn)，則成功退出，求得一個(gè)解； 擴(kuò)展節(jié)點(diǎn)，生成其全部后繼節(jié)點(diǎn)。對(duì)于的每一個(gè)后繼節(jié)點(diǎn)：計(jì)算；如果 既不在OPEN表中，又不在CLOCED表中，則用估價(jià)函數(shù)把它添入OPEN表中。從加一指向其父節(jié)點(diǎn)的指針，以便一旦找到目標(biāo)節(jié)點(diǎn)時(shí)記住一個(gè)解答路徑；如果已在OPEN表或C

4、LOSED表中，則比較剛剛對(duì)計(jì)算過的和前面計(jì)算過的該節(jié)點(diǎn)在表中的值。如果新的較小，則(I)以此新值取代舊值。(II)從指向，而不是指向他的父節(jié)點(diǎn)。(III)如果節(jié)點(diǎn)在CLOSED表中，則把它移回OPEN表中。 轉(zhuǎn)向，即GOTO。（3） 算法流程圖：2.2啟發(fā)式搜索技術(shù)（1）原理啟發(fā)式搜索就是在狀態(tài)空間中的搜索對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估，得到最好的位置，再?gòu)倪@個(gè)位置進(jìn)行搜索直到目標(biāo)。這樣可以省略大量無謂的搜索路徑，提高了效率。在啟發(fā)式搜索中，對(duì)位置的估價(jià)是十分重要的。采用了不同的估價(jià)可以有不同的效果。（2）估價(jià)函數(shù)計(jì)算一個(gè)節(jié)點(diǎn)的估價(jià)函數(shù)，可以分成兩個(gè)部分：1、 已經(jīng)付出的代價(jià)（起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)

5、）；2、 將要付出的代價(jià)（當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)）。節(jié)點(diǎn)n的估價(jià)函數(shù)定義為從初始節(jié)點(diǎn)、經(jīng)過n、到達(dá)目標(biāo)節(jié)點(diǎn)的路徑的最小代價(jià)的估計(jì)值，即 = + 。是從初始節(jié)點(diǎn)到達(dá)當(dāng)前節(jié)點(diǎn)n的實(shí)際代價(jià)； 是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最佳路徑的估計(jì)代價(jià)，體現(xiàn)出搜索過程中采用的啟發(fā)式信息（背景知識(shí)），稱之為啟發(fā)函數(shù)。所占的比重越大，越趨向于寬度優(yōu)先或等代價(jià)搜索；反之，的比重越大，表示啟發(fā)性能就越強(qiáng)。本實(shí)驗(yàn)中我們使用函數(shù)，其值是節(jié)點(diǎn)n與目標(biāo)狀態(tài)節(jié)點(diǎn)相比較，每個(gè)錯(cuò)位棋牌在假設(shè)不受阻攔的情況下，移動(dòng)到目標(biāo)狀態(tài)相應(yīng)位置所需走步（移動(dòng)次數(shù)）的總和。顯然比更接近于，因?yàn)椴粌H考慮了錯(cuò)位因素，還考慮了錯(cuò)位的距離。（3） 算法描述：參考有序搜

6、索算法描述，基本相同。流程圖亦參考有序算法流程圖。4、 實(shí)驗(yàn)程序及其說明：1） int goalNN，struct Chessboard：試驗(yàn)中我定義goal數(shù)組為目標(biāo)狀態(tài)1,2,3,8,0,4,7,6,5。結(jié)構(gòu)體Chessboard記錄棋盤信息，其中變量pos數(shù)組坐標(biāo)記錄每個(gè)數(shù)碼a的位置，其值為數(shù)碼a。d表示該棋盤的深度，f為啟發(fā)函數(shù)值，move為父節(jié)點(diǎn)移動(dòng)到該節(jié)點(diǎn)的方式，以便在輸出時(shí)告訴用戶該如何移動(dòng)棋子知道目標(biāo)狀態(tài)。2）struct LNode：定義節(jié)點(diǎn)LNode結(jié)構(gòu)體，存放該節(jié)點(diǎn)狀態(tài)時(shí)的棋盤信息board，和指向父節(jié)點(diǎn)、下一節(jié)點(diǎn)的指針(*parent,*next)，以及標(biāo)記量flag值

7、為true時(shí)表示該節(jié)點(diǎn)是最佳路徑上的節(jié)點(diǎn)。3）int* Findzero(LNode* &Node)：為方便找到空格，我設(shè)計(jì)了找到該函數(shù)Findzero(*&Node)，以便找到當(dāng)前節(jié)點(diǎn)空格所在位置以利于接下來的程序執(zhí)行。返回值為空格所在的行和列。4） int Wrong(LNode *Node)和int pick(LNode *Node)：分別為函數(shù)和。5） LNode* extend(LNode *Node,int depth,int zero2,int moveflag,int Choose)樹形方式擴(kuò)展節(jié)點(diǎn)。Node為要擴(kuò)展的當(dāng)前節(jié)點(diǎn)，depth為當(dāng)前深度，zero存放該節(jié)點(diǎn)空格位置信

8、息，moveflag即擴(kuò)展節(jié)點(diǎn)的移動(dòng)方式，Choose為選擇函數(shù)還是。6） void InitList(LNode* &Open,LNode* &Close)和int ListInsert(List &L,LNode* NewNode)分別為表OPEN、CLOSE的創(chuàng)建和表的插入操作。7） LNode* Getminf(List &L)主要是實(shí)現(xiàn)從OPEN表中選擇一個(gè)值最小的節(jié)點(diǎn)。如果有幾個(gè)節(jié)點(diǎn)值相同，當(dāng)其中有一個(gè)為目標(biāo)節(jié)點(diǎn)時(shí)，則選擇此目標(biāo)節(jié)點(diǎn)；否則就選擇其中任一個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn)。5、 實(shí)驗(yàn)小結(jié)通過本次試驗(yàn)，我對(duì)啟發(fā)式搜索有了更加深入的了解。在實(shí)驗(yàn)中，通過對(duì)兩種啟發(fā)式搜索所擴(kuò)在的節(jié)點(diǎn)數(shù)來看，看來

9、比更加有效，能在復(fù)雜情況下求得更加優(yōu)質(zhì)的解，避免不必要的節(jié)點(diǎn)的擴(kuò)展。但是對(duì)于估價(jià)函數(shù)來說，它的定義趨向多元化，只是它的一個(gè)比較好的特例，對(duì)一復(fù)雜的搜索問題，如國(guó)際象棋問題，他就顯得較簡(jiǎn)單。所以，要更好地定義一個(gè)估價(jià)函數(shù)還有待深入討論。在尋找最佳擴(kuò)展路徑的過程中我發(fā)現(xiàn)，最佳擴(kuò)展路基上的節(jié)點(diǎn)均在CLOSED表中，利用標(biāo)志flag，以及它們之間的父子關(guān)系，我很容易的就找到了擴(kuò)展路徑，避免了再用一個(gè)路徑指針path來找到路徑，這樣節(jié)省了存儲(chǔ)空間，更利于搜索。通過實(shí)驗(yàn)結(jié)果來看，這兩個(gè)函數(shù)都是可采納的，盡管存在不必要的擴(kuò)展。6、 實(shí)驗(yàn)代碼及輸出結(jié)果1. 源代碼：#include#include#inclu

10、de#define Overflow 1#define N 3int goalNN=1,2,3,8,0,4,7,6,5;int zero2,NodeQTY=0;int *z=zero;/記錄0的位置，zero0:r行；zero1:c列 typedef int Piece;struct Chessboard/棋盤信息 Piece posNN;/記錄每個(gè)數(shù)碼a的位置r行c列int d,f,move;/d:深度；f:啟發(fā)函數(shù)值 ；move:父節(jié)點(diǎn)移動(dòng)到該節(jié)點(diǎn)的方式 ;struct LNodeChessboard board;LNode *parent,*next;bool flag;typedef

11、LNode* List;int* Findzero(LNode* &Node)int i,j,zr2;int *z=zr;for(i=0;iN;i+)for(j=0;jboard.posij=0)zr0=i+1;zr1=j+1;break;return z;int Wrong(LNode *Node)int w=0,i,j;for(i=0;iN;i+)for(j=0;jboard.posij!=goalij&Node-board.posij!=0)w+;return w;int pick(LNode *Node)int w=0,i,j,ii,jj;for(i=0;iN;i+)for(j=0;j

12、board.posij!=goalij&Node-board.posij!=0)for(ii=0;iiN;ii+)for(jj=0;jjboard.posij=goaliijj) w=w+abs(ii-i)+abs(jj-j);break; return w;LNode* extend(LNode *Node,int depth,int zero2,int moveflag,int Choose)LNode* NewNode=new LNode;for(int i=0;iN;i+)for(int j=0;jboard.posij=Node-board.posij;switch(moveflag

13、)case 1:/向左移，不能出界：zero1=2NewNode-board.poszero0-1zero1-1=NewNode-board.poszero0-1zero1-2;NewNode-board.poszero0-1zero1-2=0;break;case 2:/向右移，不能出界：zero1board.poszero0-1zero1-1=NewNode-board.poszero0-1zero1;NewNode-board.poszero0-1zero1=0;break;case 3:/向上移，不能出界：zero0=2NewNode-board.poszero0-1zero1-1=N

14、ewNode-board.poszero0-2zero1-1;NewNode-board.poszero0-2zero1-1=0;break;case 4:/向下移，不能出界：zero0board.poszero0-1zero1-1=NewNode-board.poszero0zero1-1;NewNode-board.poszero0zero1-1=0;break;NewNode-board.d=depth+1;switch(Choose)case 1:NewNode-board.f=NewNode-board.d+Wrong(NewNode);break; case 2:NewNode-b

15、oard.f=NewNode-board.d+pick(NewNode);break; NewNode-board.move=moveflag;NewNode-parent=Node;NodeQTY+; return NewNode;void InitList(LNode* &Open,LNode* &Close)Open=(List)malloc(sizeof(LNode);Close=(List)malloc(sizeof(LNode);if(!Open&!Close)exit(Overflow);Open-next=NULL;Close-next=NULL;int ListInsert(

16、List &L,LNode* NewNode)List p=L;while(p-next)p=p-next;NewNode-next=p-next;p-next=NewNode;return true;LNode* Getminf(List &L)List p=L,q=L-next,r=L,min;min=q;/p,q尋找f最小值的指針，r指向表L中min前一個(gè)元素 if(!q)return NULL;while(q)if(min-board.fq-board.f)r=p;min=q;p=q;q=q-next;r-next=min-next;min-next=NULL;return min;i

17、nt main()int i,j,choose;List Open,Close;LNode *Best,*current;LNode *Start=new LNode;printf(ttt八 數(shù) 碼 問 題 求 解n); printf(n請(qǐng)輸入初始狀態(tài)：);for(i=0;iN;i+)for(j=0;jboard.posij);printf(注:The flag of movement-1:左移;2:右移;3:上移;4:下移)n);printf(初始棋盤狀態(tài)：n); for(i=0;iN;i+)for(j=0;jboard.posij);printf(|n);InitList(Open,Clo

18、se); printf(請(qǐng)選擇(1:A算法;2:A*算法):); scanf(%d,&choose); Start-board.d=0;switch(choose)case 1:Start-board.f=Start-board.d+Wrong(Start);break; case 2:Start-board.f=Start-board.d+pick(Start);break; /Start-board.f=0+Wrong(Start);Start-board.move=0;Start-parent=NULL;Start-next=NULL;Start-flag=1;ListInsert(Op

19、en,Start);/將S加入到Open表中 while(Open-next)Best=Getminf(Open);ListInsert(Close,Best);if(!(Best-board.f-Best-board.d)printf($*有解！*$n); break;z=Findzero(Best);zero0=*(z+0);zero1=*(z+1);if(zero1=N-1&Best-board.move!=2)ListInsert(Open,extend(Best,Best-board.d,zero,1,choose);if(zero1board.move!=1)ListInsert(Open,extend(Best,Best-board.d,ze