八數(shù)碼問題算法文獻綜述

1、八數(shù)碼問題算法文獻綜述報告摘要：隨著計算機和網(wǎng)絡的大范圍普及，電腦游戲也普遍存在于人們的生活 中，但是大部分的人都只是看重游戲的娛樂價值（啟發(fā)思維，培養(yǎng)觀察能力、耐 心等），而不在乎其本質(zhì)，比如說它有著什么樣的數(shù)據(jù)結構，它的核心算法是什 么等等這些問題。本文就目前一個很經(jīng)典的算法問題一一八數(shù)碼問題來分析其核 心的算法，并且借助前人得出的研究，進一步分析和設計算法。關鍵詞：八數(shù)碼；拼圖游戲；廣度優(yōu)先搜索；深度優(yōu)先搜索；A*搜索1引言從古至今，“游戲”這個詞對于人們來說都不陌生，從古代的斗禽，蹴鞠等 到現(xiàn)在的一系列的電腦游戲。尤其是如今的電腦游戲，不勝其數(shù)，種類繁多，不 亦樂乎，拼圖游戲就是其中的

2、一種。所謂的拼圖游戲就是把一副完整的圖片通過 規(guī)則的或者不規(guī)則的切割后打亂成零片，玩家只需把零片拼湊回原形即可。在這 個過程中，要發(fā)生無數(shù)次的狀態(tài)改變，在電腦上也如此。不同的是，電腦上的拼 圖游戲需要一個“看不見”的存儲空間來存儲這一個個不同的狀態(tài)。這就必須涉 及到數(shù)據(jù)的存貯方式。尤其是算法，它是拼圖游戲的核心，它決定了計算機怎樣 解決這個問題，同時還影響著這個游戲程序的存儲方式。但是，并不是一個能玩 的游戲都具有理想的算法和數(shù)據(jù)結構。因此，對一個游戲的算法進行分析優(yōu)化并 設計出一個理想的算法顯得更加重要。此拼圖游戲是建立在一個3*3的方格棋 盤上，把棋盤上的打散的八塊圖片分別用數(shù)字1-8標識

3、，棋盤上空的那塊標識為 0，那么拼圖游戲就可以轉(zhuǎn)化成我們算法中極為極為經(jīng)典的八數(shù)碼問題。2八數(shù)碼問題的研究現(xiàn)狀2.1八數(shù)碼問題的概念八數(shù)碼問題也稱為九宮問題。在3X3的棋盤，擺有八個棋子，每個棋子上 標有1至8的某一數(shù)字，不同棋子上標的數(shù)字不相同。棋盤上還有一個空格，與 空格相鄰的棋子可以移到空格中。要求解決的問題是：給出一個初始狀態(tài)和一個 目標狀態(tài)，找出一種從初始轉(zhuǎn)變成目標狀態(tài)的移動棋子步數(shù)最少的移動步驟。所 謂問題的一個狀態(tài)就是棋子在棋盤上的一種擺法。棋子移動后，狀態(tài)就會發(fā)生改 變。解八數(shù)碼問題實際上就是找出從初始狀態(tài)到達目標狀態(tài)所經(jīng)過的一系列中間 過渡狀態(tài)。2.2八數(shù)碼問題的狀態(tài)空間法表

4、示2.2.1狀態(tài)描述八數(shù)碼問題的一個狀態(tài)就是八個數(shù)字在棋盤上的一種放法。每個棋子用它上 面所標的數(shù)字表示，并用0表示空格，這樣就可以將棋盤上棋子的一個狀態(tài)存儲 在一個一維數(shù)組p9中，存儲的順序是從左上角開始，自左至右，從上到下。把標識的八塊圖片抽象成一個數(shù)字序列，構成一個數(shù)組，表示其擺放的位置。例如:假設初始狀態(tài)為：218 ，目標狀態(tài)為:6 518732 0465，那么此八數(shù)碼問題就可以轉(zhuǎn)換為從開始系列為2,8,3,1,0,6,7,4,5向目標系列為1,2,3,8,0,4,7,6,5 轉(zhuǎn)化的 問題。也可以用一個二維數(shù)組來存放。2.3八數(shù)碼問題的搜索算法2.3.1深度優(yōu)先搜索耿國華在研究中指出了

5、深度優(yōu)先搜索（Depth_First Search，DFS）的概念： 是指按照深度方向搜索，它類似于樹的先根遍歷，是樹的先根遍歷的推廣。它 的算法思想中有遞歸算法：首先訪問出發(fā)點A，然后依次以A的未被訪問的鄰 接點為出發(fā)點，深度優(yōu)先搜索圖，直至圖中所有與A有路徑相同的頂點都被訪 問。若是非連通圖，那么圖中一定還會有未被訪問的頂點，則需要從圖中另選一 個還未被訪問過得頂點作為起始點，重復上述搜索過程，直到圖中所有頂點都被 訪問過為止。除了遞歸算法外，還用鄰接表作為存儲結構實現(xiàn)深度優(yōu)先搜索，其 查找鄰接點的時間復雜度為O（e），其中e是無向圖中的邊數(shù)或有向圖中的弧數(shù)， 則深度優(yōu)先搜索圖的時間復雜度

6、為O（n+e）。用深度優(yōu)先搜索求解八數(shù)碼問題的搜索過程：（1） 把起始節(jié)點S放到未擴展節(jié)點的OPEN表（此時OPEN表是一個堆 棧，后進先出）中。如果此節(jié)點為一目標節(jié)點，則得到解。（2）如果OPEN為一空表則無解，失敗退出。（3）把第一個節(jié)點（記作節(jié)點n ）從OPEN表移到CLOSED表。（4）如果節(jié)點n的深度等于最大深度則轉(zhuǎn)向第二步。（5）擴展節(jié)點n產(chǎn)生其全部后繼節(jié)點并把它們放入OPEN表的前頭。如果 沒有后繼節(jié)點則轉(zhuǎn)向第二步。（6）如果后繼節(jié)點中有任一個節(jié)點為目標節(jié)點，則求得一個解（反向追蹤 從目標節(jié)點到起始節(jié)點的路徑），成功退出；否則，轉(zhuǎn)向第二步。2.3.2廣度優(yōu)先搜索廣度優(yōu)先搜索和深度

7、優(yōu)先搜索的基本思路相同。與深度優(yōu)先搜尋對應，耿國華還提出廣度優(yōu)先搜索（Breadth_First Search， BFS）的概念：是指按照廣度方向搜索，它類似于樹的層次遍歷，是樹的層次遍 歷的推廣。其基本的思想是：從圖中某個頂點B出發(fā)，首先訪問B；依次訪問 B的各個未被訪問的鄰接點。最后，分別從這些鄰接點（端結點）出發(fā)，依次訪 問它們的各個未被訪問的鄰接點（新的端結點）。注意，訪問時應保證：如果Bi 和Bk為當前的端結點，且在Bi和Bk之前被訪問，則耳的所有未被訪問的鄰接 點應在Bk的所有未被訪問的鄰接點之前訪問。再重復此步驟，直到所有的端結 點均沒有未被訪問的鄰接點為止。若此時還有頂點未被訪

8、問，則選一個未被訪問 的頂點作為起始點，重復上述過程，直到所有的頂點均被訪問過為止。深度優(yōu)先搜索的過程：把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標節(jié)點，則得到解)。如果OPEN是個空表，則無解，失敗退出；否則繼續(xù)下一步。把第一個節(jié)點(記作節(jié)點n )從OPEN表移出并把它放入CLOSED的已擴展點表中。擴展節(jié)點n如果沒有后繼節(jié)點，則轉(zhuǎn)向第2步。把n的所有后繼節(jié)點放到OPEN表的末端并提供從這些后繼節(jié)點回到n的指針。如果n的任一個后繼節(jié)點是個目標節(jié)點，則找到一個解(反向追蹤得到從目標節(jié)點到起始節(jié)點的路徑)，成功退出，否則轉(zhuǎn)第3步。2.3.3 A*搜索呂國英研究者還提出了啟發(fā)式搜索的概念：考

9、慮問題給定的特有的性質(zhì)，選 用合適的規(guī)則，提高搜索的效率。這正是需要探索的方向。算法技術手冊 提到的A*搜索就是一種啟發(fā)式搜索，在搜索時能夠利用啟發(fā)式信息，智能地調(diào) 整搜索策略。其實，A*搜索也是一種迭代有序的搜索，它維護一個棋面狀態(tài)的 開放集合。以下是算法技術手冊中所講的A*搜索的具體描述：在每次迭代時，A*搜索使用一個評價函數(shù)f*(n)評價開放集合中的所有棋 面狀態(tài)，選擇最小的棋面狀態(tài)。定義f*(n)=g*(n)+h*(n):g*(n)估算從初始狀態(tài)到狀態(tài)n的最短走法序列。h*(n)估算從狀態(tài)n到目標狀態(tài)的最短走法序列。f*(n)估算從初始狀態(tài)開始，經(jīng)過狀態(tài)n，到達目標狀態(tài)的最短走法序列。

10、星號*表示使用了啟發(fā)式信息(自從1968年開發(fā)出此算法后，這個記法就被 廣泛接受)，因此f*(n)，g*(n)以及h*(n)是對實際開銷f(n)，g(n)以及h(n)的估 算，而這些實際開銷只能在得到解后才能夠知道。簡而言之，就是f*(n)越低， 表示狀態(tài)n越接近目標狀態(tài)。f*(n)最關鍵的部分是啟發(fā)式的計算h*(n)，因為g*(n)能夠在搜索的過程中， 通過記錄狀態(tài)n的深度計算出來，如果h*(n)不能準確地區(qū)分開有繼續(xù)搜索價值 的狀態(tài)和沒有價值的狀態(tài)，那么A*搜索不會表現(xiàn)得比上述任何盲目搜索要好。 如果能準確地估算h*(n)，那么使用f*(n)就能夠得到一個開銷最小的解。以下是A*搜索過程：

11、把初始節(jié)點A0放入Open表，計算f(A0)。如果Open表為空，則問題無解，退出。把Open表首個節(jié)點(即節(jié)點n)取出放入Closed表。 判斷節(jié)點n是否是目標節(jié)點，如果是，則求得問題的解，退出。若節(jié)點n不可擴展，則轉(zhuǎn)第2步。擴展節(jié)點n，用估價函數(shù)f( x)計算每個子節(jié)點的估價值，并為每個子 節(jié)點配置指向父節(jié)點的指針，將其子節(jié)點放入Open表中，對Open表 中的全部節(jié)點按估價值從小到大進行排序。然后轉(zhuǎn)第2步。2.3.4結果比較初始狀態(tài) 33,6,4,7,0.5目標狀態(tài)門4,7,6,5擴展節(jié)點生成節(jié)點解的步敷有效分枝因子A*P(rrM51161.491 3A，不在位61361.533 41深

12、度優(yōu)先(Q1。)473787101.948 04深度優(yōu)先(20)54489 S01161.767 6寬度優(yōu)先203461.799 89圖1結果比較Fig.1 Comparison】7】3.總結綜上，從圖一和圖二已經(jīng)研究出來的結果可以看到，用深度優(yōu)先搜索、廣度(2 8 3)(12 3 )優(yōu)先搜索和A*搜索解的步數(shù)，從初始狀態(tài)為7 0 4到目標狀態(tài)為8 0 416 5 J7 6 5)的擴展節(jié)點、生成節(jié)點以及解的步數(shù)等的比較，對比出了 A*算法的優(yōu)勢：在搜 索時，雖然也需要保存一些狀態(tài)，但在每次擴展時，它有啟發(fā)的選擇了有希望的 節(jié)點進行擴展，因此大大的縮小了搜索的空間，能夠較快的找到問題的解。這是

13、深度優(yōu)先搜索和廣度優(yōu)先搜索不能達到的。深度優(yōu)先搜索雖然有時候會較快的 找到解，但是如果沒有利用回溯作為輔助，得到的解可能不是最優(yōu)的，而且如果 對其他進行搜索深度限制的話，往往會得不到解；廣度優(yōu)先搜索先搜索則能夠保 證找到最優(yōu)解，但是由于需要保存大量的狀態(tài)而使得空間復雜度非常的大，很容 易出現(xiàn)“組合爆炸”問題。參考文獻1周浩.八數(shù)碼問題DNF和BNF算法的設計與實現(xiàn)J.電腦知識與技術，2011,7 （22）:5487-5489. 耿國華.數(shù)據(jù)結構一一C語言描述M.北京：清華大學出版社，2009.2, 212-216.呂國英.算法設計與分析M.北京：高等教育出版社,2005,7.180-190.G

14、eorge T. Heineman,Gary Pollice,Stanley Selkow 楊晨，李明（譯）.算法技術手 冊M.北京：機械工業(yè)出版社，2010.3,185-208.喬宏敬.求解八數(shù)碼問題的幾種搜索算法比較J.福建電腦，2007,8:50-51.歐陽林艷.八數(shù)碼問題的搜索算法比較J.洛陽師范學院學報，2011,30（8）： 69-71.詹志輝，胡曉敏，張軍.通過八數(shù)碼問題比較搜索算法的性能J.計算機工程 與設計，2007,28（11）： 2505-2508張鴻.人工智能中求解八數(shù)碼問題算法的實現(xiàn)與分析J.軟件導刊，2009,8（6）： 63-64.陶陽.VS2008環(huán)境下八數(shù)碼問

15、題的BFS算法設計與實現(xiàn)J.電腦知識與技術 2009,5（26）:7417-7419.A.V.Aho,J.E.Hopcroft,J.D.Ullman,The Design and Analysis of Computer Algorithms,Addison Wesley,Reading,Mass.,1974.Eight Digital Algorithm for the ProblemAbstract： With the computer and network wide range of only valued the entertainment value popular computer games are also common in peoples lives, but most people are of the game（inspired thinking, to develop observation, patience, etc.）, but not with its nature, for example,what data it has a structure, it is the core algorithm and so these problems. This is a c