回溯法求解哈密爾頓回路

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

2、溯法求解哈密頓爾回路算法.1 2.2 非遞歸回溯法求解哈密頓爾回路算法.2 3 設(shè)計(jì)方案設(shè)計(jì)方案.3 3.1 整體設(shè)計(jì)方案.3 3.2 程序遞歸算法的主要代碼 .3 3.3 程序非遞歸算法的主要代碼.4 3.4 程序的其他函數(shù).5 4 系統(tǒng)測(cè)試系統(tǒng)測(cè)試.6 4.1 測(cè)試數(shù)據(jù).6 4.2 程序的錄入、編譯和連接.7 4.3 運(yùn)行程序.7 4.4 進(jìn)入主界面.8 4.4 測(cè)試遞歸回溯法求解圖的所有哈密頓爾回路.8 4.5 測(cè)試非遞歸回溯法求解圖的所有哈密頓爾回路.9 4.6 測(cè)試第二組數(shù)據(jù).9 4.7 測(cè)試退出模塊.10 結(jié)結(jié) 論論.11 致致 謝謝.12 參考文獻(xiàn)參考文獻(xiàn).13 回溯法求解一般哈

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

4、起點(diǎn)的回路。 1.2 任務(wù)與分析任務(wù)與分析 本課程設(shè)計(jì)主要的目的是： 通過(guò)回溯的方法找出圖的一般哈密頓爾回路，并且能夠輸出。 題目分析： 回溯法是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問(wèn)題的所有解 的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空 間樹的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問(wèn)題的解。如果肯定不包含， 則跳過(guò)對(duì)以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點(diǎn)回溯。否則，進(jìn)入該子 樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索?；厮莘ㄔ谟脕?lái)求問(wèn)題的所有解時(shí)，要回溯到根， 且根結(jié)點(diǎn)的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來(lái)求問(wèn)題的任一解時(shí)，只要 搜索到問(wèn)

5、題的一個(gè)解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問(wèn)題的解的算法 稱為回溯法，它適用于解一些組合數(shù)較大的問(wèn)題。 哈密頓回路：從某頂點(diǎn)開(kāi)始，經(jīng)過(guò)圖 g 全部頂點(diǎn)一次回到起點(diǎn)的回路。 2 算法算法 2.1 遞歸回溯法求解哈密頓爾回路算法遞歸回溯法求解哈密頓爾回路算法 2.1.12.1.1 遞歸求圖的所有哈密頓爾回路算法遞歸求圖的所有哈密頓爾回路算法 1）解向量用數(shù)組 x1.n表示；xk=0 無(wú)合法頂點(diǎn)；x 數(shù)組初始化為 0； 2）若 k=n 時(shí)，需檢查 xk是否有邊與 x1相連（回到起點(diǎn)，構(gòu)成回路） 3）用 k = 1 啟動(dòng)（指定哈密頓回路的起點(diǎn)） 由此可得以下算法： status hamilt

6、on(int k ) 回溯法求解一般哈密頓爾回路 2 if(kn-1 flag=1; else for(int i=k;i=1) 3.1 xk=xk+1，搜索下一個(gè)頂點(diǎn); 3.2 若(n 個(gè)頂點(diǎn)沒(méi)有被窮舉) 執(zhí)行下列操作 3.2.1 若(頂點(diǎn) xk不在哈密頓回路上 3.2.2 否則，xk=xk+1，搜索下一個(gè)頂點(diǎn)； 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，取消頂點(diǎn) xk的訪問(wèn)標(biāo)志， 轉(zhuǎn)步驟 3； 3 設(shè)計(jì)方案設(shè)計(jì)方案 3.1 整體

7、設(shè)計(jì)方案整體設(shè)計(jì)方案 這兩個(gè)算法是通過(guò) c+語(yǔ)言編程實(shí)現(xiàn)的，在主菜單欄可以分成三塊：1、遞歸求圖 的所有哈密頓回路 2、非遞歸求圖的所有哈密頓回路 0、退出程序。 3.2 程序遞歸算法的主要代碼程序遞歸算法的主要代碼 void hamilton(int k ) /遞歸算法 if(kn-1 flag=1; else for(int i=k;in;i+) 回溯法求解一般哈密頓爾回路 4 swap(xk,xi); if ( cxk-1xk=1) hamilton(k+1); swap(xi,xk); 3.3 程序非遞歸算法的主要代碼程序非遞歸算法的主要代碼 void hamilton(int n,

8、int xn, bool cnn) /非遞歸算法 int i, k; bool*visited = new booln; for(i =0; i =1) xk+; while(xk n) if(visitedxk=0 else xk+; if(xk n kn;k+) coutxk ; flag=1; coutendl; k-; else if (xkn k+; else xk=0; k-; visitedxk=0; 3.4 程序的其他函數(shù)程序的其他函數(shù) 3.4.13.4.1 輸出函數(shù)主要代碼輸出函數(shù)主要代碼 void output(int x) /輸出函數(shù) for(int i=0;in;i+)

9、 coutxi ; coutendl; 回溯法求解一般哈密頓爾回路 6 3.4.23.4.2 建立鄰接矩陣函數(shù)建立鄰接矩陣函數(shù) void creat_m() /建立鄰接矩陣 memset(c, 0, sizeof(c); int i=0; coutn; cout請(qǐng)輸入n階鄰接矩陣：endl; for(i=0;in;i+) for(int j=0;jcij; 4 系統(tǒng)測(cè)試系統(tǒng)測(cè)試 首先進(jìn)入 vc+6.0，打開(kāi)源程序文件 “哈密頓回路（遞歸與非遞歸）.cpp” ，然 后進(jìn)入源程序，接著選擇 build 下的 execute person.exe 即可,也可以不打開(kāi)工程， 直接雙擊“哈密頓回路（遞歸

10、與非遞歸）.exe”也可以直接運(yùn)行程序。 4.1 測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù) 第一組數(shù)據(jù)位 4 階完全圖，第二組數(shù)據(jù)為 3 階完全圖。 4.2 程序的錄入、編譯和連接程序的錄入、編譯和連接 如圖 4.1 所示。 第二組：0 1 1 1 0 1 1 1 0 第一組：0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 回溯法求解一般哈密頓爾回路 7 圖 4.1 源程序的錄入、編譯和連接 4.3 運(yùn)行程序運(yùn)行程序 如圖 4.2 所示。 圖 4.2 運(yùn)行程序 從圖中可見(jiàn)程序能夠成功的運(yùn)行。 4.4 進(jìn)入主界面進(jìn)入主界面 如圖 4.3 所示。 回溯法求解一般哈密頓爾回路 8 4.4 測(cè)試遞歸回溯法求解

11、圖的所有哈密頓爾回路測(cè)試遞歸回溯法求解圖的所有哈密頓爾回路 首先輸入操作 1，顯示如圖 4.4 界面。 圖 4.4 遞歸界面 輸入第一組數(shù)據(jù)信息，為 4 階矩陣。如圖 4.5 所示 圖 4.3 菜單界面 回溯法求解一般哈密頓爾回路 9 圖 4.5 遞歸回溯法求解哈密頓爾回路 從上圖可見(jiàn)能夠回溯法遞歸輸出圖的哈密頓爾回路功能。 4.5 測(cè)試非遞歸回溯法求解圖的所有哈密頓爾回路測(cè)試非遞歸回溯法求解圖的所有哈密頓爾回路 在主界面下輸入 2 號(hào)功能鍵，將顯示讀者所有已借圖書信息。如圖 4.6 所示。 圖 4.6 非遞歸回溯法求解哈密頓爾回路 程序與遞歸的結(jié)果一樣，正確顯示出 4 階完全圖的哈密頓爾回路

12、，模塊測(cè)試完成。 4.6 測(cè)試第二組數(shù)據(jù)測(cè)試第二組數(shù)據(jù) 按照測(cè)試第一組數(shù)據(jù)的步驟，測(cè)試第二組 3 階完全圖鄰接矩陣。測(cè)試結(jié)果分別如 圖 4.7 和 4.8 所示。 回溯法求解一般哈密頓爾回路 10 圖 4.7 遞歸測(cè)試第二組數(shù)據(jù)結(jié)果 圖 4.8 非遞歸測(cè)試第二組數(shù)據(jù)結(jié)果 如圖可以說(shuō)明，成功地輸出了 3 階完全圖的哈密頓爾回路。 4.7 測(cè)試退出模塊測(cè)試退出模塊 在主界面下輸入 0 號(hào)功能鍵，觀察結(jié)果。圖 4.9 所示。 圖 4.9 程序退出 回溯法求解一般哈密頓爾回路 11 結(jié)結(jié) 論論 本次課程設(shè)計(jì)的題目是用回溯法求解一般哈密頓爾回路問(wèn)題，旨在了解回溯法以 及用這種方法求解圖中的哈密頓爾回路回

13、路，方便我們尋找某些復(fù)雜的圖形的哈密頓 爾回路。通過(guò)這次課程設(shè)計(jì)，使我了解了算法的設(shè)計(jì)與分析的重要性，使我明白了算 法的設(shè)計(jì)和分析與當(dāng)今社會(huì)的發(fā)展息息相關(guān)，并且提高了自身運(yùn)用知識(shí)和變通知識(shí)的 能力。 在這個(gè)課程設(shè)計(jì)中，我我首先通過(guò)課堂所學(xué)習(xí)的回溯法找出了簡(jiǎn)單的解哈密頓爾 回路的方法，然后通過(guò)課后的資料使解法更加深入化，最后通過(guò)反復(fù)推敲得到了比較 精確的解題算。由此，我寫了遞歸版和非遞歸版兩個(gè)算法，這兩個(gè)算法各有各的特點(diǎn)， 但是其宗旨是不變的，就是運(yùn)用回溯法解題，只是通過(guò)不同的數(shù)據(jù)結(jié)構(gòu)表達(dá)出來(lái)。最 后，結(jié)合所學(xué)過(guò)的 c+語(yǔ)言知識(shí)，編出來(lái)相對(duì)應(yīng)的遞歸和非遞歸回溯法解哈密頓爾回路 的程序，經(jīng)測(cè)試我的

14、算法和程序是正確的。但是這個(gè)程序尚且不夠完善，由于本人的 水平有限，暫時(shí)無(wú)法使用 mfc 來(lái)實(shí)現(xiàn)可視化的界面，程序中也存在著很多可以延伸的 問(wèn)題有待解決。 總之，通過(guò)這次課程設(shè)計(jì)，不僅提高了自己的算法設(shè)計(jì)與分析能力，而且提高了 對(duì) c+編程語(yǔ)言的操作水平。雖然程序尚不完美，但是能將自己的知識(shí)運(yùn)用到實(shí)際已經(jīng) 是很大的成功。 回溯法求解一般哈密頓爾回路 12 致致 謝謝 感謝謝春芝老師本學(xué)期對(duì)我課程設(shè)計(jì)的教導(dǎo)，感謝黃襄念老師辛勤栽培，他們給 予了我莫大的支柱。感謝我身邊的同學(xué)們，感謝所有幫助過(guò)我的人。如果沒(méi)有你們的 幫助，這次課程設(shè)計(jì)很難一個(gè)人完成，在此我致以衷心的謝意。 回溯法求解一般哈密頓爾回

15、路 13 參考文獻(xiàn)參考文獻(xiàn) 1 嚴(yán)蔚敏 吳偉民 著. 數(shù)據(jù)結(jié)構(gòu) （c 語(yǔ)言版）(第三版). 北京：清華大學(xué)出版社 2007.4 2 譚浩強(qiáng) 著. c 程序設(shè)計(jì)(第三版).北京：清華大學(xué)出版社；2006.9 3 anany levitin 著. 潘彥 譯 算法設(shè)計(jì)與分析基礎(chǔ)(第二版).北京：清華大學(xué) 出版社；2010.1 4 美 s 巴斯 著.計(jì)算機(jī)算法：設(shè)計(jì)和分析引論. 朱洪等譯 上海：復(fù)旦大學(xué)出版社； 1985.1 回溯法求解一般哈密頓爾回路 14 附錄附錄 #include #include using namespace std; #define n 20 bool cnn; int x

16、n; int n; bool flag =0; void output(int x) /輸出函數(shù) for(int i=0;in;i+) coutxi ; coutn-1 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 = new booln; for(i =0; i =1) xk+; while(xk n) if(visitedx

17、k=0 else xk+; if(xk n kn;k+) 回溯法求解一般哈密頓爾回路 15 coutxk ; flag=1; coutendl; k-; else if (xkn k+; else xk=0; k-; visitedxk=0; void creat_m() /建立鄰接矩陣 memset(c, 0, sizeof(c); int i=0; coutn; cout請(qǐng)輸入n階鄰接矩陣：endl; for(i=0;in;i+) for(int j=0;jcij; void menu() int order,i; cout .endl; cout . 菜單 .endl; cout .en

18、dlendl; cout . 1 回溯法求圖的所有哈密頓回路（遞歸） .endlendl; cout . 2 回溯法求圖的所有哈密頓回路（非遞歸） .endlendl; cout . 0 退出程序 .endlendl; cout .endl; cout .endlendl; coutorder; switch(order) case 1: system(cls); coutt.創(chuàng)建鄰接矩陣.endl; 回溯法求解一般哈密頓爾回路 16 creat_m(); coutt.回溯法求圖的所有哈密頓回路（遞歸）. .endl; for(i = 0; i n; i+) xi = i; hamilton(1); if(!flag) cout無(wú)哈密頓回路!endl; system(pause); system(cls); menu(); break; case 2: system(cls); coutt.創(chuàng)建鄰接矩陣.endl; creat_m(); coutt.回溯法求圖的所有哈密頓回路（非遞歸）. .endl;