201226100315 史玲娟 計自1201

1、A*算法實驗I班級：計自1201學號：201226100315 姓名：史玲娟一、實驗?zāi)康氖煜ず驼莆諉l(fā)式搜索的定義、估價函數(shù)和算法過程，并利用A*算法求解N 數(shù)碼難題，理解求解流程和搜索順序。二、實驗原理A*算法是一種啟發(fā)式圖搜索算法，其特點在于對估價函數(shù)的定義上。對于一 般的啟發(fā)式圖搜索，總是選擇估價函數(shù)f值最小的節(jié)點作為擴展節(jié)點。因此，f 是根據(jù)需要找到一條最小代價路徑的觀點來估算節(jié)點的，所以，可考慮每個節(jié)點 n的估價函數(shù)值為兩個分量：從起始節(jié)點到節(jié)點n的實際代價g(n)以及從節(jié)點n 到達目標節(jié)點的估價代價h(n),且 h(n) h *(n)，h *(n)為n節(jié)點到目的結(jié)點的最 優(yōu)路徑的代

2、價。八數(shù)碼問題是在3X3的九宮格棋盤上，擺有8個刻有18數(shù)碼的將牌。棋 盤中有一個空格，允許緊鄰空格的某一將牌可以移到空格中，這樣通過平移將牌 可以將某一將牌布局變換為另一布局。針對給定的一種初始布局或結(jié)構(gòu)(目標狀 態(tài))，問如何移動將牌，實現(xiàn)從初始狀態(tài)到目標狀態(tài)的轉(zhuǎn)變。如下圖1表示了一 個具體的八數(shù)碼問題求解。13182482477657651384765圖1八數(shù)碼問題的求解類似的，十五數(shù)碼問題是在4X4的十六宮格棋盤上，擺有15個刻有1F 數(shù)碼的將牌。棋盤中有一個空格，允許緊鄰空格的某一將牌可以移到空格中，這 樣通過平移將牌可以將某一將牌布局變換為另一布局。針對給定的一種初始布局 或結(jié)構(gòu)(目

3、標狀態(tài))，問如何移動將牌，實現(xiàn)從初始狀態(tài)到目標狀態(tài)的轉(zhuǎn)變。三、實驗結(jié)果此圖為位置不符的數(shù)碼的估價函數(shù)方法的流程圖:A(4) 2 8 3 16 47 5s(4)17 . 6 -初始2 8 316 47 53D(5)2 8 31 47 6 5G(6)H8 32 8 32 1 47 1 4E(5) 2 1 8 4 7 6I(5)2 1 8 4 7 6 53F(6) 2 8 3 1 4 7 6 5ate-J(7) 2 3 1 8 4 7 6 5K(5) 1 2 3 8 4 7 6 5L(5) 1 2 3 847 6 5 目的M 1 2 3 7 8 4 6 5表1不同啟發(fā)函數(shù)h(n)求解8數(shù)碼問題的結(jié)果

4、比較啟發(fā)函數(shù)h(n)不在位數(shù)移動距離總和初始狀態(tài)283164705283164705283164705目標狀態(tài)123804765123804765123804765最優(yōu)解Case 1:283164705k慝繭電魏：1?性成F點數(shù)，13 驚圖；2 8 316 4b 5Case 1:283164705鏟展克電麝&隹成P點數(shù)出EE：Q 8 316 475移動過程:移動過程:btep 1:2 8 314b 6 5Step 1: 2 S 3 k 4 i7 6 5|Step 2 : 2318 4 I? 6 5Step 2 :2318 47 6 5Step 3 : 2 3 18 4 P 6 5Step 3

5、: 2 3 18 4 7 6 5Step 4: 12 3 8 4 7 6 5Step 4：12 38 47 6 5Step 5 : 12 3 847 6 5移動結(jié)束!IB 15意鍵繼續(xù)-移動結(jié)束!if間電意鍵繼續(xù)EiJ擴展節(jié)點數(shù)7638生成節(jié)點數(shù)131166運行時間153146表2奇偶性不同時的情況啟發(fā)函數(shù)h(n)初始狀態(tài)453672810目標狀態(tài)123804765最優(yōu)解453672310初始狀態(tài)和目標狀態(tài)的逆序?qū)?shù)奇偶性不同,.則無解請重新輸入一表3不同啟發(fā)函數(shù)A()求解15數(shù)碼問題的結(jié)果比較啟發(fā)函數(shù)h(n初始狀態(tài) 目標狀態(tài) 最優(yōu)解.動結(jié)束！ 葛亍時間陌不在位數(shù)12345a68907bdef

6、c123456789abcdef0移動距離總和12345a68907bdefc123456789abcdef0012345a68907bdefc123456789abcdef0擴展節(jié)點數(shù) 生成節(jié)點數(shù) 運行時間615786157812125593表4奇偶性同時的情況啟發(fā)函數(shù)h(n)初始狀態(tài)21345a68907bdefc目標狀態(tài)123456789abcdef0最優(yōu)解|21345a6890?bdefc1初始狀態(tài)和目標狀態(tài)的逆序?qū)?shù)奇偶性相同，則無解，請重新輸入|8數(shù)碼為例，不同啟發(fā)函數(shù)源代碼：int calw(string s)/計算該狀態(tài)的不在位數(shù)h(n)int re=0;for(int i=0

7、;i9;i+) if(si!=ti & si!=0) re+;return re;int calw1(string s)/自定義估價函數(shù)，是各數(shù)碼移到目的位置所需移動的 距離的總和int re=0;for(int i=0;i9;i+)if(si!=ti & si!=0) for(int j=0;j9;j+)if(si=tj) break;re+=abs(i/3-j/3)+abs(i%3-j%3);return re;int calw2(string s)/寬度優(yōu)先搜索算法(即令估計代價h(n) = 0的A*算法) return 0;四、實驗總結(jié)完成實驗報告要求1, 2和3。參考人*算法核心代碼

8、，以8數(shù)碼問題為例實現(xiàn)A*算法的求解程序，設(shè)計 兩種不同的估價函數(shù)。第一種是取一格局與目的格局相比，其位置不符的數(shù)碼數(shù)目。另外一種是各 數(shù)碼移到目的位置所需移動的距離的總和。在求解8數(shù)碼問題的A*算法程序中，設(shè)置相同的初始狀態(tài)（ 例如 283164705）和目標狀態(tài)（例如123804765），針對不同的估價函數(shù)，求得問題 的解，并比較它們對搜索算法性能的影響，包括擴展節(jié)點數(shù)、生成節(jié)點數(shù)等。在8數(shù)碼的基礎(chǔ)上完成15數(shù)碼?？偨Y(jié)實驗心得體會三個不同的估價函數(shù)，最后求得的最優(yōu)解都是相同的。相比之下，第二種移 動距離總和的估價函數(shù)的方法，擴展節(jié)點數(shù)和生成節(jié)點數(shù)最少，第一種方法次之， 深度優(yōu)先搜索的擴展節(jié)點數(shù)和生成節(jié)點數(shù)大幅度多于上訴兩方法，在15數(shù)碼中 這一點體現(xiàn)得更加明顯。前兩種啟發(fā)函數(shù)運行時產(chǎn)生的擴展節(jié)點數(shù)和生成節(jié)點數(shù) 相差不大，但是第三種生成的數(shù)量遠遠大于前者。同時值得一說的是在8數(shù)碼中奇偶校驗后奇偶性不同的無解，而在15數(shù)碼 中則相反，奇偶性相同則無解。這里的15數(shù)碼采用了 16進制的編碼方式，取值 0-f.通過這次實驗，我們熟悉和掌握啟發(fā)式搜索的定義、估價函數(shù)和算法過程， 并利用A*算法求解N數(shù)碼難題，理解求解流程和搜索順序。其中最簡單的估價函數(shù)是取一格局與目的格局相比，其位置不符的數(shù)碼數(shù) 目。直觀感覺認為這種估價函數(shù)很有效，因為在其他