用回溯法求解一般哈密爾頓回路問題-文庫吧
2024-12-25 18:57 本頁面
【正文】 爾頓回 路的問題。所謂哈密 爾 頓 回路 就是指經(jīng)過圖（有向圖或無向圖）中所有頂點(diǎn)一次且僅一次的通路。 用回溯法解 哈密爾頓回路 問題首先要畫出問題的解空間樹，該解空間樹是一棵最大度是 n 的樹（其中 n 為圖中的頂點(diǎn)數(shù)），樹中只有第一個結(jié)點(diǎn)的度是 n，其余結(jié)點(diǎn)的度都為 n1（該結(jié)點(diǎn)不用與其自身相連）。在編寫算法時可以通過判斷該邊在圖的鄰接矩陣中的值來剪枝，如果其值不是 1 則說明該邊不存在則剪枝不用搜索。由于在求圖的 哈密爾頓回路 時走過的頂點(diǎn)不能再重復(fù)走，所以要對已經(jīng)遍歷過的頂點(diǎn)做一個標(biāo)記，如果在 搜索時找到的是一個帶有標(biāo)記的頂點(diǎn)，那么該路徑也是不可行的，應(yīng)剪去。 4 用回溯法求解一般哈密爾頓回路問題 2 概要設(shè)計 此算法設(shè)計為用回溯法求解一般哈密爾頓回路問題，設(shè)計的主要內(nèi)容為：給出內(nèi)存分類法的多種應(yīng)用，給出各類分類法的求解算法，編程實現(xiàn)各種分類法 的算法，對所寫的每一個算法給出時間空間復(fù)雜性分析。 系統(tǒng)運(yùn)行環(huán)境 根據(jù)目前市場上能夠提供的硬件。我們設(shè)計系統(tǒng)的硬件環(huán)境如下： ? IBM PC286 及以上檔次微機(jī)、便攜機(jī)、各種品牌兼容機(jī)，最佳檔次為 386 以上微機(jī)。 ? 512M或 512M 以上內(nèi)存，最好具備擴(kuò)展內(nèi)存 ? EGA、 VGA、 TVGA、 所有 SUPERVGA 彩色顯示器。 ? 20M 以上硬盤。 ? 任何光電鼠或機(jī)械鼠。 軟件環(huán)境如下： ? MS（ PC） 或以上版本； ? 采用 VC++進(jìn)行開發(fā)； 算法的實現(xiàn) class Cind { public: intamp。 operator []( int index ){ return data[index]。 } Cind amp。 Cind::operator = (Cind amp。a)。 bool operator == (Cind amp。ind)。 void CrossWith(Cind amp。a)。 void Mut()。 void show()。 void SetArc()。 double fun()。 Cind()。 virtual ~Cind()。 int * data。 static int n。 5 用回溯法求解一般哈密爾頓回路問題 double fitness。 }。 // : implementation of the Cind class. // ///////////////////////////////////////////////////////////////// include include include include include include include ifdef _DEBUG undef THIS_FILE static char THIS_FILE[]=__FILE__。 define new DEBUG_NEW endif int Cind::n。 extern CShapeList node_list,arc_list。 // Construction/Destruction Cind::Cind() { data = new int[n]。 bool * flag = new bool[n]。 for ( int i=0。 in。 i++ ) flag= true。 int k=0。 for ( int m=n。 m0。 m ) { int t = rand()%m。 int j = 0。 for ( i = 0。 in。 i++ ) if ( flag ) { if ( j == t ) { data[k++] = i。 flag =false。 break。 6 用回溯法求解一般哈密爾頓回路問題 } j++。 } } delete[] flag。 } Cind::~Cind() { delete[] data。 } double Cind::fun() { double v = 0。 CNode * pn1,*pn2。 for ( int i=0。 in1。 i++ ) { pn1 = (CNode *)(data)。 pn2 = (CNode *)(data[i+1])。 v += sqrt((pn1x pn2x)*(pn1x pn2x)+ (pn1ypn2y)*(pn1ypn2y))。 } pn1 = (CNode *)(data[0])。 v += sqrt((pn1x pn2x)*(pn1x pn2x)+ (pn1ypn2y)*(pn1ypn2y))。 return v。 } void Cind::SetArc() { ()。 CArc * parc。 for ( int i=0。 in1。 i++ ) { parc = new CArc((CNode *)(data), (CNode *)(data[i+1]))。 (parc)。 } 7 用回溯法求解一般哈密爾頓回路問題 parc = new CArc((CNode *)(data), (CNode *)(data[0]))。 (parc)。 } void Cind::show() { TRACE(The ind:\n)。 for ( int i=0。 in。 i++ ) TRACE ( %d,data )。 TRACE(\n)。 } void Cind::Mut() { int p1 = rand() % n。 int p2 = rand() % n。 int t = data[p1]。 data[p1]=data[p2]。 data[p2]=t。 } void Cind::CrossWith(Cind amp。a) { int pos = rand() % (n1)。 pos ++。 int * t1, * t2。 t1 = new int[n]。 t2 = new int[n]。 int k=0。 for ( int i=0。 in。 i++ ) { for ( int j=0。 jpos。 j++ ) {
試題試卷相關(guān)推薦
鄂ICP備17016276號-1