TSP問題的解決與實現(xiàn)講解

1、1 .問題描述所謂TSP問題是指旅行家要旅行n個城市，要求各個城市經(jīng)歷且僅經(jīng)歷一次，并且要求 所走的路程最短。該問題又稱為貨郎擔(dān)問題、郵遞員問題、售貨員問題，是圖問題中最廣為 人知的問題。2 .基本要求（1）上網(wǎng)查找TSP問題的應(yīng)用實例；（2）分析求TSP問題的全局最優(yōu)解的時間復(fù)雜度；（3）設(shè)計一個求近似解的算法；（4）分析算法的時間復(fù)雜度。3 .提交報告課程設(shè)計報告提交內(nèi)容包括：（1）問題描述；（2）需求分析；（3）概要設(shè)計；（4）詳細(xì)設(shè)計；（5）調(diào)試分析；（6）使用說 明；（7）測試結(jié)果；（8）附錄（帶注釋的源程序）。參見“數(shù)據(jù)結(jié)構(gòu)課程設(shè)計概述.pdf”和“數(shù)據(jù)結(jié)構(gòu)課程設(shè)計示例.pdf”。

2、指導(dǎo)教師（簽字）：系主任（簽字）：批準(zhǔn)日期：2014年 月 日1 .問題描述（1）題目要求旅行家要旅行n個城市，要求各個城市經(jīng)歷且僅經(jīng)歷一次，最終要回到出發(fā)的城市，求 出最短路徑。用圖論的術(shù)語來說，假如有一個圖 G=（V,E）,其中V是頂點集，E是邊集，設(shè)D=（dj）是由 頂點i和頂點j之間的距離所組成的距離矩陣。TSP問題就是求出一條通過每個頂點且每個頂 點只通過一次的具有最短距離的回路。(2)基本要求a.上網(wǎng)查找TSP問題的應(yīng)用實例；b.分析求TSP問題的全局最優(yōu)解的時間復(fù)雜度;c.設(shè)計一個求近似解的算法；d.分析算法的時間復(fù)雜度。(3)測試數(shù)據(jù)5個城市的TSP問題:路程矩陣如圖所示:注：

3、由于矩陣所表示的是兩個城市之間的距離，所以該矩陣為對稱矩陣OO2541322825OO1831264118OO7132317OO112826111OO0213420134最短路徑為V0V1V4V2V32 .需求分析(1)本程序用于求解n個結(jié)點的最短哈密爾頓回路問題。(2)程序運行后顯示提示信息 一Please insert the number of cities: "，例如用戶輸入5,則表示結(jié) 點n的值為 5;接下來程序輸出提示信息 “Please insert the distance between one city and another:"，例如用戶輸入測試數(shù)據(jù)中

4、給出的路程矩陣，表示任意兩個城市之間的距離，比 如第一個城市到第0個城市之間的距離為25。(3)用戶輸入數(shù)據(jù)完畢，程序?qū)⑤敵鲞\算結(jié)果。(4)測試數(shù)據(jù)均為正數(shù)，其中用999來表示兩個城市之間距離為3 .概要設(shè)計為了實現(xiàn)上述程序功能，使用優(yōu)先隊列來維護(hù)結(jié)點表，因此需要圖和隊列兩個抽象數(shù)據(jù)類(1)圖的抽象數(shù)據(jù)類型定義ADT GraphData:具有相同類型的數(shù)據(jù)元素的集合，稱為頂點集。Relation :頂點偶對的有窮集合。Operation :CreateGraph(&G ,V,VR)初始條件：V是圖中頂點集合，VR是圖中頂點偶對集合。操作條件：按照V和VR的定義構(gòu)造圖GoDestroyG

5、raph(&G)初始條件：圖G已經(jīng)存在。操作結(jié)果：銷毀GoLocateVex(G,u)初始條件：圖G已經(jīng)存在，u和G中頂點有相同類型。操作結(jié)果：如果G中存在u,則返回u在G中的位置；否則返回相應(yīng)信息。GetVex(G,v)初始條件：圖G已經(jīng)存在，v是G中某個頂點。操作結(jié)果：返回v的值。PutVex(&G,v,value)初始條件：圖G已經(jīng)存在，v是G中頂點。操作結(jié)果：對v賦值value oFirstAdjvex(G ,v)初始條件：圖G已經(jīng)存在，v是G中頂點。操作結(jié)果：返回v的第一個鄰接頂點。如果v在G中沒有鄰接頂點，則返回相應(yīng)信息。NextAdjvex(G,v,w)初始條件：

6、圖G已經(jīng)存在，v是G中頂點,w是v的鄰接頂點。操作結(jié)果：返回v的下一個鄰接頂點。如果w是v的最后一個鄰接點，則返回相應(yīng)信息InsertVex(&G,v,w)初始條件：圖G已經(jīng)存在，v和w是G中頂點。操作結(jié)果：在G中添加VoDeleteVex(&G,v)初始條件：圖G已經(jīng)存在，v是G中頂點。操作結(jié)果：刪除G中頂點v及其相關(guān)的邊。InsertEdge(&G ,v,w) 初始條件：圖G已經(jīng)存在，v和w是G中頂點。操作結(jié)果：在G中添加v,w ;如果G是無向圖，則還增添w,vDeleteEdge(&G,v,w)初始條件：圖G已經(jīng)存在，v和w是G中頂點。操作結(jié)果：在G中刪除

7、v,w;如果G是無向圖，則還刪除w,v。DFSTraverse(G,v)初始條件：圖G已經(jīng)存在，v是G中頂點。操作結(jié)果：從v起深度訪問GoBFSTraverse(G,v)初始條件：圖G已經(jīng)存在，v是G中頂點。操作結(jié)果：從v起廣度訪問G。ADT Graph(2)隊列的抽象數(shù)據(jù)類型ADT QueueData:具有相同數(shù)據(jù)類型的及先進(jìn)先出特性的數(shù)據(jù)元素集合。Relation :相鄰數(shù)據(jù)元素具有前驅(qū)和后繼的關(guān)系。Operation：InitQueue(&Q)初始條件：無操作結(jié)果：創(chuàng)造一個空隊列Q。DestroyQueue(&Q)初始條件：隊列Q已經(jīng)存在。操作結(jié)果：銷毀Q。ClearQu

8、eue(&Q)初始條件：隊列Q已經(jīng)存在。操作結(jié)果：重置Q為空隊列。QueueLength(Q)初始條件：隊列Q已經(jīng)存在。操作結(jié)果： 返回Q的元素個數(shù)。GetHead(Q, &e)初始條件：隊列Q已經(jīng)存在并且非空。操作結(jié)果：用e返回Q的隊頭元素。EnQueue(&Q,e)初始條件：隊列Q已經(jīng)存在。操作結(jié)果：重置Q為空隊列。DeQueue(&Q, &e)初始條件：隊列Q已經(jīng)存在且非空。操作結(jié)果：刪除Q的隊頭元素，并用e返回其值。ADT Queue三大模塊之間的調(diào)用關(guān)(3)本程序包含三大模塊：主程序模塊，TSP算法模塊，輔函數(shù)模塊 系如下。主函數(shù)模塊TSP算法

9、模塊7輔函數(shù)模塊4 .詳細(xì)設(shè)計Node *xnode;Node *ynode;Node *znode;Node *qbase;ElemType bound;(1)元素類型、結(jié)點類型和指針類型、變量和數(shù)據(jù)結(jié)構(gòu)聲明父親結(jié)點指針兒子結(jié)點指針兒子結(jié)點指針/優(yōu)先隊列首指針當(dāng)前可行解的最優(yōu)值typedef int ElemType;#define MAX_V ALUE_OF_TYPE 999;元素類型代表00城市頂點用數(shù)字0, 1, 2,，n-1編號。在搜索的過程中，各個結(jié)點的數(shù)據(jù)是動態(tài)變 化的，互不相同，發(fā)生回溯時，必須使用結(jié)點中原來的數(shù)據(jù)。因此，每個結(jié)點的數(shù)據(jù)必須是 局部與該結(jié)點的。用如下的數(shù)據(jù)結(jié)構(gòu)來

10、定義結(jié)點中所使用的數(shù)據(jù)：typedef struct NodeElemType c100100;intinit_row100;intinit_col100;intcur_row100;intcur_col100;intad100;intk;ElemType w;struct Node *next;Node;/路程矩陣/路程矩陣的當(dāng)前行映射為原始行/路程矩陣的當(dāng)前列映射為原始列路程矩陣的原始行映射為當(dāng)前行/路程矩陣的原始列映射為當(dāng)前列回路頂點鄰接表當(dāng)前路程矩陣的階結(jié)點的下界隊列鏈指針(2)隊列類型Node *data;數(shù)據(jù)域struct QNode *next;指針域typedef struct

11、 QNodeQNode,*QueuePtr;typedef structQueuePtr front;頭指針，指向鏈隊頭結(jié)點QueuePtr rear;尾指針，指向鏈隊列最后一個結(jié)點LinkQueue;程序中所用到的關(guān)于優(yōu)先隊列基本操作實現(xiàn)的偽碼算法如下:void InitQueue(LinkQueue &Q)/構(gòu)造一個空鏈隊列QQ.front=Q.rear=new QNode;Q.front->next=NULL;/InitQueuevoid EnQueue(LinkQueue &Q,Node *e)插入一個指針e到鏈隊列Q中，成為新的隊尾指針QueuePtr p;p=

12、new QNode;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;/EnQueueNode *DeQueue(LinkQueue &Q)/若鏈隊列Q為空，則返回NULL ;否則返回指向數(shù)據(jù)的指針QNode *p;Node *e;if(Q.front->next=NULL)return NULL;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear=p)Q.rear=Q.front;delete p;return e;/DeQueu

13、e(3)輔助函數(shù)的實現(xiàn)(共7個)ElemType Row_min(Node *node,int row,ElemType &second)計算路程矩陣行的最小值if(node->crow0<node->crow1)temp=node->crow0;second=node->crow1;else temp=node->crow1;second=node->crow0;for(i=2;i<node->k;i+)if(node->crowi<temp)second=temp;temp=node->crowi;)else

14、if(node->crowi<second)second=node->crowi;)return temp;)ElemType Col_min(Node *node,int col,ElemType &second)計算路程矩陣列的最小值if(node->c0col<node->c1col)temp=node->c0col;second=node->c1col;)else temp=node->c1col;second=node->c0col;)for(i=2;i<node->k;i+)if(node->ci

15、col<temp)second=temp;temp=node->cicol;)else if(node->cicol<second)second=node->cicol;)return temp;)ElemType Array_red(Node *node)歸約node所指向的結(jié)點的路程矩陣sum=0;行歸約行歸約常數(shù)行歸約常數(shù)累計列歸約列歸約常數(shù)for(i=0;i<node->k;i+)temp=Row_min(node,i,temp1);for(j=0;j<node->k;j+) node->cij-=temp;sum+=temp

16、;for(j=0;j<node->k;j+)temp=Col_min(node,j,temp1);for(i=0;i<node->k;i+) node->cij-=temp;sum+=temp;return sum;ElemType Edge_sel(Node *node,int &vk,int v1)計算Dkl,選擇搜索分支的邊d=0;ElemType *row_value=new ElemTypenode->k;ElemType *col_value=new ElemTypenode->k;for(i=0;i<node->k;i

17、+)每一行的次小值Row_min(node,i,row_valuei);for(i=0;i<node->k;i+)每一列的次小值Col_min(node,i,col_valuei);for(i=0;i<node->k;i+)for(j=0;j<node->k;j+)if(node->cij=0)temp=row_valuei+col_valuei;if(temp>d)d=temp;vk=i;v1=j;/對路程矩陣所有的0元素值計算相應(yīng)的temp值求最大的temp值于d/保存相應(yīng)的行、列號元素上移元素左移元素上移及左移當(dāng)前行轉(zhuǎn)換為原始行 vk1/原

18、始行vk1置刪除標(biāo)志/vk1之后的原始行，其對應(yīng)的當(dāng)前行號減1當(dāng)前列v1轉(zhuǎn)換為原始列vl1原始列vl1置刪除標(biāo)志/vl1之后的原始列，其對應(yīng)的當(dāng)前列號減1/修改vk及其后的當(dāng)前行的對應(yīng)原始行號修改v1及其后的當(dāng)前列的對應(yīng)原始行號當(dāng)前矩陣的階數(shù)減1當(dāng)前行號轉(zhuǎn)換為原始行號當(dāng)前列號轉(zhuǎn)換為原始列號/登記回路頂點鄰接表delete row_value;delete col_value;return d;)void Del_rowcol(Node *node,int vk,int v1)刪除路程矩陣的第vk行和第v1列的所有元素for(i=vk;i<node->k-1;i+)for(j=0;j

19、<v1;j+)node->cij=node->ci+1j;for(j=v1;j<node->k-1;j+)for(i=0;i<vk;i+)node->cij=node->cij+1;for(i=vk;i<node->k-1;i+)for(j=v1;j<node->k-1;j+)node->cij=node->ci+1j+1;vk1=node->init_rowvk;node->row_curvk1=-1;for(i=vk1+1;i<n;i+)node->row_curi-;vl1=nod

20、e->init_colv1;node->col_curvl1=-1;for(i=vl1+1;i<n;i+)node->col_cur-;for(i=vk;i<node->k;i+)node->init_rowi=node->init_rowi+1;for(i=v1;i<node->k;i+)node->init_coli=node->init_coli+1;node->k-;)void Edge_byp(Node *node,int vk,int vl)登記回路頂點鄰接表，旁路有關(guān)的邊vk=init_rowvk;vl

21、=init_colvl;node->advk=vl;k=node->row_curvl;l=node->col_curvk;if(k>=0)&&(l>=0)node->ckl=MAX_V ALUE_OF_TYPE;Node * Initial(ElemType c,int n)初始化Node *node=new Node;for(i=0;i<n;i+)for(j=0;j<n;j+)node->cij=cij;for(i=0;i<n;i+)node->init_rowi=i;node->init_coli=i

22、;/vl轉(zhuǎn)換為當(dāng)前行號 k/vk轉(zhuǎn)換為當(dāng)前列號l當(dāng)前行、列號均處于當(dāng)前矩陣中旁路相應(yīng)的邊分配結(jié)點緩沖區(qū)復(fù)制路程矩陣的初始數(shù)據(jù)/建立路程矩陣原始行、列號與初始行、列號對應(yīng)的關(guān)系node->row_cur=i;node->col_cur=i;for(i=0;i<n;i+)回路頂點鄰接表初始化為空node->adi=-1;node->k=n;return node;返回結(jié)點指針(4)TSP、可題分支限界算法voidTSP(ElemType c100100,int n,int *ad)初始化隊列初始化父親結(jié)點x結(jié)點歸約路程矩陣/選擇分支方向并計算 Dkl/建立分支結(jié)點z結(jié)

23、點（右兒子結(jié)點）*znode=*xnode;bound=MAX_V ALUE_OF_TYPE;InitQueue(qbase);xnode=Initial(c,n);xnode->w=Array_red(xnode);while(xnode->k!=0)d=Edge_sel(xnode,vk,vl);znode=new Node;/x結(jié)點數(shù)據(jù)復(fù)制給z結(jié)點旁路結(jié)點的邊歸約z結(jié)點路程矩陣計算z結(jié)點的下界若下界小于當(dāng)前可行解最優(yōu)值將z結(jié)點插入優(yōu)先隊列否則，剪去該結(jié)點/建立分支節(jié)點-y結(jié)點（左兒子結(jié)點）/x結(jié)點數(shù)據(jù)復(fù)制到 y結(jié)點登記回路鄰接表，旁路有關(guān)的邊刪除結(jié)點y路程矩B$當(dāng)前vk行vl

24、歹U歸約y結(jié)點路程矩陣計算y結(jié)點的下界/路程矩B$只剩2階若下界小于當(dāng)前可行解最優(yōu)值/y結(jié)點插入優(yōu)先隊列更新當(dāng)前可行解最優(yōu)值A(chǔ)LUE_OF_TYPE;znode->cvkvl=MAX_V Array_red(znode);znode->w=xnode->w+d;if(znode->w<bound)EnQueue(qbase,znode); else delete znode; ynode=new Node; *ynode=*xnode;Edge_byp(ynode,vk,vl); Del_rowcol(ynode,vk,vl); ynode->w=Array

25、_red(xnode); ynode->w+=xnode->w;if(ynode->k=2)if(ynode->c00=0)&&(ynode->c11=0)ynode->adynode->init_row0=ynode->init_col0;ynode->adynode->init_row1=ynode->init_col1; else ynode->adynode->init_row0=ynode->init_col1;ynode->adynode->init_row1=ynode

26、->init_col0;登記最后的兩條邊ynode->k=0; if(ynode->w<bound)EnQueue(qbase,ynode);if(ynode->k=0)釋放隊列節(jié)點緩沖區(qū)bound=ynode->w;else delete ynode;xnode=DeQueue(qbase);w=xnode->w;for(i=0;i<n;i+)adi=xnode->adi;delete xnode;while(qbase.front!=qbase.rear)否則剪去y結(jié)點取優(yōu)先隊列首元素保存最短路線長度保存路線的頂點鄰接表釋放x結(jié)點緩沖區(qū)

27、xnode=DeQueue(qbase);delete xnode;)cout<<"The way is:"for(int m=0;m<n;m+)cout<<adm;cout<<endl;cout<<"The length of the way is:"<<w<<endl;)(5)主函數(shù)的偽碼算法void main()cout<< " Please insert the number of cities:“ ；cin>>n;cout<&l

28、t; " Please insert the distance between one city and another: for(i=0;i<n;i+)for(j=0;j<n;j+)cin>>cij;cout<< " ” ; cout<<endl;TSP(c, n, ad);/main(6)函數(shù)調(diào)用關(guān)系圖main5 .調(diào)試分析(1)使用分支限界法求解的過程中，將動態(tài)地生成很多結(jié)點，用結(jié)點表來存放動態(tài)生成的結(jié) 點信息。因此必須按路程的下界來確定搜索的方向，因此可以用優(yōu)先隊列或堆來維護(hù)結(jié)點表。 在此使用優(yōu)先隊列來維護(hù)結(jié)點表。(2

29、)算法的時間復(fù)雜度分析TSP算法的時間估計如下：a.初始化父親結(jié)點，歸約父親結(jié)點路程矩陣，都需要O(n2)時間。b. while循環(huán)體的執(zhí)行次數(shù)取決于所搜索的結(jié)點個數(shù)，假定所搜索的借點數(shù)為c。在while循環(huán)內(nèi)部，選擇分支方向需要 O(n2)時間。c.把x結(jié)點數(shù)據(jù)復(fù)制到z結(jié)點(這里包括整個路程矩陣的復(fù)制工作)，歸約z結(jié)點的路 程矩陣，都需要O(n2)時間。d.把z結(jié)點插入到優(yōu)先隊列，在最壞的情況下需要 0(c)時間。e.把x結(jié)點復(fù)制到y(tǒng)結(jié)點，同樣需要O(n2)時間。f.登記回路鄰接表，旁路有關(guān)的邊，只需 O(1)時間。g.刪除y結(jié)點路程矩陣當(dāng)前vk行vl歹I，歸約y結(jié)點的路程矩陣，這些操作都需

30、要O(n2) 時間。h.把y結(jié)點插入隊列，刪除隊列首元素，都需要O(c)時間。i.其余的花費為O(1)時間。j.因此，整個while循環(huán)在最壞的情況下需要 O(cn2)時間。k.最后，在算法白尾部，for循環(huán)保存路線的頂點鄰接表于數(shù)組 ad中作為算法的返回值， 需要O(n)時間。l.釋放隊列緩沖區(qū)的while循環(huán)在最壞情況下需要O(c)時間。所以，整個算法的時間復(fù)雜度為 O(cn2)(3)算法的空間復(fù)雜度分析算法所需要的空間，主要花費在結(jié)點的存儲空間。每個結(jié)點需要O(n2)空間存放路程矩陣， 而存放路程矩陣的原始行、列號和當(dāng)前行、列號的對應(yīng)關(guān)系的映射表，以及回路的頂點鄰接 表僅需要O(n)空間

31、。因此，每個結(jié)點相應(yīng)需要 O(n2)空間。所以，算法的空間復(fù)雜度為O(cn2)空間。6 .使用說明程序運行后用戶根據(jù)提示輸入城市的數(shù)目n,城市彼此之間的距離(存放在 cnn數(shù)組中)。程序?qū)⒋?lián)起所有城市并回到最初起點的最短回路以及整個路線的長度輸出出來。7 .測試結(jié)果(1)輸入數(shù)據(jù)：5, 999, 25, 41, 32, 28, 25, 999, 18, 31, 26, 41 , 18, 999, 7, 1, 32, 31,7, 999, 11, 28, 26, 1 ,11, 999 (999代表輸出結(jié)果:nnX(2)輸入數(shù)據(jù)：5, 1 , 1, 1, 1, 1, 1, 1, 1, 1, 1,

32、 1 , 1 , 1 , 1, 1, 1 , 1 , 1 , 1, 1 , 1 , 1 , 1 ,1 , 1輸出結(jié)果：(3)輸入數(shù)據(jù)：3, 1 , 1 , 1 , 1, 1, 1, 1, 1, 1輸出結(jié)果：999;代表8用此數(shù)據(jù)結(jié)構(gòu)來定義結(jié)點中所使用的數(shù)據(jù)/路程矩陣/路程矩陣的當(dāng)前行映射為原始行/路程矩陣的當(dāng)前列映射為原始列路程矩陣的原始行映射為當(dāng)前行/路程矩陣的原始列映射為當(dāng)前列回路頂點鄰接表當(dāng)前路程矩陣的階結(jié)點的下界8.附錄（帶注釋的源程序）(1)文件 others.h#include<iostream>using namespace std;typedef int ElemT

33、ype;#define MAX_V ALUE_OF_TYPEtypedef struct Node_dataElemType c100100;intinit_row100;intinit_col100;int row_cur100;intcol_cur100;int ad100;intk;ElemType w;struct Node_data *next;隊列鏈指針Node;typedef struct QNodeNode *data;/ 數(shù)據(jù)域struct QNode *next;指針域QNode,*QueuePtr;typedef structQueuePtr front;頭指針，指向鏈隊

34、頭結(jié)點QueuePtr rear;尾指針，指向鏈隊列最后一個結(jié)點LinkQueue;void InitQueue(LinkQueue &Q)/構(gòu)造一個空鏈隊列 QQ.front=Q.rear=new QNode;Q.front->next=NULL;/InitQueuevoid EnQueue(LinkQueue &Q,Node *e)插入一個指針e到鏈隊列Q中，成為新的隊尾指針QueuePtr p;p=new QNode;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;/EnQueueNode *DeQue

35、ue(LinkQueue &Q)/若鏈隊列Q為空，則返回NULL ;否則返回指向數(shù)據(jù)的指針QNode *p;Node *e;if(Q.front->next=NULL)return NULL;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear=p)Q.rear=Q.front;delete p;return e;/DeQueueElemType Row_min(Node *node,int row,ElemType &second)計算路程矩陣行的最小值ElemType temp;in

36、t i;if(node->crow0<node->crow1)temp=node->crow0;second=node->crow1;else temp=node->crow1;second=node->crow0;for(i=2;i<node->k;i+)if(node->crowi<temp)second=temp;temp=node->crowi;else if(node->crowi<second)second=node->crowi;return temp;ElemType Col_min(No

37、de *node,int col,ElemType &second)計算路程矩陣列的最小值ElemType temp;int i;if(node->c0col<node->c1col)temp=node->c0col;second=node->c1col;else temp=node->c1col;second=node->c0col;)for(i=2;i<node->k;i+)if(node->cicol<temp)second=temp;temp=node->cicol;)else if(node->ci

38、col<second) second=node->cicol;)return temp;)ElemType Array_red(Node *node)歸約node所指向的結(jié)點的路程矩陣int i,j;ElemType temp,temp1,sum=0;行歸約行歸約常數(shù)行歸約常數(shù)累計列歸約列歸約常數(shù)for(i=0;i<node->k;i+)temp=Row_min(node,i,temp1);for(j=0;j<node->k;j+) node->cij-=temp;sum+=temp;)for(j=0;j<node->k;j+)temp=C

39、ol_min(node,j,temp1);for(i=0;i<node->k;i+)node->cij-=temp;sum+=temp;)return sum;)ElemType Edge_sel(Node *node,int &vk,int v1)計算Dkl,選擇搜索分支的邊int i,j;ElemType temp,d=0;ElemType *row_value=new ElemTypenode->k;ElemType *col_value=new ElemTypenode->k;for(i=0;i<node->k;i+)Row_min(n

40、ode,i,row_valuei);for(i=0;i<node->k;i+)Col_min(node,i,col_valuei);for(i=0;i<node->k;i+)for(j=0;j<node->k;j+)if(node->cij=0)temp=row_valuei+col_valuei;if(temp>d)d=temp;vk=i;v1=j;delete row_value;delete col_value;return d;void Del_rowcol(Node *node,int vk,int v1)每一行的次小值每一列的次小值/

41、對路程矩陣所有的0元素值計算相應(yīng)的temp值求最大的temp值于d保存相應(yīng)的行、列號刪除路程矩陣的第vk行和第v1列的所有元素int i,j,vk1,vl1;for(i=vk;i<node->k-1;i+)元素上移for(j=0;j<v1;j+)node->cij=node->ci+1j;for(j=v1;j<node->k-1;j+)元素左移for(i=0;i<vk;i+)node->cij=node->cij+1;for(i=vk;i<node->k-1;i+)元素上移及左移for(j=v1;j<node->

42、;k-1;j+)當(dāng)前行號轉(zhuǎn)換為原始行號當(dāng)前列號轉(zhuǎn)換為原始列號登記回路頂點鄰接表/vl轉(zhuǎn)換為當(dāng)前行號 k/vk轉(zhuǎn)換為當(dāng)前列號l當(dāng)前行、列號均處于當(dāng)前矩陣中旁路相應(yīng)的邊node->cij=node->ci+1j+1;vk1=node->init_rowvk;node->row_curvk1=-1;for(i=vk1+1;i<5;i+)node->row_curi-;vl1=node->init_colv1;node->col_curvl1=-1;for(i=vl1+1;i<5;i+)node->col_curi-;for(i=vk;i&l

43、t;node->k;i+)node->init_rowi=node->init_rowi+1;for(i=v1;i<node->k;i+)node->init_coli=node->init_coli+1;node->k-;void Edge_byp(Node *node,int vk,int vl)登記回路頂點鄰接表，旁路有關(guān)的邊int k,l;vk=node->init_rowvk;vl=node->init_colvl;node->advk=vl;k=node->row_curvl;l=node->col_cu

44、rvk;if(k>=0)&&(l>=0)node->ckl=MAX_V ALUE_OF_TYPE;Node * Initial(ElemType c100100,int n)初始化Node *node=new Node; /分配結(jié)點緩沖區(qū)int i,j;for(i=0;i<n;i+)for(j=0;j<n;j+)node->cij=cij;當(dāng)前行轉(zhuǎn)換為原始行 vk1原始行vk1置刪除標(biāo)志/vk1之后的原始行，其對應(yīng)的當(dāng)前行號減當(dāng)前列v1轉(zhuǎn)換為原始列vl1原始列vl1置刪除標(biāo)志/vl1之后的原始列，其對應(yīng)的當(dāng)前列號減1修改vk及其后的當(dāng)前行的對

45、應(yīng)原始行號修改v1及其后的當(dāng)前列的對應(yīng)原始行號當(dāng)前矩陣的階數(shù)減1復(fù)制路程矩陣的初始數(shù)據(jù)for(i=0;i<n;i+)/建立路程矩陣原始行、列號與初始行、列號對應(yīng)的關(guān)系node->init_rowi=i;node->init_coli=i;node->row_curi=i;node->col_curi=i;)for(i=0;i<n;i+)node->adi=-1;node->k=n;return node;)(2)文彳tsp.h#include "others.h回路頂點鄰接表初始化為空返回結(jié)點指針void TSP(ElemType c1

46、00100,int n,int *ad) int i,vk=0,vl=0;ElemType d,w,bound=MAX_V ALUE_OF_TYPE;Node *xnode;Node *ynode;Node *znode;父親結(jié)點指針兒子結(jié)點指針兒子結(jié)點指針LinkQueue qbase;InitQueue(qbase);優(yōu)先隊列首指針初始化隊列ALUE_OF_TYPE;初始化父親結(jié)點x結(jié)點歸約路程矩陣/選擇分支方向并計算 Dkl/建立分支結(jié)點z結(jié)點（右兒子結(jié)點）/x結(jié)點數(shù)據(jù)復(fù)制給z結(jié)點旁路結(jié)點的邊歸約z結(jié)點路程矩陣計算z結(jié)點的下界若下界小于當(dāng)前可行解最優(yōu)值xnode=Initial(c,n);xnode->w=Array_red(xnode);while(xnode->k!=0)d=Edge_sel(xnode,vk,vl);znode=new Node;*znode=*xnode;znod