【正文】 用 VC++進行開發(fā)； 算法的實現(xiàn) class Cind { public: intamp。注意，這種搜索過程并不是嘗試搜索問題解空間中所有的可能狀態(tài)和路徑，而是采用深度優(yōu)先的方式，沿著一條路徑，盡可能深入地向前探索。 回溯法 可以用來求出問題的全部解，也可以在求出問題的一個解之后停止對問題 的求解，即只求該問題是否有解。 如果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。 用回溯法解 哈密爾頓回路 問題首先要畫出問題的解空間樹，該解空間樹是一棵最大度是 n 的樹（其中 n 為圖中的頂點數(shù)），樹中只有第一個結(jié)點的度是 n，其余結(jié)點的度都為 n1（該結(jié)點不用與其自身相連）。 void CrossWith(Cind amp。 bool * flag = new bool[n]。 } Cind::~Cind() { delete[] data。 (parc)。 int * t1, * t2。 i++ ) { for ( int j=0。a ) return * this。 CGroup()。 double CGroup::miu。 i++ ) { =()。 j++ ) // find the indvidul if ( pos = t ) { pool=group[j]。 i+=2 ) { (pool[i+1])。 } } 接口設計 (1) 用戶界面 采用圖形用戶界面（ GUI），包含菜單、按鈕、對話框等元素。 if(graph[x[k1]][x[k]]) { for(j=1。 else hamiltonian(k+1)。 for(i=1。 } 19 用回溯法求解一般哈密爾頓回路問題 設計環(huán)境 操作系統(tǒng)： Windows XP 設計工具： Microsoft Visual C++ 20 用回溯法求解一般哈密爾頓回路問題 4 調(diào)試分析 有哈密爾頓回路連通圖 1 4 3 2 5 6 21 用回溯法求解一般哈密爾頓回路問題 22 用回溯法求解一般哈密爾頓回路問題 無哈密爾頓回路連通圖 1 2 3 5 4 23 用回溯法求解一般哈密爾頓回路問題 5 總結(jié) 通過本次課程設計，本人 對算法設計與分析基礎有了更深的認識，基本 掌握 了回溯法 求解一般 哈密 爾頓回路 的算法思路以及編程原理，提高了程序 開發(fā)的能力，讓能切實體會到 算法在編程過程 中的指導作用。i。 } } 27 用回溯法求解一般哈密爾頓回路問題 return 1。//提前結(jié)束 } visitTag[t]=0。 dispMGraph(G)。amp。//初始化跟蹤棧，把所有已經(jīng)遍歷過的并且當前已經(jīng)符合條件的點都放在這里面 } } bool testHami(const MGraphamp。關(guān)于 Cayley 圖的 Hamilton 性的一個猜想 [J]。i=n。i=n。 m++。 int graph[128][128]。 jgn1。 } void CGroup::Grow() { Select()。 i++ ) { double pos = rand()*sum/RAND_MAX。 delete[] pool。 // : implementation of the CGroup class. // ////////////////////////////////////////////////////////////////////// include include include include ifdef _DEBUG undef THIS_FILE static char THIS_FILE[]=__FILE__。 void Grow()。 delete[] t2。 i++ ) t1[k++] = a。 data[p2]=t。 CArc * parc。 flag =false。 // : implementation of the Cind class. // ///////////////////////////////////////////////////////////////// include include include include include include include ifdef _DEBUG undef THIS_FILE static char THIS_FILE[]=__FILE__。 Cind::operator = (Cind amp。 (2)編程實現(xiàn)各種分類法的算法 。本文主要講的就是用回溯法來求解一個任意的圖中是否存在一條哈密頓通路的問題 ， 并用具體的算法來實現(xiàn)它。 關(guān)鍵詞 ： 回溯法 哈密爾頓回路 空間樹 1 用回溯法求解一般哈密爾頓回路問題 引言 回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。 (3)對所寫的每個算法給出時空復雜性分析。a)。 define new DEBUG_NEW endif int Cind::n。 break。 for ( int i=0。 } void Cind::CrossWith(Cind amp。 8 用回溯法求解一般哈密爾頓回路問題 k=0。 } Cind amp。 Cind * GetBest()。 define new DEBUG_NEW endif extern CShapeList node_list,arc_list。 } void CGroup::CalFitness() { double maxfst=0。 double t=group[0].fitness。 Reserve()。 j++ ) if ( group[j].fitness group[j+1].fitness ) { t=group[j]。 void nextvalue(int k) { 創(chuàng)建一個 N節(jié)點的連通圖