資源描述：
《回溯法的應用(實驗報告)》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。
1、華南師范大學本科生實驗報告姓名＿張俊發(fā)＿學號20082101032院系＿計算機學院＿專業(yè)＿計算機科學與技術＿年級2008級班級＿2班＿小組實驗任務分工＿獨立完成實驗時間2010年＿6＿月1＿日實驗名稱回溯法的應用指導老師及職稱陳振洲華南師范大學教務處編印實驗課程：算法分析與設計實驗名稱：回溯法的應用（綜設型實驗）第一部分實驗內(nèi)容1．實驗目標（1）熟悉使用回溯法求解問題的基本思路。（2）掌握回溯算法的程序實現(xiàn)方法。（3）理解回溯算法的特點。2.實驗任務（1）從所給定的題目中選擇一題，使用回溯法求解之。（2
2、）用文字來描述你的算法思路，包括解空間、限界函數(shù)、算法主要步驟等。（3）在Windows環(huán)境下使用C/C++語言編程實現(xiàn)算法。（4）記錄運行結果，包括輸入數(shù)據(jù)，問題解答及運行時間。（5）分析算法最壞情況下時間復雜度和空間復雜度。（6）談談實驗后的感想，包括關于該問題或類似問題的求解算法的建議。3.實驗設備及環(huán)境PC；C/C++等編程語言。4.實驗主要步驟(1)根據(jù)實驗目標，明確實驗的具體任務；(2)設計求解問題的回溯算法，并編寫程序實現(xiàn)算法；(3)設計實驗數(shù)據(jù)并運行程序、記錄運行的結果；(4)分析算法時
3、空性能；(5)實驗后的心得體會。第二部分問題及算法1.問題描述國際象棋的棋盤上有八八六十四個格子(這里簡化為5*6=30個格子),黑白相間,棋子放在格子中.棋中的馬走“日”字,即橫二豎一,或橫一豎二.馬從棋盤的某個格子出發(fā),走29步,是否能走過其他29個格子各一次?如果能夠,則說存在一條馬的周游路線.如果馬從某個格子出發(fā),不重復地走過了其余29個格子,第30步又回到了出發(fā)點,則說存在一條馬的周游閉路.按照從上到下，從左到右對棋盤的方格編號，如下所示：1?????2?????3?????4????5???
4、??67?????8?????9?????10????11????1213????14?????15????16?????17????1819????20??????21????22?????23????2425????26??????27????28?????29????30馬的走法是“日”字形路線，例如當馬在位置15的時候，它可以到達2、4、7、11、19、23、26和28。但是規(guī)定馬是不能跳出棋盤外的，例如從位置1只能到達9和14。2.回溯法的一般思路對于用回溯法求解的問題，首先要將問題進行適當?shù)?/p>
5、轉化，得出狀態(tài)空間樹。這棵樹的每條完整路徑都代表了一種解的可能。通過深度優(yōu)先搜索這棵樹，枚舉每種可能的解的情況；從而得出結果。回溯法中，首先需要明確下面三個概念：（一）約束函數(shù)：約束函數(shù)是根據(jù)題意定出的。通過描述合法解的一般特征用于去除不合法的解，從而避免繼續(xù)搜索出這個不合法解的剩余部分。因此，約束函數(shù)是對于任何狀態(tài)空間樹上的節(jié)點都有效、等價的。（二）狀態(tài)空間樹：剛剛已經(jīng)提到，狀態(tài)空間樹是一個對所有解的圖形描述。樹上的每個子節(jié)點的解都只有一個部分與父節(jié)點不同。（三）擴展節(jié)點、活結點、死結點：所謂擴展節(jié)點
6、，就是當前正在求出它的子節(jié)點的節(jié)點，在DFS中，只允許有一個擴展節(jié)點?；罱Y點就是通過與約束函數(shù)的對照，節(jié)點本身和其父節(jié)點均滿足約束函數(shù)要求的節(jié)點；死結點反之。由此很容易知道死結點是不必求出其子節(jié)點的（沒有意義）。2.求解問題的回溯算法描述Backtrack(x,y,dep);(1)棋盤board[5][6]每個點初始化為0，輸入起始點的坐標x,y，棋盤起始點board[x][y]賦值為1，保存起始點坐標為xstart,ystart,步數(shù)dep賦值為1。(2)每個點從八個方向去試探，若全部試完則轉(7)。
7、(3)通過約束函數(shù)check(x,y)檢查這一步是否還在棋盤內(nèi)，不是則轉(2)。(4)試探成功則，步數(shù)+1，board[x][y]=dep,前進一步再試探即遞歸調(diào)用Backtrack(x,y,dep);(5)正確解（步數(shù)等于30，下一步可以回到起始點）還未找到則轉(2)。(6)已找到一種解則記錄并打印。(7)退回一步（回溯），若未退到頭則轉(2)。(8)已退到頭則結束或打印無解。1.算法實現(xiàn)的關鍵技巧棋中的馬走“日”字,即橫二豎一,或橫一豎二，在每個點都有八個方向可以走，用一個二維數(shù)組dir[8][2]
8、={-1,-2,1,-2,2,-1,2,1,1,2,-1,2,-2,1,-2,-1}表示八個方向，則下一步可表示為x=x+dir[i][0],y=y+dir[i][1](0<=i<8)。遍歷每個方向時要用約束函數(shù)chack(x,y)檢查點是否合法，即0<=x<5,0<=y<6。第三部分實驗結果與分析1.實驗數(shù)據(jù)及結果118722316827217122319302161542692813241129202510514211217227618
