用回溯法求解一般哈密爾頓回路問題

1、目 錄 引言- 1 -1 需求分析- 2 -1.1問題的提出- 2 -1.2問題的描述- 2 -1.3算法的描述- 3 -2 概要設計- 4 -2.1系統(tǒng)運行環(huán)境- 4 -2.2算法的實現(xiàn)- 4 -2.3接口設計- 12 -2.4出錯處理設計- 12 -2.5維護設計- 13 -3 詳細設計- 14 -3.1算法的分析- 14 -3.2程序的思路- 15 -3.3程序的實現(xiàn)- 15 -3.4設計環(huán)境- 19 -4 調(diào)試分析- 20 -4.1有哈密爾頓回路連通圖- 20 -4.2無哈密爾頓回路連通圖- 22 -5 總結(jié)- 23 -參考文獻- 25 -附錄- 26 - 摘 要 回溯法是一種按照深度

2、優(yōu)先的策略從根結(jié)點開始搜索解空間樹的算法，該算法既帶有系統(tǒng)性又帶有跳躍性，它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根節(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一節(jié)點時，總是先判定該節(jié)點是否肯定不包含問題的解，如果肯定不包含，則跳過對以該節(jié)點為跟的子樹的系統(tǒng)搜索，逐層向其祖先節(jié)點回溯。否則，進入該子樹，繼續(xù)按深度優(yōu)先的策略進行探索。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法。回溯法可以用來求出問題的全部解，也可以在求出問題的一個解之后停止對問題的求解，即只求該問題是否有解。它適用于解一些組合數(shù)較大的問題。哈密爾頓回路路就是判斷圖中是否存在一條通過所有頂點一次且僅一次

3、的路徑。本文主要講的就是用回溯法來求解一個任意的圖中是否存在一條哈密頓通路的問題，并用具體的算法來實現(xiàn)它。 關(guān)鍵詞：回溯法 哈密爾頓回路 空間樹 引言回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹1。算法搜索至解空間樹的任一結(jié)點時，總是先判斷該結(jié)點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。否則，進入該子樹，繼續(xù)按深度優(yōu)先的策略進行搜索?；厮莘ㄔ谟脕砬髥栴}的所有解時，要回溯到根，且根結(jié)點的所有子樹都已被搜索遍才結(jié)束 2。而回溯法在用來求問題的任一解時，只要搜

4、索到問題的一個解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。 1 需求分析1.1問題的提出 在求解一些問題（如走迷宮、地圖著色等問題）時，題目的要求可能是求出原問題的一種或所有可能的解決方案。這類問題的解往往是由一個一個的步驟或狀態(tài)所構(gòu)成的，每一步驟又有若干種可能的決策方案；由于沒有固定、明確的數(shù)學解析方法，往往要采用搜索的做法，即從某一個初始狀態(tài)出發(fā)，不斷地向前（即下一個狀態(tài)）搜索，以期最終達到目標狀態(tài)，從而得到原問題的一個解或所有的解。在搜索的過程中，由于問題本身及所采取的搜索方法的特點（如在缺乏全局及足夠的前瞻信息的情況下進行搜索等

5、）3，會導致走到某一狀態(tài)就走不下去的情況，這時，就必須回頭（即回到上一步，而不是回到最初的狀態(tài)），再嘗試其 他的可能性，換一個方向或方法再試試。這樣，不斷地向前探索、回溯，再向前、再回溯，直至最終得出問題的解，或者一路回溯到出發(fā)點（出現(xiàn)這種情況即表示原問題無解）4 。注意，這種搜索過程并不是嘗試搜索問題解空間中所有的可能狀態(tài)和路徑，而是采用深度優(yōu)先的方式，沿著一條路徑，盡可能深入地向前探索。1.2問題的描述1設計內(nèi)容：給出內(nèi)存分類法的多種應用，給出這些應用對應的算法并編程實現(xiàn)。2設計要求：(1)給出各種分類法的求解算法;(2)編程實現(xiàn)各種分類法的算法;(3)對所寫的每個算法給出時空復雜性分析。

6、1.3算法的描述 該算法講的就是用回溯法求解一個無向圖中是否存在哈密爾頓回路的問題。所謂哈密爾頓回路就是指經(jīng)過圖（有向圖或無向圖）中所有頂點一次且僅一次的通路。用回溯法解哈密爾頓回路問題首先要畫出問題的解空間樹，該解空間樹是一棵最大度是 n 的樹（其中 n 為圖中的頂點數(shù)），樹中只有第一個結(jié)點的度是 n，其余結(jié)點的度都為 n-1（該結(jié)點不用與其自身相連）。在編寫算法時可以通過判斷該邊在圖的鄰接矩陣中的值來剪枝，如果其值不是 1 則說明該邊不存在則剪枝不用搜索。由于在求圖的哈密爾頓回路時走過的頂點不能再重復走，所以要對已經(jīng)遍歷過的頂點做一個標記，如果在搜索時找到的是一個帶有標記的頂點，那么該路徑

7、也是不可行的，應剪去。2 概要設計此算法設計為用回溯法求解一般哈密爾頓回路問題，設計的主要內(nèi)容為：給出內(nèi)存分類法的多種應用，給出各類分類法的求解算法，編程實現(xiàn)各種分類法的算法，對所寫的每一個算法給出時間空間復雜性分析。2.1系統(tǒng)運行環(huán)境根據(jù)目前市場上能夠提供的硬件。我們設計系統(tǒng)的硬件環(huán)境如下：l IBM PC286及以上檔次微機、便攜機、各種品牌兼容機，最佳檔次為386以上微機。l 512M或512M以上內(nèi)存，最好具備擴展內(nèi)存l EGA、VGA、TVGA、所有SUPERVGA彩色顯示器。l 20M以上硬盤。l 任何光電鼠或機械鼠。軟件環(huán)境如下：l MS（PC）DOS3.3或以上版本；l 采用V

8、C+進行開發(fā)；2.2算法的實現(xiàn)1.個體類class Cind public:int& operator ( int index ) return dataindex; Cind & Cind:operator = (Cind &a);bool operator = (Cind &ind);void CrossWith(Cind &a);void Mut();void show();void SetArc();double fun();Cind();virtual Cind();int * data;static int n;double fitness;

9、/ ind.cpp: implementation of the Cind class./#include "stdafx.h"#include "GrWndapp.h"#include "shapelist.h"#include "ind.h"#include "node.h"#include "arc.h"#include "math.h"#ifdef _DEBUG#undef THIS_FILEstatic char THIS_FILE=_FILE_

10、;#define new DEBUG_NEW#endifint Cind:n;extern CShapeList node_list,arc_list;/ Construction/DestructionCind:Cind()data = new intn;bool * flag = new booln;for ( int i=0; i<n; i+ )flag= true;int k=0;for ( int m=n; m>0; m- )int t = rand()%m;int j = 0;for ( i = 0; i<n; i+ )if ( flag )if ( j = t

11、)datak+ = i;flag =false;break;j+;delete flag;Cind:Cind()delete data;double Cind:fun()double v = 0;CNode * pn1,*pn2;for ( int i=0; i<n-1; i+ )pn1 = (CNode *)node_list.GetShape(data);pn2 = (CNode *)node_list.GetShape(datai+1);v += sqrt(pn1->x - pn2->x)*(pn1->x - pn2->x)+(pn1->y-pn2-&

12、gt;y)*(pn1->y-pn2->y);pn1 = (CNode *)node_list.GetShape(data0);v += sqrt(pn1->x - pn2->x)*(pn1->x - pn2->x)+(pn1->y-pn2->y)*(pn1->y-pn2->y);return v;void Cind:SetArc()arc_list.Clear();CArc * parc;for ( int i=0; i<n-1; i+ )parc = new CArc(CNode *)node_list.GetShape(da

13、ta),(CNode *)node_list.GetShape(datai+1);arc_list.Add(parc);parc = new CArc(CNode *)node_list.GetShape(data),(CNode *)node_list.GetShape(data0);arc_list.Add(parc);void Cind:show()TRACE("The ind:n");for ( int i=0; i<n; i+ )TRACE ( "%d->",data );TRACE("n");void Cind

14、:Mut()int p1 = rand() % n;int p2 = rand() % n;int t = datap1;datap1=datap2;datap2=t;void Cind:CrossWith(Cind &a)int pos = rand() % (n-1);pos +;int * t1, * t2;t1 = new intn;t2 = new intn;int k=0;for ( int i=0; i<n; i+ )for ( int j=0; j<pos; j+ )if ( data = aj )break;if ( j = pos ) / find no

15、net1k+ = data;for ( i=0; i<pos; i+ )t1k+ = a;k=0;for ( i=0; i<n; i+ )for ( int j=0; j<pos; j+ )if ( dataj = a )break;if ( j = pos ) / find nonet2k+ = a;for ( i=0; i<pos; i+ )t2k+ = data;for ( i=0; i<n; i+ )data = t1;a = t2;delete t1;delete t2;Cind & Cind:operator =(Cind &a)if

16、( this = &a )return * this;for ( int i=0; i<n; i+ )data=a;fitness=a.fitness;return * this;bool Cind:operator =(Cind &ind)for ( int i=0; i<n; i+ )if ( data != ind )return false;return true;2.群體類#include "ind.h"class CGroup public:void Reserve();void Grow();Cind * GetBest();voi

17、d Select();void CalFitness();CGroup();virtual CGroup();int n,m,ml;Cind * group;Cind * pool;int nres;static int gn; / group lengthstatic double miu;static double gg; / gerneration gapstatic double pmut; / probability of mutantstatic double pres; ;/ Group.cpp: implementation of the CGroup class./#incl

18、ude "stdafx.h"#include "GrWndapp.h"#include "Group.h"#include "shapelist.h"#ifdef _DEBUG#undef THIS_FILEstatic char THIS_FILE=_FILE_;#define new DEBUG_NEW#endifextern CShapeList node_list,arc_list;int CGroup:gn;double CGroup:gg;double CGroup:miu;double CGroup:

19、pres;double CGroup:pmut;/ Construction/Destruction/CGroup:CGroup()gn=100; / group lengthpmut=0.3;pres = 0.1;srand( (unsigned)time( NULL ) );Cind:n = node_list.n;group = new Cindgn;pool = new Cindgn;nres = gn*pres;CGroup:CGroup()delete group;delete pool;void CGroup:CalFitness()double maxfst=0;for ( i

20、nt i=0; i<gn; i+ )group.fitness=group.fun();maxfst=_max(maxfst,group.fitness);for ( i=0; i<gn; i+ )group.fitness=maxfst-group.fitness;void CGroup:Select()CalFitness();/ calculate the sum of fitness of the individuldouble sum=0;for ( int i=0; i<gn; i+ )sum += group.fitness;/ create a positio

21、nfor ( i=0; i<gn-nres; i+ )double pos = rand()*sum/RAND_MAX;double t=group0.fitness;for ( int j=0; j<gn; j+ ) / find the indvidulif ( pos <= t )pool=groupj;break;elset += groupj+1.fitness;Cind * CGroup:GetBest()double v=group0.fun();Cind * pind = &group0;for ( int i=1; i<gn; i+ )if (

22、 group.fun() < v )pind = &group;v = group.fun();return pind; void CGroup:Grow()Select();Reserve();/ cross over-for ( int i=0; i<gn-nres; i+=2 )pool.CrossWith(pooli+1);group=pool;groupi+1=pooli+1;/ mutant-int num = gn * pmut; / 要變異的個體數(shù)for ( i=0; i<num; i+ )int ind = rand()%gn; / random s

23、electgroupind.Mut();void CGroup:Reserve()Cind t;for ( int i=0; i<nres; i+ )for ( int j=0; j<gn-1; j+ )if ( groupj.fitness > groupj+1.fitness )t=groupj;groupj=groupj+1;groupj+1=t;2.3接口設計1.外部接口(1) 用戶界面采用圖形用戶界面（GUI），包含菜單、按鈕、對話框等元素。(2) 軟件接口軟件運行于windows XP極其以上版本之上。(3) 硬件接口運行于IBM PC386及兼容機以上。2.4出

24、錯處理設計1.系統(tǒng)應具有相當健壯性，避免或降低由系統(tǒng)錯誤所造成的損壞。2.對關(guān)鍵性操作。2.5維護設計系統(tǒng)嚴格按照設計規(guī)范進行設計，并保持各階段文檔的完整性，為以后對軟件的維護打好基礎。3 詳細設計在以上工作的基礎上，我們根據(jù)任務要求編程實現(xiàn)用回溯法求解一般哈密爾頓回路問題。對有輸出要求的全部數(shù)據(jù)進行分析，進一步研究整個算法的實現(xiàn)。 3.1算法的分析各函數(shù)功能簡要分析：函數(shù) FirstAdjVex（）用來求出圖的鄰接矩陣的某一行存在的第一條邊所對應的第一個頂點；函數(shù) NextAdjVex（）用來求出跟第一個頂點在解空間樹中同行相鄰的下一個頂點；函數(shù) initStatus（）初始化跟蹤棧，把所有

25、已經(jīng)遍歷過的并且當前已經(jīng)符合條件的點都放在這里面；函數(shù) backtrack（）進行回溯；函數(shù) bool testHami（）判斷一下該圖有沒有哈密頓通路；函數(shù) Hami（）是該算法的入口點，它通過調(diào)用函數(shù) backtrack（） 來實現(xiàn)層層遞歸。根據(jù)程序中判斷哈密爾頓回路的條件對每一個節(jié)點訪問一次且僅僅一次即visitTag0.N都等于 1，對 Hami(G)函數(shù)的簡要分析： 1判斷是不是連通圖 2對每一個節(jié)點進行以下操作 (1) 初始化訪問標志 visitTag (2) 調(diào)用試探每一個節(jié)點出發(fā)能不能找到哈密頓通路 ，如果能立即輸出并跳出程序 3到這的時候說明不存在哈密爾頓回路3.2程序的思路

26、創(chuàng)建一個N節(jié)點的連通圖輸入頂點N的值輸入連通圖的邊數(shù)創(chuàng)建每一條邊，構(gòu)成完整連通圖求出哈密爾頓回路的所有解3.3程序的實現(xiàn) #include<stdio.h>#include<process.h>#include<math.h>/全局變量聲明int m=1; /用于標志哈密爾頓回路的總個數(shù)int n; /int x128;int graph128128;void nextvalue(int k)int j;while(1)xk=(int)fmod(xk+1,n+1);if(xk=0) return;if(graphxk-1xk)for(j=1;j<=k-

27、1;j+)if(xj=xk) break;if(j=k)if(k<n|(k=n&&graphxn1)return;void print(int x,int n)int i=1;printf("回路%d:",m);for(;i<=n;i+)printf("%d ",xi);printf("n");m+;void hamiltonian(int k)while(1)nextvalue(k);if(xk=0) return;if(k=n)print(x,n);elsehamiltonian(k+1);void m

28、ain()int i,j,e,a,b;printf("*哈密頓回路遞歸回溯算法*n");printf("*n");printf("請先創(chuàng)建一個n結(jié)點的連通圖graphnnn");printf("請輸入頂點n的值:");scanf("%d",&n);printf("圖中一共有幾條邊？請輸入以便我們創(chuàng)建圖:");scanf("%d",&e);for(i=1;i<=n;i+)for(j=1;j<=n;j+)graphij=0;for(

29、i=1;i<=e;i+)printf("n創(chuàng)建第%d條邊:n",i);printf("構(gòu)成此邊的一個頂點號(1%d):",n);scanf("%d",&a);printf("另一個頂點號(1%d):",n);scanf("%d",&b);graphab=graphba=1;x1=1;for(i=2;i<=n;i+)xi=0;printf("n以下為所求hamiltonian回路的所有解n");hamiltonian(2);3.4設計環(huán)境 操作系統(tǒng)：

30、Windows XP 設計工具：Microsoft Visual C+4 調(diào)試分析4.1有哈密爾頓回路連通圖 1432564.2無哈密爾頓回路連通圖 123545 總結(jié)通過本次課程設計，本人對算法設計與分析基礎有了更深的認識，基本掌握了回溯法求解一般哈密爾頓回路的算法思路以及編程原理，提高了程序開發(fā)的能力，讓能切實體會到算法在編程過程中的指導作用。通過課程設計，學會了按課程設計的任務要求完成各項程序的開發(fā)，對提高自身編程能力和項目管理能力有重要的現(xiàn)實意義。在本次課程設計中，由于對回溯法以及哈密爾頓回路的不熟悉，走了很多彎路，花了一些時間去了解其相關(guān)知識。但是最后終于完成了自己的課程設計，自己覺

31、得還是比較有成就感的。與此同時，我也發(fā)現(xiàn)用回溯法求解一般哈密爾頓回路問題是一個 np 問題，其時間復雜度是 O（n ），空間復雜度是 O（2 ）。通過這次的課程設計，我學到了很多東西：1 多和別人交流，畢竟一個人所能想到的東西是有限的，但是通過和別人的交流，我發(fā)現(xiàn)我可以看到更多的東西了，例如：可能在程序的實現(xiàn)過程中，我并沒有注意到程序在運行過程中會產(chǎn)生異常，但是在和別人的交流過程中，我發(fā)現(xiàn)了這個異常，促使我去捕獲它，使所開發(fā)的系統(tǒng)有了更好的健壯性。2 一個程序的開發(fā)，需要開發(fā)人員用心去完成每一個階段的工作，這樣才不會出現(xiàn)開發(fā)到一半又忽然發(fā)現(xiàn)在某個地方出現(xiàn)了致命的錯誤，需要重新開發(fā)的嚴重錯誤，我

32、想這就好像是在編程的時候需要避免“回溯”是一個道理，前期多做些工作，后期的開發(fā)才會水到渠成，縮短開發(fā)周期。致謝能完成這個課程設計，我首先要感謝我的指導老師譚三老師，在他嚴格的監(jiān)督和細心指導中，使我能夠堅持完成本課程，并能夠較好的實現(xiàn)要求任務書上所要求的功能，最后，我要感謝班上同學對我的幫助和指點。沒有他們的幫助和提供資料對于我一個對編程知識不是很精通的人來說要想在短短的的時間里完成一個算法的設計是幾乎不可能的事情。在此表示最誠摯的感謝！參考文獻1算法設計與分析 宋 文等編 重慶大學出版社，2001。2算法設計與分析 周培德 電子工業(yè)出版社，2000。3算法設計與分析 王曉東 電子工業(yè)出版社，20044 李登信;關(guān)于 Cayley 圖的 Hamilton 性的一個猜想J;渝州大學學報(自然科學版);1999 年 04 期5 百度網(wǎng)站 6 google網(wǎng)站 附錄該算法的具體實現(xiàn)主要代碼如下： int FirstAdjVex(const MGraph& G,int v)/查找 v 的第一個鄰接點 for(int i=0;i<G.vexnum;i+) if(G.arcsvi.adj!=0) return i; return -1; int NextAdjVex(const MGraph& G,int v,int w)/查找 v 的（相對于 w 的