9、回溯法求解哈密爾頓回路

1、數(shù)學與計算機學院課程設計說明書課 程 名 稱: 算法設計與分析-課程設計 課 程 代 碼: 7106620 題 目: 回溯法求解一般哈密爾頓回路 年級/專業(yè)/班: 學 生 姓 名: 學 號: 開 始 時 間: 2010 年 12 月 27 日完 成 時 間: 2011 年 01 月 07 日課程設計成績：學習態(tài)度及平時成績（30）技術(shù)水平與實際能力（20）創(chuàng)新（5）說明書撰寫質(zhì)量（45）總 分（100）指導教師簽名： 年 月 日 回溯法求解一般哈密頓爾回路目 錄1 引引 言言.11.1 問題的提出 .11.2 任務與分析.12 算法算法.12.1 遞歸回溯法求解哈密頓爾回路算法.12.2 非遞

2、歸回溯法求解哈密頓爾回路算法.23 設計方案設計方案.33.1 整體設計方案.33.2 程序遞歸算法的主要代碼 .33.3 程序非遞歸算法的主要代碼.43.4 程序的其他函數(shù).54 系統(tǒng)測試系統(tǒng)測試.64.1 測試數(shù)據(jù).64.2 程序的錄入、編譯和連接.74.3 運行程序.74.4 進入主界面.84.4 測試遞歸回溯法求解圖的所有哈密頓爾回路.84.5 測試非遞歸回溯法求解圖的所有哈密頓爾回路.94.6 測試第二組數(shù)據(jù).94.7 測試退出模塊.10結(jié)結(jié) 論論.11致致 謝謝.12參考文獻參考文獻.13 回溯法求解一般哈密頓爾回路摘摘 要要本次我的課程設計題目是“用回溯法求解一般哈密爾頓回路問題

3、” ，主要內(nèi)容是給出用回溯法求解一般哈密爾頓回路問題的算法并編程實現(xiàn)。所涉及到的知識是算法設計與分析中的回溯法，以及圖論中的哈密頓爾回路?；厮莘ǎ簭母Y(jié)點出發(fā)，按照深度優(yōu)先策略遍歷解空間樹，搜索滿足約束條件的解。哈密頓回路：從某頂點開始，經(jīng)過圖 G 全部頂點一次回到起點的回路。關(guān)鍵詞：關(guān)鍵詞：回溯法 哈密頓爾回路 算法 編程實現(xiàn) 回溯法求解一般哈密頓爾回路11 引引 言言1.1 問題的提出問題的提出 我所做的課程設計就是用回溯法求解一般哈密爾頓回路問題，即從某頂點開始，經(jīng)過圖 G 全部頂點一次回到起點的回路。1.2 任務與分析任務與分析 本課程設計主要的目的是：通過回溯的方法找出圖的一般哈密頓

4、爾回路，并且能夠輸出。題目分析：回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點時，總是先判斷該結(jié)點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。否則，進入該子樹，繼續(xù)按深度優(yōu)先的策略進行搜索?；厮莘ㄔ谟脕砬髥栴}的所有解時，要回溯到根，且根結(jié)點的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。哈密頓回

5、路：從某頂點開始，經(jīng)過圖 G 全部頂點一次回到起點的回路。2 算法算法2.1 遞歸回溯法求解哈密頓爾回路算法遞歸回溯法求解哈密頓爾回路算法2.1.12.1.1 遞歸求圖的所有哈密頓爾回路算法遞歸求圖的所有哈密頓爾回路算法1）解向量用數(shù)組 X1.n表示；Xk=0 無合法頂點；X 數(shù)組初始化為 0；2）若 k=n 時，需檢查 xk是否有邊與 x1相連（回到起點，構(gòu)成回路）3）用 k = 1 啟動（指定哈密頓回路的起點）由此可得以下算法：status hamilton(int k ) 回溯法求解一般哈密頓爾回路2 if(kn-1 & cxk-10=1) output(x);flag=1; e

6、lse for(int i=k;i=1) 3.1 xk=xk+1，搜索下一個頂點; 3.2 若(n 個頂點沒有被窮舉) 執(zhí)行下列操作 3.2.1 若(頂點 xk不在哈密頓回路上&(xk-1,xk)E)， 轉(zhuǎn)步驟 3.3; 3.2.2 否則，xk=xk+1，搜索下一個頂點； 3.3 若數(shù)組 xn已形成哈密頓路徑，則輸出數(shù)組 xn，算法結(jié)束； 3.4 否則， 3.4.1 若數(shù)組 xn構(gòu)成哈密頓路徑的部分解， 則 k=k+1，轉(zhuǎn)步驟 3； 3.4.2 否則，重置 xk，k=k-1，取消頂點 xk的訪問標志， 轉(zhuǎn)步驟 3；3 設計方案設計方案3.1 整體設計方案整體設計方案這兩個算法是通過 C

7、+語言編程實現(xiàn)的，在主菜單欄可以分成三塊：1、遞歸求圖的所有哈密頓回路 2、非遞歸求圖的所有哈密頓回路 0、退出程序。3.2 程序遞歸算法的主要代碼程序遞歸算法的主要代碼void hamilton(int k ) 回溯法求解一般哈密頓爾回路4/遞歸算法 if(kn-1 & cxk-10=1) output(x);flag=1; else for(int i=k;in;i+) swap(xk,xi); if ( cxk-1xk=1) hamilton(k+1); swap(xi,xk); 3.3 程序非遞歸算法的主要代碼程序非遞歸算法的主要代碼void hamilton(int n, i

8、nt xN, bool cNN)/非遞歸算法 int i, k; bool*visited = new booln; for(i =0; i =1) 回溯法求解一般哈密頓爾回路5 xk+; while(xk n) if(visitedxk=0 & cxk - 1xk=1) break; elsexk+; if(xk n & k=n-1 & cxk0=1) for(k=0;kn;k+) coutxk ; flag=1; coutendl; k-; else if (xkn & kn-1)/k!=n-1) visitedxk=1; k+; else xk=0; k-

9、; visitedxk=0; 回溯法求解一般哈密頓爾回路63.4 程序的其他函數(shù)程序的其他函數(shù)3.4.13.4.1 輸出函數(shù)主要代碼輸出函數(shù)主要代碼void output(int x)/輸出函數(shù) for(int i=0;in;i+) coutxi ; coutendl;3.4.23.4.2 建立鄰接矩陣函數(shù)建立鄰接矩陣函數(shù)void Creat_M()/建立鄰接矩陣 memset(c, 0, sizeof(c); int i=0;coutn;cout請輸入n階鄰接矩陣：endl;for(i=0;in;i+)for(int j=0;jcij;4 系統(tǒng)測試系統(tǒng)測試首先進入 VC+6.0，打開源程序文

10、件 “哈密頓回路（遞歸與非遞歸）.cpp” ，然后進入源程序，接著選擇 Build 下的 Execute person.exe 即可,也可以不打開工程， 回溯法求解一般哈密頓爾回路7直接雙擊“哈密頓回路（遞歸與非遞歸）.exe”也可以直接運行程序。4.1 測試數(shù)據(jù)測試數(shù)據(jù)第一組數(shù)據(jù)位 4 階完全圖，第二組數(shù)據(jù)為 3 階完全圖。4.2 程序的錄入、編譯和連接程序的錄入、編譯和連接如圖 4.1 所示。 圖 4.1 源程序的錄入、編譯和連接4.3 運行程序運行程序如圖 4.2 所示。第二組：0 1 11 0 11 1 0第一組：0 1 1 11 0 1 11 1 0 11 1 1 0 回溯法求解一般

11、哈密頓爾回路8 圖 4.2 運行程序從圖中可見程序能夠成功的運行。4.4 進入主界面進入主界面如圖 4.3 所示。 4.4 測試遞歸回溯法求解圖的所有哈密頓爾回路測試遞歸回溯法求解圖的所有哈密頓爾回路首先輸入操作 1，顯示如圖 4.4 界面。圖 4.3 菜單界面 回溯法求解一般哈密頓爾回路9 圖 4.4 遞歸界面輸入第一組數(shù)據(jù)信息，為 4 階矩陣。如圖 4.5 所示 圖 4.5 遞歸回溯法求解哈密頓爾回路從上圖可見能夠回溯法遞歸輸出圖的哈密頓爾回路功能。4.5 測試非遞歸回溯法求解圖的所有哈密頓爾回路測試非遞歸回溯法求解圖的所有哈密頓爾回路在主界面下輸入 2 號功能鍵，將顯示讀者所有已借圖書信

12、息。如圖 4.6 所示。 回溯法求解一般哈密頓爾回路10 圖 4.6 非遞歸回溯法求解哈密頓爾回路程序與遞歸的結(jié)果一樣，正確顯示出 4 階完全圖的哈密頓爾回路，模塊測試完成。4.6 測試第二組數(shù)據(jù)測試第二組數(shù)據(jù)按照測試第一組數(shù)據(jù)的步驟，測試第二組 3 階完全圖鄰接矩陣。測試結(jié)果分別如圖 4.7 和 4.8 所示。 圖 4.7 遞歸測試第二組數(shù)據(jù)結(jié)果 回溯法求解一般哈密頓爾回路11 圖 4.8 非遞歸測試第二組數(shù)據(jù)結(jié)果如圖可以說明，成功地輸出了 3 階完全圖的哈密頓爾回路。4.7 測試退出模塊測試退出模塊 在主界面下輸入 0 號功能鍵，觀察結(jié)果。圖 4.9 所示。 圖 4.9 程序退出結(jié)結(jié) 論論

13、本次課程設計的題目是用回溯法求解一般哈密頓爾回路問題，旨在了解回溯法以及用這種方法求解圖中的哈密頓爾回路回路，方便我們尋找某些復雜的圖形的哈密頓爾回路。通過這次課程設計，使我了解了算法的設計與分析的重要性，使我明白了算法的設計和分析與當今社會的發(fā)展息息相關(guān)，并且提高了自身運用知識和變通知識的能力。在這個課程設計中，我我首先通過課堂所學習的回溯法找出了簡單的解哈密頓爾回路的方法，然后通過課后的資料使解法更加深入化，最后通過反復推敲得到了比較精確的解題算。由此，我寫了遞歸版和非遞歸版兩個算法，這兩個算法各有各的特點， 回溯法求解一般哈密頓爾回路12但是其宗旨是不變的，就是運用回溯法解題，只是通過不

14、同的數(shù)據(jù)結(jié)構(gòu)表達出來。最后，結(jié)合所學過的 C+語言知識，編出來相對應的遞歸和非遞歸回溯法解哈密頓爾回路的程序，經(jīng)測試我的算法和程序是正確的。但是這個程序尚且不夠完善，由于本人的水平有限，暫時無法使用 MFC 來實現(xiàn)可視化的界面，程序中也存在著很多可以延伸的問題有待解決?？傊?，通過這次課程設計，不僅提高了自己的算法設計與分析能力，而且提高了對 c+編程語言的操作水平。雖然程序尚不完美，但是能將自己的知識運用到實際已經(jīng)是很大的成功。 回溯法求解一般哈密頓爾回路13致致 謝謝感謝謝春芝老師本學期對我課程設計的教導，感謝黃襄念老師辛勤栽培，他們給予了我莫大的支柱。感謝我身邊的同學們，感謝所有幫助過我的

15、人。如果沒有你們的幫助，這次課程設計很難一個人完成，在此我致以衷心的謝意。 回溯法求解一般哈密頓爾回路14參考文獻參考文獻1 嚴蔚敏 吳偉民 著. 數(shù)據(jù)結(jié)構(gòu) （C 語言版）(第三版). 北京：清華大學出版社2007.42 譚浩強 著. C 程序設計(第三版).北京：清華大學出版社；2006.93 Anany Levitin 著. 潘彥 譯 算法設計與分析基礎(第二版).北京：清華大學出版社；2010.14 美 S 巴斯 著.計算機算法：設計和分析引論. 朱洪等譯 上海：復旦大學出版社；1985.1 回溯法求解一般哈密頓爾回路15附錄附錄#include #include using names

16、pace std;#define N 20bool cNN;int xN;int n;bool flag =0;void output(int x)/輸出函數(shù) for(int i=0;in;i+) coutxi ; coutn-1 & cxk-10=1) output(x);flag=1; else for(int i=k;in;i+) swap(xk,xi); if ( cxk-1xk=1) hamilton(k+1); swap(xi,xk); void hamilton(int n, int xN, bool cNN)/非遞歸算法 int i, k; bool*visited =

17、 new booln; for(i =0; i =1) xk+; while(xk n) if(visitedxk=0 & cxk - 1xk=1) break; elsexk+; if(xk n & k=n-1 & cxk0=1) for(k=0;kn;k+) 回溯法求解一般哈密頓爾回路16 coutxk ; flag=1; coutendl; k-; else if (xkn & kn-1)/k!=n-1) visitedxk=1; k+; else xk=0; k-; visitedxk=0; void Creat_M()/建立鄰接矩陣 memset(c,

18、 0, sizeof(c); int i=0;coutn;cout請輸入n階鄰接矩陣：endl;for(i=0;in;i+)for(int j=0;jcij;void menu()int order,i; cout .endl; cout . 菜單 .endl; cout .endlendl; cout . 1 回溯法求圖的所有哈密頓回路（遞歸） .endlendl; cout . 2 回溯法求圖的所有哈密頓回路（非遞歸） .endlendl; cout . 0 退出程序 .endlendl; cout .endl; cout .endlendl; coutorder; switch(order) case 1: system(cls); coutt.創(chuàng)建鄰接矩陣.endl; 回溯法求解一般哈密頓爾回路17 Creat_M(); coutt.回溯法求圖的所有哈密頓回路（遞歸）.endl; for(i = 0; i n; i+) xi = i; hamilton(1); if(!flag) cout無哈密頓回路!endl; system(pause); system(cls); menu(); break; case 2: system(cls); coutt.創(chuàng)建鄰接矩陣.endl; Creat_M(); coutt.回溯法求圖的所有哈密頓回路