用回溯法求解一般哈密爾頓回路問題-資料下載頁
2025-01-09 18:57本頁面
【正文】 an(2)。 } 19 用回溯法求解一般哈密爾頓回路問題 設(shè)計(jì)環(huán)境 操作系統(tǒng)： Windows XP 設(shè)計(jì)工具： Microsoft Visual C++ 20 用回溯法求解一般哈密爾頓回路問題 4 調(diào)試分析 有哈密爾頓回路連通圖 1 4 3 2 5 6 21 用回溯法求解一般哈密爾頓回路問題 22 用回溯法求解一般哈密爾頓回路問題 無哈密爾頓回路連通圖 1 2 3 5 4 23 用回溯法求解一般哈密爾頓回路問題 5 總結(jié) 通過本次課程設(shè)計(jì)，本人 對(duì)算法設(shè)計(jì)與分析基礎(chǔ)有了更深的認(rèn)識(shí)，基本 掌握 了回溯法 求解一般 哈密 爾頓回路 的算法思路以及編程原理，提高了程序 開發(fā)的能力，讓能切實(shí)體會(huì)到 算法在編程過程 中的指導(dǎo)作用。通過課程設(shè)計(jì)，學(xué)會(huì)了按 課程設(shè)計(jì)的任務(wù) 要求完成各項(xiàng) 程序的開發(fā) ，對(duì)提高 自身編程 能力和項(xiàng)目管理能力有重要的現(xiàn)實(shí)意義。 在本次課程設(shè)計(jì)中，由于對(duì) 回溯法以及哈密爾頓回路的不熟悉，走了很多彎路，花了一些時(shí)間去了解其相關(guān)知識(shí) 。但是最后終于完成了自己的 課程設(shè)計(jì) ，自己覺得還是比較有成就感的。與此同時(shí)，我也發(fā)現(xiàn) 用回溯法求解一般哈密爾頓回路問題是一個(gè) np 問題，其時(shí)間復(fù)雜度是 O（ n ），空間復(fù)雜度是 O（ 2 ）。 通過這次的課 程設(shè)計(jì)，我學(xué)到了很多東西 ： 1． 多和別人交流，畢竟一個(gè)人所能想到的東西是有限的，但是通過和別人的交流，我發(fā)現(xiàn)我可以看到更多的東西了，例如：可能在程序的實(shí)現(xiàn)過程中，我并沒有注意到程序在運(yùn)行過程中會(huì)產(chǎn)生異常，但是在和別人的交流過程中，我發(fā)現(xiàn)了這個(gè)異常，促使我去捕獲它，使所開發(fā)的系統(tǒng)有了 更好 的健壯性。 2． 一個(gè)程序 的開發(fā)，需要開發(fā)人員用心去完成每一個(gè)階段的工作，這樣才不會(huì)出現(xiàn)開發(fā)到一半又忽然發(fā)現(xiàn)在某個(gè)地方出現(xiàn)了致命的錯(cuò)誤，需要重新開發(fā)的嚴(yán)重錯(cuò)誤，我想這就好像是在編程的時(shí)候需要避免“回溯”是一個(gè)道理，前期多做些工作，后期的 開發(fā)才會(huì)水到渠成，縮短開發(fā)周期 。 24 用回溯法求解一般哈密爾頓回路問題 致謝 能完成這個(gè) 課程設(shè)計(jì) ，我首先要感謝我的 指導(dǎo) 老師譚三老師， 在他嚴(yán)格的監(jiān)督和細(xì)心指導(dǎo)中，使我能夠堅(jiān)持完成本課程 ，并 能夠較好的實(shí)現(xiàn)要求 任務(wù) 書上所要求的功能，最后，我要感謝班上同學(xué)對(duì)我的幫助和指點(diǎn)。沒有他們的幫助和提供資料對(duì)于我 一個(gè)對(duì)編程知識(shí)不是很精通的人來說要想在短短的的時(shí)間里完成一個(gè)算法 的設(shè)計(jì)是幾乎不可能的事情。 在此表示最誠(chéng)摯的感謝！ 25 用回溯法求解一般哈密爾頓回路問題 參考文獻(xiàn) [1]《算法設(shè)計(jì)與分析》 宋 文等編 重慶大學(xué)出版社， 2022。 [2]《算法設(shè)計(jì)與分析》 周培德 電子工業(yè)出版社 ， 2022。 [3]《算法設(shè)計(jì)與分析》 王曉東 電子工業(yè)出版社， 2022 [4] 李登信 。關(guān)于 Cayley 圖的 Hamilton 性的一個(gè)猜想 [J]。渝州大學(xué)學(xué)報(bào) (自然科學(xué)版 )。1999 年 04 期 [5] 百度網(wǎng)站 [6] google網(wǎng)站 26 用回溯法求解一般哈密爾頓回路問題 附錄 該算法的具體實(shí)現(xiàn)主要代碼如下： int FirstAdjVex(const MGraphamp。 G,int v){//查找 v 的第一個(gè)鄰接點(diǎn) for(int i=0。i。i++){ if([v][i].adj!=0){ return i。 } } return 1。 } int NextAdjVex(const MGraphamp。 G,int v,int w){//查找 v 的（相對(duì)于 w 的）下一個(gè)鄰接點(diǎn) for(int i=w+1。i。i++){ if([v][i].adj!=0){ return i。 } } return 1。 } void initStatus(){ for(int i=0。iMAX_VERTEX_NUM。i++){ visitTag[i]=0。 x[i]=1。//初始化跟蹤棧，把所有已經(jīng)遍歷過的并且當(dāng)前已經(jīng)符合條件的點(diǎn)都放在這里面 } } bool testHami(const MGraphamp。 G){//用來測(cè)試是不是 Hami? for(int i=0。i。i++){ if(!visitTag[i]){ return 0。 } } 27 用回溯法求解一般哈密爾頓回路問題 return 1。 } void backtrack(const MGraphamp。 G,int t,int idxsum){ int i。 visitTag[t]=1。 x[idxsum]=t。//將節(jié)點(diǎn)的坐標(biāo)放到當(dāng)前棧里 for(i=FirstAdjVex(G,t)。i=0。i=NextAdjVex(G,t,i)){ if(!visitTag[i])backtrack(G,i,++idxsum)。 } if(testHami(G)){//找到 HAMI 通路 cout圖中存在的一條哈密頓通路是： endl。 for(i=0。i。i++){//輸出通路中相應(yīng)的節(jié)點(diǎn) if(x[i]=0amp。amp。x[i]=) cout[x[i] ] 。 } coutendl。 exit(0)。//提前結(jié)束 } visitTag[t]=0。//回朔也使它的訪問標(biāo)志為 0，為了下一次的訪問 x[idxsum]=1。//清空它，說明當(dāng)前點(diǎn)是不符合條件的， } void Hami(const MGraphamp。 G){ if(){ cout非連通圖 endl。 return。 } for(int i=0。i。i++){//必須查看從所有點(diǎn)開始的所有路徑 initStatus()。//設(shè)置狀態(tài) backtrack(G,i,0)。//試探由 [i]出發(fā)是不是有通路 } cout沒有找到通路 endl。 } void main() { MGraph G。 CreatUDN(G)。 dispMGraph(G)。 Hami(G)。 }
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1