1、課程名稱： 設計題目：所在院系：指導教師： 職 稱： 提交時間：吉林財經大學課程設計報告算法課程設計插棒游戲管理科學與信息工程學院計算機科學與技術副教授2017 年4月目錄一、題目描述與設計要求 11題目描述與設計要求 1二、問題分析 11解空間 12解空間結構 23剪枝 24回溯法的基本思想 25回溯法的適用條件 36回溯法的空間樹 47回溯法的基本步驟 4三、算法設計 51偽代碼 5四、復雜性分析 61時間復雜度 62空間復雜度該 6五、樣本測試、分析與總結 61樣本測試 62 分析 72.1 、數據類型 72.2 主要函數思路 72.3 回溯 83 總結 8參考文獻 9附錄 10一、題目

2、描述與設計要求1題目描述與設計要求a.已知空孔的位置, 不限。b.已知空孔的位置, 初的空孔上。這個類似謎題的游戲在等邊三角形的板上布置了 15個孔。在初始時候，如下 圖所示，除了一個孔，所有孔都插上了插棒。一個插棒可以跳過它的直接鄰居， 移到一個空白的位置上。這一跳會把被跳過的鄰居從板上移走。 設計并實現一個 回溯算法，求解該謎題的下列版本：求出消去13個插棒的最短步驟，對剩下的插棒的最終位置求出消去13個插棒的最短步驟，剩下的插棒最終要落在最 O 二、問題分析1解空間由于棋盤的對稱性，棋盤在變化的過程中會形成多個同構的狀態。例如初始狀態時，空孔只有一個，共有 15種基本狀態。如圖2所示，任

3、意 狀態與空孔位置在其它的與該空孔顏色相同的點處的狀態是同構的，它們可以通過沿中位線翻轉和旋轉 60o互相轉換。也就是說，空孔所在位置的顏色相同的 個狀態是同構的。如空孔位置在頂點處的三個狀態，他們僅通過旋轉60o的操作 即可互相轉換。圖2同構的狀態要么都無解，要么有相同數量的解，且他們的解可以根據同構對 應變化得到。本題所描述的問題可能無解，也可能有多個解，且同構狀態的解也有一定關 聯。2解空間結構分析整個游戲的過程，發現每合法地走出一步，棋盤上就會少一個棋子 ，故 當該問題有解時，最后都需要走13步。如果無解，必然小于或等于13步。因此, 我們的狀態樹的深度將達到13層，每一個點的分支數量

4、不確定。3剪枝考慮到深度確定這一點，在剪枝的時候就不能用”最短步數”這一個限制條 件了。由于對稱性，當一個狀態被證實無解時，該狀態的旋轉、對稱變換后的同 構體也必然無解。因此，可以利用這一特性，對已經證實無解的狀態不再探索而 減少不必要的試探。4回溯法的基本思想回溯法又稱試探法，它采用試錯的思想，嘗試分步的去解決一個問題。在分 步解決問題的過程中，當它通過嘗試發現現有的分步答案不能得到有效的正確的 解答的時候，它將取消上一步甚至是上幾步的計算， 再通過其它的可能的分步解 答再次嘗試尋找問題的答案。回溯法通常用最簡單的遞歸方法來實現，在反復重 復上述的步驟后可能出現兩種情況：找到一個可能存在的正

5、確的答案，在嘗試了所有可能的分步方法后宣告該問 題沒有答案。回溯法的本質是深度優先搜索，是一種組織得井井有條的、能避免不必要重 復搜索的窮舉式搜索算法。在包含問題的所有解的解空間樹中，按照深度優先搜 索的策略，從根結點出發深度探索解空間樹。當探索到某一結點時，要先判斷該 結點是否包含問題的解，如果（可能）包含，就從該結點出發繼續探索下去，如 果該結點不包含問題的解，則逐層向其祖先結點回溯。其實回溯法就是對隱式圖 的深度優先搜索算法。若用回溯法求問題的所有解時，要回溯到根，且根結點的所有可行的子樹都要已被搜索遍才結束。而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結束。5回溯法的適用條

6、件可用回溯法求解的問題P,通常要能表達為：對于已知的由n元組（xi,X2,， Xn）組成的一個狀態空間 E= （Xi, X2,，Xn） I Xi Si , i=1 , 2,，n,給 定關于n元組中的一個分量的一個約束集 D,要求E中滿足D的全部約束條件的 所有n元組。其中S是分量Xi的定義域，且|S i|有限，i=1 , 2,n。我們 稱E中滿足D的全部約束條件的任一 n元組為問題P的一個解。解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其 是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計算量是相 當大的。我們發現，對于許多問題，所給定的約束集 D具有完備性，即

7、i元組（Xi, X2,Xi）滿足D中僅涉及到Xi, X2,Xi的所有約束意味著j （j<=i ）元組 （Xi, X2,Xj） 一定也滿足D中僅涉及到Xi, X2,Xj的所有約束，i=1 , 2,，n。換句話說，只要存在 0&j&n-i ,使得（xi, X2,Xj）違反D中 僅涉及到Xi, X2,，Xj的約束之一，則以（Xi, X2,，Xj）為前綴的任何n 元組（Xi, X2,，Xj , Xj+i,，Xn） 一定也違反D中僅涉及到Xi, X2,，Xi 的一個約束，nij。因此，對于約束集D具有完備性的問題P, 一旦檢測斷 定某個j元組（Xi, X2,，Xj）違反D中僅涉及X

8、i, X2,，Xj的一個約束， 就可以肯定，以（xi, X2,，Xj）為前綴的任何n元組（xi, X2,，Xj, Xj+i,，Xn)都不會是問題P的解，因而就不必去搜索它們、檢測它們。回溯法正是針對 這類問題，利用這類問題的上述性質而提出來的比枚舉法效率更高的算法。6回溯法的空間樹回溯法首先將問題P的n元組的狀態空間E表示成一棵高為n的帶權有序樹 T,把在E中求問題P的所有解轉化為在T中搜索問題P的所有解。樹T類似于 檢索樹，它可以這樣構造：設 S 中的元素可排成 Xi(1) , Xi(2),Xi(m-1) , |Si| =m, i=1 , 2, n。從根開始，讓T的第I層的每一個結點都有 m

9、個兒子。這mi個兒子到它們 的雙親的邊，按從左到右的次序，分別帶權Xi+1(1) , Xi+1(2)，Xi+1(m), i=0 , 1, 2,，n-1。照這種構造方式，E中的一個n元組(x1，X2,，Xn) 對應于T中的一個葉子結點，T的根到這個葉子結點的路徑上依次的 n條邊的權 分別為X1, X2,，Xn,反之亦然。另外，對于任意的 0&i&n-1, E中n元組 (X1, X2,，Xn)的一個前綴I元組(X1, X2,，Xi)對應于T中的一個非葉 子結點，T的根到這個非葉子結點的路徑上依次的I條邊的權分別為X1, X2,， Xi,反之亦然。特別，E中的任意一個n元組的空前綴(

10、),對應于T的根。因而，在E中尋找問題P的一個解等價于在T中搜索一個葉子結點，要求從 T的根到該葉子結點的路徑上依次的 n條邊相應帶的n個權X1, X2,，Xn滿足 約束集D的全部約束。在T中搜索所要求的葉子結點，很自然的一種方式是從根 出發，按深度優先的策略逐步深入，即依次搜索滿足約束條件的前綴1元組(X1i )、 前綴2元組(X1, X2)、，前綴I元組(X1, X2,，Xi),，直到i=n為止。在回溯法中，上述引入的樹被稱為問題 P的狀態空間樹；機tT上任意一個結 點被稱為問題P的狀態結點；樹T上的任意一個葉子結點被稱為問題 P的一個解 狀態結點；樹T上滿足約束集D的全部約束的任意一個葉

11、子結點被稱為問題 P 的一個回答狀態結點，它對應于問題 P的一個解7回溯法的基本步驟回溯法解決問題，一般有三個步驟：(1)針對所給問題，定義問題的解空間；(2) (2)確定易于搜索的解空間結構；(3)以深度優先方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索。三、算法設計1偽代碼ALGORITHM Get_all_moves(i,j)/Get_avail_peg then updates the variables move and move_set/Input :Two nonnegative,integer i and j/Output:Update the peg-boardFor?

12、0 to max_peg_hole doIfpegboardi?-1For j?0 to num_of_rules domove_setmove.move_what?peg_move_rulesj.move_what;move_setmove.del_what?peg_move_rulesj.del_what;move_setmove.move_where?peg_move_rulesj.move_where;move+ALGORITHM Reset_pegboard(i)/Resets the pegboard to the original problem/Input :integer/O

13、utput:original pegboardFor?0 to max_peg_hole doSwap pegboardi andorig_pegboardiALGORITHM Is_solve(i)/Judge problem is solved or not/Input :integer i/Output: 0 or 1Fori?0 to max_peg_hole doIfpegboardi=1Count+Ifcount=1ReturniReturn 0四、復雜性分析1時間復雜度該算法在最好情況下，求得第一種解需要試探 13次。因為每次的走法數目 不確定，也就是狀態數的子孩子數量不確定，

14、狀態總數量不確定。但是該數目不 大于215-2種。無解時，就是這種情況。對于要求所有的解時，需要遍歷整個狀態樹。2空間復雜度該算法需要維護一個狀態棧和一個走法棧。走法棧的深度不超過 13,為常數。 狀態空間樹只記錄當前路徑有關的狀態。假設樹的平均子樹數目為 N,則該堆棧 的大小約為1/N。五、樣本測試、分析與總結1樣本測試The initial pegboard set up*00 0 10 0 0 0 0 0 8 0 0 10 0Golution to the pegboard prohlen= in <161> iterationsStep<01>： Moue14T

15、o05>Step<025： Nove12To14Step<03>s Moue04Io13>Step<04>： Noue11To的4Eteji<05）： Move02To07>Step<06?： Move14To12Step<07>： Moue03To08>Step<08J： Nove10To03Step<09>： Houe0iTa06>Step<10>： MoueW7To的9Step<11）： Moue0bTo13>Step<12>： Move12To14S

16、tep<13>： Moue15To13Press flny key2分析2.1 、數據類型棋盤。正三角形的棋盤用數組很難表示。自定義最多有六個子節點的Node類，用雙向多維鏈表構成圖，表示棋盤。但是這樣不適合隨機讀寫，切在判斷同 構上沒有太大優勢，因此采用變形的數組表示棋盤。把正三角形的棋盤上的孔左 對齊，用5*5的數組的左下半部分表示。此時，棋棒可以左右跳、上下跳、沿著 從左上到右下的對角線方向跳。狀態空間。把每一步的移動信息（從哪個坐標到哪個坐標）記錄下來，構成 隱式多叉樹。因為用的是回溯法，故只需維護一個棋盤對象，根據走棋信息就可 以得到上下的棋盤狀態。堆棧。維護一個堆棧，把

17、每一個帶探測的狀態點放入，方便回溯。鏈表。考慮到多解的可能性，用一個鏈表記錄結果集。每個節點是一個解的 全部移動棒子流程。2.2 主要函數思路判斷同構。先判斷最內部三個點空點數量，若一致再繼續判斷，否則肯定不 是同構。合理選擇關鍵點，可以避免多次遍歷數列。剪枝。判斷是否剪掉該分支的依據是該狀態是否與無解狀態集合中的某個元 素同構。其本質是查找，按照含有棋子數量、中心三角形元素個數、外頂點狀態 等信息可以對無解狀態集合構建二叉書，查找時效率就會高狠多。2.3 回溯把初始狀態放入堆棧。把堆棧最頂上元素取出，判斷棋盤狀態，若：棋盤只剩一個元素。把全部堆 棧信息復制，作為一個解記錄到解集中。棋盤剩多個

18、元素還有孩子節點。 把該節 點的所有不與空解狀態集合中同構的下一狀態的走法記錄到堆棧中。沒有孩子節點。把這時的棋盤復制，放到空解狀態集合中若堆棧不為空，重復 bo根據問題 A、B篩選解集，并打印。3總結回溯算法主要是通過深度試探查詢的方法， 找到解空間，并對不滿足條件和 不是最優組合的方法進行剪枝，從而得到最優解的方法。通過這次運用回溯算法的課程設計，使我們對回溯算法原理和特點有了更深 的理解和掌握。并且通過這次合作形式的作業，我們更加懂得了分工合作的意義， 增強了自己的協作能力和團隊合作的意識。參考文獻1 .侯焯明.面向教育云平臺的智能排課系統的設計與實現D中山大學出版社.20152 .劉彥

19、.基于優先級與回溯算法的排課系統的設計與實現D黑龍江大學出版社.20123 .（美）Anany Lev市n算法設計與分析基礎（第三版 影印版）清華大學出版 社.2013附錄/pegsolve.cpp#include <stdio.h>#include <conio.h>#include <stdlib.h>#include <time.h>#include <iostream> using namespace std;const int MAX_PEG_HOLE=15;const int NUM_OF_RULES=36;const i

20、nt MOVES=0;const int DATA_OFFSET=1;const int INVALID_PEG=-1;/pegboard to play onstatic int pegboard15;/default pegboard/(1 means there is a peg; 0 means there is no peg) static int orig_pegboard15 =.1, 1 ,1,1 ,1 ,1,1 , 1 , 1 , 1,1 , 1 , 1 , 1 , 1;#define VALID_HOLE(x) (x>=0 && x<=14) /

21、* Layout of the pegboard:* 00,* 01,02* 03, 04, 05,* 06, 07, 08, 09,* 10, 11, 12, 13, 14*/ static int move;/data structure representing a movestruct _move_set( 一 一int move_what;int del_what;int move_where; 一typedef _move_set MOVE_SET;static MOVE_SET move_setMAX_PEG_HOLE;static MOVE_SET peg_move_rules

22、NUM_OF_RULES= (/* move_what OVER del_what TO move_where* = <peghole#>,<peghole#>,<peghole#> */0,1,3, 0,2,5,1,4,8, 1,3,6,2,4,7, 2,5,9,3,1,0, 3,4,5, 3,7,12, 3,6,10,4,8,13, 4,7,11,5,9,14, 5,2,0, 5,4,3, 5,8,12,6,3,1, 6,7,8,7,4,2, 7,8,9,8,4,1, 8,7,6,9,5,2, 9,8,7,10,6,3, 10,11,12,11,7,4,

23、 11,12,13,12,7,3, 12,8,5, 12,11,10, 12,13,14,13,8,4, 13,12,11, 14,9,5, 14,13,12 ;/*= reset_pegboard() resets the pegboard to the original problem.=*/ void reset_pegboard() (.int i;for( i = 0; i < MAX_PEG_HOLE; i+ ) pegboardi = orig_pegboardi;/end of reset_pegboard /*= is_solved() returns TRUE if

24、pegboard is solved.=*/ unsigned char is_solved( ) (int i;int count = 0; /count how many pegs there arefor( i = 0; i < MAX_PEG_HOLE; i+ ) if ( pegboardi ) count+ ;if ( count = 1 ) return 1; /pegboard solved!return 0;/end of is_solved/*=display_pegboard displaysthe current statusof the pegboard.=*/

25、void display_pegboard( )(.printf( "n" );printf( "%dn" , pegboard0 );printf( " %d %dn" , pegboard1 , pegboard2);printf( " %d %d %dn" , pegboard3 , pegboard4 , pegboard5);printf( " %d %d %d %dn" , pegboard6 , pegboard7 , pegboard8 , pegboard9);printf(

26、"%d %d %d %d %dn",pegboard10 , pegboard11 , pegboard12 , pegboard13 , pegboard14 );printf( "n" );/end of display_pegboard/*=get_avail_peg updatesthe variables move andmove_set=*/void get_all_moves()( 一一int i , j; /loop countersmove = 0; /initialize # of movesmove_setmove.move_wha

27、t = -1;move_setmove.del_what = -1;move_setmove.move_where = -1;for( i = 0; i < MAX_PEG_HOLE; i+ ) /check all holes(if ( !pegboardi ) /if there is a hole(for( j = 0; j < NUM_OF_RULES; j+)(if (i=peg_move_rulesj.move_where) &&(pegboardpeg_move_rulesj.del_what)(-/* can we move a peg to thi

28、s hole? */if (pegboardpeg_move_rulesj.move_what)(一一一move_setmove.move_what=peg_move_rulesj.move_what;move_setmove.del_what=peg_move_rulesj.del_what;move_setmove.move_where=peg_move_rulesj.move_where; move+; /increment move count /end of if /end of if/end of for/end of if/end of for/end of get_avail_

29、peg/*=movepeg() does theactual moving of a peg.=*/void movepeg( int move_what , int del_what , int move_where )(-pegboardmove_what = 0;pegboarddel_what = 0;pegboardmove_where = 1;/end of movepeg/*=usage() displays how this app can be invoked.=*/void usage()printf("The Pegboard Solver'n"

30、;);printf("Usage:n");printf("tpegsolve <hole#>n");printf("where,n");printf("t<hole#>tis the empty hole on the pegboard.n");printf("ttHole# is between 1 and 15, inclusive.n");printf("nLayout of the pegboard:n");printf("01,n&

31、quot;);printf(" 02, 03n");printf(" 04, 05, 06,n");printf(" 07, 08, 09, 10,n");printf("11, 12, 13, 14, 15n");/end of usage()/*=main starts here=*/int main( )int argc;int hole_num; / initial hole numbertime_t t;/ seed value for the random generatorunsigned long

32、l = 0; / attempt number to solve problem int trace = 0;/ when a solution is found, remember the stepsint i;/ loop counterint s;MOVE_SET step_to_solve100; / steps to the solution int rnd_move;/ for random selection in a move seta/* check if the user gave a valid scenario*/cout<<"請輸入孔洞的位置：&

33、quot;<<""cin>>argc;/cout<<”請輸入要解決的題目序號："/cin>>s;/* validate the hole# */hole_num = argc-1;if(!VALID_HOLE(hole_num)usage();exit(1);)/* create the hole on the pegboard */orig_pegboardhole_num = 0;srand(unsigned)time(NULL);/play until a solution is reached/while(s

34、tep_to_solvetrace.move_where=13) dowhile ( ! is_solved() )reset_pegboard(); get_all_moves();trace = 0;/ while(step_to_solvetrace.move_where=13) l+;/reset to the original problem/get # of moves, and the set of moves/initialize solution tracer/while there is a move that can be madeplay the game / dowhile ( move )/pick a movernd_move = rand() % move;/move pegmovepeg( move_setrnd_mo