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