算法課程設(shè)計資料

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

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

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

4、不確定。3剪枝考慮到深度確定這一點，在剪枝的時候就不能用”最短步數(shù)”這一個限制條 件了。由于對稱性，當(dāng)一個狀態(tài)被證實無解時，該狀態(tài)的旋轉(zhuǎn)、對稱變換后的同 構(gòu)體也必然無解。因此，可以利用這一特性，對已經(jīng)證實無解的狀態(tài)不再探索而 減少不必要的試探。4回溯法的基本思想回溯法又稱試探法，它采用試錯的思想，嘗試分步的去解決一個問題。在分 步解決問題的過程中，當(dāng)它通過嘗試發(fā)現(xiàn)現(xiàn)有的分步答案不能得到有效的正確的 解答的時候，它將取消上一步甚至是上幾步的計算， 再通過其它的可能的分步解 答再次嘗試尋找問題的答案?；厮莘ㄍǔＳ米詈唵蔚倪f歸方法來實現(xiàn)，在反復(fù)重 復(fù)上述的步驟后可能出現(xiàn)兩種情況：找到一個可能存在的正

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

6、件可用回溯法求解的問題P,通常要能表達為：對于已知的由n元組（xi,X2,， Xn）組成的一個狀態(tài)空間 E= （Xi, X2,，Xn） I Xi Si , i=1 , 2,，n,給 定關(guān)于n元組中的一個分量的一個約束集 D,要求E中滿足D的全部約束條件的 所有n元組。其中S是分量Xi的定義域，且|S i|有限，i=1 , 2,n。我們 稱E中滿足D的全部約束條件的任一 n元組為問題P的一個解。解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其 是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計算量是相 當(dāng)大的。我們發(fā)現(xiàn)，對于許多問題，所給定的約束集 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的解，因而就不必去搜索它們、檢測它們?；厮莘ㄕ轻槍?這類問題，利用這類問題的上述性質(zhì)而提出來的比枚舉法效率更高的算法。6回溯法的空間樹回溯法首先將問題P的n元組的狀態(tài)空間E表示成一棵高為n的帶權(quán)有序樹 T,把在E中求問題P的所有解轉(zhuǎn)化為在T中搜索問題P的所有解。樹T類似于 檢索樹，它可以這樣構(gòu)造：設(shè) S 中的元素可排成 Xi(1) , Xi(2),Xi(m-1) , |Si| =m, i=1 , 2, n。從根開始，讓T的第I層的每一個結(jié)點都有 m

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

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

11、子結(jié)點被稱為問題 P 的一個回答狀態(tài)結(jié)點，它對應(yīng)于問題 P的一個解7回溯法的基本步驟回溯法解決問題，一般有三個步驟：(1)針對所給問題，定義問題的解空間；(2) (2)確定易于搜索的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。三、算法設(shè)計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四、復(fù)雜性分析1時間復(fù)雜度該算法在最好情況下，求得第一種解需要試探 13次。因為每次的走法數(shù)目 不確定，也就是狀態(tài)數(shù)的子孩子數(shù)量不確定，

14、狀態(tài)總數(shù)量不確定。但是該數(shù)目不 大于215-2種。無解時，就是這種情況。對于要求所有的解時，需要遍歷整個狀態(tài)樹。2空間復(fù)雜度該算法需要維護一個狀態(tài)棧和一個走法棧。走法棧的深度不超過 13,為常數(shù)。 狀態(tài)空間樹只記錄當(dāng)前路徑有關(guān)的狀態(tài)。假設(shè)樹的平均子樹數(shù)目為 N,則該堆棧 的大小約為1/N。五、樣本測試、分析與總結(jié)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 、數(shù)據(jù)類型棋盤。正三角形的棋盤用數(shù)組很難表示。自定義最多有六個子節(jié)點的Node類，用雙向多維鏈表構(gòu)成圖，表示棋盤。但是這樣不適合隨機讀寫，切在判斷同 構(gòu)上沒有太大優(yōu)勢，因此采用變形的數(shù)組表示棋盤。把正三角形的棋盤上的孔左 對齊，用5*5的數(shù)組的左下半部分表示。此時，棋棒可以左右跳、上下跳、沿著 從左上到右下的對角線方向跳。狀態(tài)空間。把每一步的移動信息（從哪個坐標(biāo)到哪個坐標(biāo)）記錄下來，構(gòu)成 隱式多叉樹。因為用的是回溯法，故只需維護一個棋盤對象，根據(jù)走棋信息就可 以得到上下的棋盤狀態(tài)。堆棧。維護一個堆棧，把

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

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

19、.基于優(yōu)先級與回溯算法的排課系統(tǒng)的設(shè)計與實現(xiàn)D黑龍江大學(xué)出版社.20123 .（美）Anany Lev市n算法設(shè)計與分析基礎(chǔ)（第三版 影印版）清華大學(xué)出版 社.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