tsp問題算法分析(編輯修改稿)
2025-04-20 05:06 本頁面
【文章內容簡介】 int[n]。 // =new int[n]。 for(int i = 0。 i n。 i++) Ex[i] = i + 1。 Es = 0。 Ecc = 0。 Ercost = MinSum。 Enext = 0。 //初始化當前擴展節(jié)點 int bestc = NoEdge。 /*記錄當前最小值*/ //搜索排列空間樹 while(Es n 1) {//非葉結點 if(Es == n 2) {//當前擴展結點是葉結點的父結點 /* 首先考慮s=n2的情形，此時當前擴展結點是排列樹中某個葉結點的父結點。如果該葉結點相應一條可行回路 且費用小于當前最小費用，則將該葉結點插入到優(yōu)先隊列中，否則舍去該葉結點 */ if(a[Ex[n 2]][Ex[n 1]] != NoEdge amp。amp。 /*當前要擴展和葉節(jié)點有邊存在*/ a[Ex[n 1]][1] != NoEdge amp。amp。 /*當前頁節(jié)點有回路*/ (Ecc + a[Ex[n 2]][Ex[n 1]] + a[Ex[n 1]][1] bestc /*該節(jié)點相應費用小于最小費用*/ || bestc == NoEdge)) { bestc = Ecc + a[Ex[n 2]][Ex[n 1]] + a[Ex[n 1]][1]。 /*更新當前最新費用*/ Ecc = bestc。 Elcost = bestc。 Es++。 Enext = NULL。 Insert(E)。 /*將該頁節(jié)點插入到優(yōu)先隊列中*/ }else free(Ex)。//該頁節(jié)點不滿足條件舍棄擴展結點 }else {/*產生當前擴展結點的兒子結點 當sn2時，算法依次產生當前擴展結點的所有兒子結點。由于當前擴展結點所相應的路徑是x[0:s]， 其可行兒子結點是從剩余頂點x[s+1:n1]中選取的頂點x[i]，且(x[s]，x[i])是所給有向圖G中的一條邊。 對于當前擴展結點的每一個可行兒子結點，計算出其前綴(x[0:s]，x[i])的費用cc和相應的下界lcost。 當lcostbestc時，將這個可行兒子結點插入到活結點優(yōu)先隊列中。*/ for(int i = Es + 1。 i n。 i++) if(a[Ex[Es]][Ex[i]] != NoEdge) { /*當前擴展節(jié)點到其他節(jié)點有邊存在*/ //可行兒子結點 int cc = Ecc + a[Ex[Es]][Ex[i]]。 /*加上節(jié)點i后當前節(jié)點路徑*/ int rcost = Ercost MinOut[Ex[Es]]。 /*剩余節(jié)點的和*/ int b = cc + rcost。 //下界 if(b bestc || bestc == NoEdge) {//子樹可能含最優(yōu)解,結點插入最小堆 MinHeapNode * N。 N = (MinHeapNode*)malloc(sizeof(MinHeapNode))。 Nx = new int[n]。 for(int j = 0。 j n。 j++) Nx[j]
試題試卷相關推薦
鄂ICP備17016276號-1