1、算法設(shè)計(jì)與分析插棒游戲?qū)W院：信息工程學(xué)院名：學(xué) 號(hào)：Sxxxxxx電 話：152xxxxxxxx實(shí)驗(yàn)室： 理工樓9082013年12月22日一、問(wèn)題描述有一個(gè)等邊三角形的板上布置了 15個(gè)孔，初始的時(shí)候除了一個(gè)孔，其它孔 都插上了棒。圖1所示為一種可能的情況，空孔的位置不限。一個(gè)棒可以跳過(guò)它 的直接鄰居，移到一個(gè)空白的位置上。這一跳會(huì)把被跳過(guò)的鄰居從板上移走。要 求在下列條件下，求問(wèn)題的解：已知空孔的位置，求出消去13個(gè)棒的最短步驟，對(duì)剩下的插棒位置不限 制。已知空孔的位置，求出消去13個(gè)插棒的最短步驟，剩下的插棒最終要落 在最初的空孔位置上。圖1棋盤示例二、回溯法2.1回溯法的基本思想回溯法

2、又稱試探法，它采用試錯(cuò)的思想，嘗試分步的去解決一個(gè)問(wèn)題。在分 步解決問(wèn)題的過(guò)程中，當(dāng)它通過(guò)嘗試發(fā)現(xiàn)現(xiàn)有的分步答案不能得到有效的正確的 解答的時(shí)候，它將取消上一步甚至是上幾步的計(jì)算，再通過(guò)其它的可能的分步解 答再次嘗試尋找問(wèn)題的答案。回溯法通常用最簡(jiǎn)單的遞歸方法來(lái)實(shí)現(xiàn)，在反復(fù)重 復(fù)上述的步驟后可能出現(xiàn)兩種情況：找到一個(gè)可能存在的正確的答案在嘗試了所有可能的分步方法后宣告該問(wèn)題沒(méi)有答案回溯法的本質(zhì)是深度優(yōu)先搜索，是一種組織得井井有條的、能避免不必要重 復(fù)搜索的窮舉式搜索算法。在包含問(wèn)題的所有解的解空間樹中，按照深度優(yōu)先搜 索的策略，從根結(jié)點(diǎn)出發(fā)深度探索解空間樹。當(dāng)探索到某一結(jié)點(diǎn)時(shí)，要先判斷該 結(jié)點(diǎn)

3、是否包含問(wèn)題的解，如果（可能）包含，就從該結(jié)點(diǎn)出發(fā)繼續(xù)探索下去，如 果該結(jié)點(diǎn)不包含問(wèn)題的解，則逐層向其祖先結(jié)點(diǎn)回溯。其實(shí)回溯法就是對(duì)隱式圖 的深度優(yōu)先搜索算法。若用回溯法求問(wèn)題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn) 的所有可行的子樹都要已被搜索遍才結(jié)束。而若使用回溯法求任一個(gè)解時(shí)，只 要搜索到問(wèn)題的一個(gè)解就可以結(jié)束。2.2回溯法的適用條件可用回溯法求解的問(wèn)題P，通常要能表達(dá)為:對(duì)于已知的由n元組（x1，x2，.，xn）組成的一個(gè)狀態(tài)空間 E=（x1，x2，xn） | xiUSi，i=1，2，n，給 定關(guān)于n元組中的一個(gè)分量的一個(gè)約束集D，要求E中滿足D的全部約束條件的 所有n元組。其中Si是分量xi

4、的定義域，且|Si|有限，i=1，2,，n。我們稱 E中滿足D的全部約束條件的任一 n元組為問(wèn)題P的一個(gè)解。解問(wèn)題P的最樸素的方法就是枚舉法，即對(duì)E中的所有n元組逐一地檢測(cè)其 是否滿足D的全部約束，若滿足，則為問(wèn)題P的一個(gè)解。但顯然，其計(jì)算量是相當(dāng)大的。我們發(fā)現(xiàn)，對(duì)于許多問(wèn)題，所給定的約束集D具有完備性，即i元組（X1, x2,，xi）滿足D中僅涉及到x1，x2，xi的所有約束意味著j （j=i）元組（x1， x2,，xj）一定也滿足D中僅涉及到x1，x2,，xj的所有約束，i=1，2,， n。換句話說(shuō)，只要存在0jijo 因此，對(duì)于約束集D具有完備性的問(wèn)題P，一旦檢測(cè)斷定某個(gè)j元組（x1，x

5、2,， xj）違反D中僅涉及x1，x2，xj的一個(gè)約束，就可以肯定，以（x1，x2， xj）為前綴的任何n元組（x1，x2,，xj，xj+1，xn）都不會(huì)是問(wèn)題P的解， 因而就不必去搜索它們、檢測(cè)它們?；厮莘ㄕ轻槍?duì)這類問(wèn)題，利用這類問(wèn)題的 上述性質(zhì)而提出來(lái)的比枚舉法效率更高的算法。2.2回溯法的空間樹回溯法首先將問(wèn)題P的n元組的狀態(tài)空間E表示成一棵高為n的帶權(quán)有序樹 T，把在E中求問(wèn)題P的所有解轉(zhuǎn)化為在T中搜索問(wèn)題P的所有解。樹T類似于 檢索樹，它可以這樣構(gòu)造：設(shè) Si 中的元素可排成 xi（1），xi（2），xi（mi-1），|Si| =mi，i=1，2,，n。 從根開始，讓T的第I層的每

6、一個(gè)結(jié)點(diǎn)都有mi個(gè)兒子。這mi個(gè)兒子到它們的雙 親的邊，按從左到右的次序，分別帶權(quán)xi+1（1），xi+1（2），xi+1（mi），i=0，1， 2，n-1。照這種構(gòu)造方式，E中的一個(gè)n元組（x1，x2，xn）對(duì)應(yīng)于T中 的一個(gè)葉子結(jié)點(diǎn)，T的根到這個(gè)葉子結(jié)點(diǎn)的路徑上依次的n條邊的權(quán)分別為x1， x2，xn，反之亦然。另外，對(duì)于任意的0in-1， E中n元組（x1，x2， xn）的一個(gè)前綴I元組（x1，x2，xi）對(duì)應(yīng)于T中的一個(gè)非葉子結(jié)點(diǎn)，T的根 到這個(gè)非葉子結(jié)點(diǎn)的路徑上依次的I條邊的權(quán)分別為x1，x2,，xi，反之亦然。 特別，E中的任意一個(gè)n元組的空前綴（），對(duì)應(yīng)于T的根。因而，在E中尋找

7、問(wèn)題P的一個(gè)解等價(jià)于在T中搜索一個(gè)葉子結(jié)點(diǎn)，要求從 T的根到該葉子結(jié)點(diǎn)的路徑上依次的n條邊相應(yīng)帶的n個(gè)權(quán)x1，x2,，xn滿足 約束集D的全部約束。在T中搜索所要求的葉子結(jié)點(diǎn)，很自然的一種方式是從根 出發(fā)，按深度優(yōu)先的策略逐步深入，即依次搜索滿足約束條件的前綴1元組（x1i）、前綴2元組（xl, x2）、，前綴I元組（xl, x2,，xi）,，直到i=n為止。在回溯法中，上述引入的樹被稱為問(wèn)題P的狀態(tài)空間樹；樹T上任意一個(gè)結(jié) 點(diǎn)被稱為問(wèn)題P的狀態(tài)結(jié)點(diǎn)；樹T上的任意一個(gè)葉子結(jié)點(diǎn)被稱為問(wèn)題P的一個(gè)解 狀態(tài)結(jié)點(diǎn)；樹T上滿足約束集D的全部約束的任意一個(gè)葉子結(jié)點(diǎn)被稱為問(wèn)題P 的一個(gè)回答狀態(tài)結(jié)點(diǎn)，它對(duì)應(yīng)于

8、問(wèn)題P的一個(gè)解2.4回溯法的基本步驟回溯法解決問(wèn)題，一般有三個(gè)步驟：（1）針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；（2）確定易于搜索的解空間結(jié)構(gòu)；（3）以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索三、本題解題思路本題所用的算法思想就是回溯法。3.1解空間由于棋盤的對(duì)稱性，棋盤在變化的過(guò)程中會(huì)形成多個(gè)同構(gòu)的狀態(tài)。例如初始狀態(tài)時(shí)，空孔只有一個(gè)，共有15種基本狀態(tài)。如圖2所示，任意 狀態(tài)與空孔位置在其它的與該空孔顏色相同的點(diǎn)處的狀態(tài)是同構(gòu)的，它們可以通 過(guò)沿中位線翻轉(zhuǎn)和旋轉(zhuǎn)60o互相轉(zhuǎn)換。也就是說(shuō)，空孔所在位置的顏色相同的個(gè) 狀態(tài)是同構(gòu)的。如空孔位置在頂點(diǎn)處的三個(gè)狀態(tài)，他們僅通過(guò)旋轉(zhuǎn)60。

9、的操作即 可互相轉(zhuǎn)換。圖2初始狀態(tài)空孔位置同構(gòu)圖同構(gòu)的狀態(tài)要么都無(wú)解，要么有相同數(shù)量的解，且他們的解可以根據(jù)同構(gòu)對(duì) 應(yīng)變化得到。本題所描述的問(wèn)題可能無(wú)解，也可能有多個(gè)解，且同構(gòu)狀態(tài)的解也有一定關(guān) 聯(lián)。3.2解空間結(jié)構(gòu)分析整個(gè)游戲的過(guò)程，發(fā)現(xiàn)每合法地走出一步，棋盤上就會(huì)少一個(gè)棋子，故 當(dāng)該問(wèn)題有解時(shí)，最后都需要走13步。如果無(wú)解，必然小于或等于13步。因此， 我們的狀態(tài)樹的深度將達(dá)到13層，每一個(gè)點(diǎn)的分支數(shù)量不確定。3.3剪枝考慮到深度確定這一點(diǎn)，在剪枝的時(shí)候就不能用最短步數(shù)這一個(gè)限制條件 了。由于對(duì)稱性，當(dāng)一個(gè)狀態(tài)被證實(shí)無(wú)解時(shí)，該狀態(tài)的旋轉(zhuǎn)、對(duì)稱變換后的同構(gòu) 體也必然無(wú)解。因此，可以利用這一特

10、性，對(duì)已經(jīng)證實(shí)無(wú)解的狀態(tài)不再探索而減 少不必要的試探。四、編程提要4.1數(shù)據(jù)類型1、棋盤。正三角形的棋盤用數(shù)組很難表示。自定義最多有六個(gè)子節(jié)點(diǎn)的Node類，用 雙向多維鏈表構(gòu)成圖，表示棋盤。但是這樣不適合隨機(jī)讀寫，切在判斷同構(gòu)上沒(méi)有太大優(yōu)勢(shì)， 因此采用變形的數(shù)組表示棋盤。把正三角形的棋盤上的孔左對(duì)齊，用5*5的數(shù)組的左下半部 分表示。此時(shí)，棋棒可以左右跳、上下跳、沿著從左上到右下的對(duì)角線方向跳。2、狀態(tài)空間。把每一步的移動(dòng)信息（從哪個(gè)坐標(biāo)到哪個(gè)坐標(biāo)）記錄下來(lái)，構(gòu)成隱式多 叉樹。因?yàn)橛玫氖腔厮莘ǎ手恍杈S護(hù)一個(gè)棋盤對(duì)象，根據(jù)走棋信息就可以得到上下的棋盤 狀態(tài)。3、堆棧。維護(hù)一個(gè)堆棧，把每一個(gè)帶探

11、測(cè)的狀態(tài)點(diǎn)放入，方便回溯。4、鏈表?？紤]到多解的可能性，用一個(gè)鏈表記錄結(jié)果集。每個(gè)節(jié)點(diǎn)是一個(gè)解的全部移 動(dòng)棒子流程。4.2主要函數(shù)思路判斷同構(gòu)。先判斷最內(nèi)部三個(gè)點(diǎn)空點(diǎn)數(shù)量，若一致再繼續(xù)判斷，否則肯定不是同構(gòu)。 合理選擇關(guān)鍵點(diǎn)，可以避免多次遍歷數(shù)列。剪枝。判斷是否剪掉該分支的依據(jù)是該狀態(tài)是否與無(wú)解狀態(tài)集合中的某個(gè)元素同構(gòu)。 其本質(zhì)是查找，按照含有棋子數(shù)量、中心三角形元素個(gè)數(shù)、外頂點(diǎn)狀態(tài)等信息可以對(duì)無(wú)解狀 態(tài)集合構(gòu)建二叉書，查找時(shí)效率就會(huì)高狠多?；厮輆）把初始狀態(tài)放入堆棧。b）把堆棧最頂上元素取出，判斷棋盤狀態(tài)，若：棋盤只剩一個(gè)元素。把全部堆棧信息復(fù)制，作為一個(gè)解記錄到解集中。棋盤剩多個(gè)元素還有孩

12、子節(jié)點(diǎn)。把該節(jié)點(diǎn)的所有不與空解狀態(tài)集合中同構(gòu)的下一狀態(tài)的走 法記錄到堆棧中。沒(méi)有孩子節(jié)點(diǎn)。把這時(shí)的棋盤復(fù)制，放到空解狀態(tài)集合中c）若堆棧不為空，重復(fù)b。根據(jù)問(wèn)題A、B篩選解集，并打印。4.3關(guān)鍵算法實(shí)現(xiàn)Game.init();/初始化棋盤Game.recall()/ 回溯法求解記錄走法的堆棧Stack steps = new Stack();記錄棋盤狀態(tài)的的堆棧Stack boards = new Stack();保存下一次走法的變量。重復(fù)使用。ArrayList moves = new ArrayList();Board b = new Board();初始化棋盤堆棧，為回溯做準(zhǔn)備。boar

13、ds.push(board);開始回溯求解while (!boards.empty() b = boards.pop(); TOC o 1-5 h z /*到上一次探索的節(jié)點(diǎn)的父節(jié)點(diǎn)的位置了。該節(jié)點(diǎn)的子孩 子一遍歷完，對(duì)該解法已經(jīng)探索完了，故該把它對(duì)應(yīng)的走法取消。*/if(b=null)steps.pop();continue;/記錄走棋過(guò)程steps.push(b.getLastMove();當(dāng)前狀態(tài)是正確的終止?fàn)顟B(tài)if (b.count = 1) /記錄解法。boolean isB = false;29.if(b.lastMove.y2=y&b.lastMove.x2 = x)30.31.

14、t_succeed_B+;32.isB = true;33.提示已經(jīng)找到B方案的解34.;35.提示已經(jīng)找到A方案的解36. 演示流程，記錄當(dāng)前解法。37.ArrayList solution = new ArrayList();38.Board sb = board;39.for (int i = 0; i steps.size(); i+) 40.if(i!=0)/第一條記錄是初始棋盤的最后一步，無(wú)意義41.sb = sb.move(steps.get(i);42.steps.get(i).show();43.sb.show();44.solution.add(steps.get(i);4

15、5.46. 記錄solution或者展示。47.steps.pop();/取消最后一步走法，繼續(xù)48. else 49.moves = b.getMoves();50./沒(méi)有走法可以繼續(xù)了。狀態(tài)被迫終止，取消走法，回溯51.if (moves.size() = 0) 52.steps.pop();53.54. else 55./還有其他走法。則把所有子孩子狀態(tài)入棧。繼續(xù)回溯56.boards.push(null);57.for (Move m : moves) 57.boards.push(b.move(m); TOC o 1-5 h z /end - while63.輸出結(jié)果：System.out.