<acronym id="yw0ww"><small id="yw0ww"></small></acronym>
<acronym id="yw0ww"></acronym>
<acronym id="yw0ww"><center id="yw0ww"></center></acronym>

回溯法(馬周游問題)——實驗報告.doc 14頁

  • 58
  • 0
  • 0
  • 2015-12-21 發布

回溯法(馬周游問題)——實驗報告.doc

文檔工具:
    1. 1、本文檔共14頁,可閱讀全部內容。
    2. 2、本文檔內容版權歸屬內容提供方,所產生的收益全部歸內容提供方所有。如果您對本文有版權爭議,可選擇認領,認領后既往收益都歸您。
    3. 3、本文檔由用戶上傳,本站不保證質量和數量令人滿意,可能有諸多瑕疵,付費之前,請仔細先通過免費閱讀內容等途徑辨別內容交易風險。如存在嚴重掛羊頭賣狗肉之情形,可聯系本站下載客服投訴處理。
    4. 文檔侵權舉報電話:19940600175。
    華南師范大學本科生實驗報告 姓名_黎國莊_ 學號 20062101247 院系_計算機學院 專業_計算機科學與技術 年級 2006級 班級_2班 _ 小組實驗任務分工_ 獨立完成 實驗時間 2008 年_6_月 3 _日 實驗名稱 回溯法的應用 指導老師及職稱 陳衛東老師 華南師范大學教務處編印 實驗課程:算法分析與設計 實驗名稱:回溯法的應用 (綜設型實驗) 第一部分 實驗內容 1.實驗目標 (1) 熟悉使用回溯法求解問題的基本思路。 (2)掌握回溯算法的程序實現方法。 (3)理解回溯算法的特點。 2. 實驗任務 (1)從所給定的題目中選擇一題,使用回溯法求解之。 (2)用文字來描述你的算法思路,包括解空間、限界函數、算法主要步驟等。 (3)在Windows環境下使用C/C++語言編程實現算法。 (4)記錄運行結果,包括輸入數據,問題解答及運行時間。 (5)分析算法最壞情況下時間復雜度和空間復雜度。 (6)談談實驗后的感想,包括關于該問題或類似問題的求解算法的建議。 3. 實驗設備及環境 PC;C/C++等編程語言。 4. 實驗主要步驟 根據實驗目標,明確實驗的具體任務; 設計求解問題的回溯算法,并編寫程序實現算法; 設計實驗數據并運行程序、記錄運行的結果; 分析算法時空性能; 實驗后的心得體會。 第二部分 問題及算法 問題描述 給出一個88的棋盤,一個放在棋盤某個位置上的馬(規定馬的走法為走“日”)是否可以好訪問每個方格一次,并回到起始位置上?對于馬所在其中一格時,它可以走的位置有以下8種情況: 馬 所以對于每一個馬所在的格子里,馬可以走對應的8個方向。 用滿8叉樹,每一個子樹對應馬可跳的方向 當要走下一子樹(跳下一格)時,該子樹可走(還沒有走過并且在棋盤里邊),即沿該方向走下去,當不可以走,即回溯到上一步,選擇另一方向往下走;當該子樹的8個子棋都遍歷完了(即8個方向都走過了),則回溯到它父親那里。 重復一直做下去,到棋盤每個格子都走過一遍,而且回到出發點或者找不到路徑即結束。算法如下: 輸入:V(x,y)馬開始的起點 輸出:馬從第一步到最后一步(64)的先后次序數字沒有被窮舉 6. x← X中的下一個元素;將x加入v 7. if v為最終解then set flag ← true,且從兩個while循環退出 8. else if v是部分解then k ← k+1 {前進} 9. end while 10. 重置X,使得下一個元素排在第一位 11. K ← k-1 {回溯} 12.end while 13.if flag then output v 14.else output “no solution” 4. 算法實現的關鍵技巧 void exit(point p) 參數:point 功能:計算出下一步可能位置,按其各個位置下一個位置的和壓棧到s[]中 算法描述:接受參數傳來的值,按次序加上 int horizontal[]={2,1,-1,-2,-2,-1,1,2}; int vertical[]={-1,-2,-2,-1,1,2,2,1}; 再根據legal函數來判斷是否合法(x(0~7),y(0~7))是,則保存在point ap[]中,再按各自下一步的數目從大到小排序。最后,將ap[]中的點壓棧。 int number(point p) 參數:point 功能:找出當前位置下一步的各種可能位置,計算可能之和 算法描述:接受參數傳來的值,按次序加上 int horizontal[]={2,1,-1,-2,-2,-1,1,2}; int vertical[]={-1,-2,-2,-1,1,2,2,1}; 再根據legal函數來判斷是否合法(x(0~7),y(0~7))是,則加1并將值返回 void next(point p) 參數:point 功能:/找出各個位置并將其步數記錄 算法描述:將其步數記錄在board[][]的相應位置,并將這點壓棧到s1,判斷步數是否小于64,再根據這四個條件選擇執行其中的一個,再遞歸調用next. bool legal(point p) 參數:point 功能:判斷是否可行,合法(是否在棋盤上,是否走過) 算法描述 :用這樣的語句if((p.x>=0)&&(p.x<n)&&(p.y<n)&&(p.y>=0)&&(board[p.x][p.y]==0)) return true; else return false; 第三部分 實驗結果與分析 實驗數據及結果 測試數據和運行輸

    文檔評論(0)

    • 內容提供方:youyang99
    • 審核時間:2015-12-21
    • 審核編號:8030134111000037

    相關文檔

    5分彩官网