tsp問(wèn)題算法分析-wenkub
2023-04-08 05:06:32 本頁(yè)面
【正文】 tmp = fq。 /*堆頭*/ MinHeapNode* lq = 0。 //圖G的鄰接矩陣 //int NoEdge。 //需要進(jìn)一步搜索的頂點(diǎn)是//x[s+1:n1] struct MinHeapNode *next。 //子樹費(fèi)用的下界 int cc。為什得加1，因?yàn)樽詈蟮米呋爻跏汲鞘校钥偮窂降某鞘袛?shù)為總城市數(shù)+1。通常稱這種算法為A算法。f*(n)函數(shù)值表示從起始s，通過(guò)某一指定的n 到達(dá)目標(biāo)節(jié)點(diǎn)ti的一條最佳路徑的實(shí)際耗散值，并有f*(n)=g*(n)+h*(n)。 A*算法算法思想對(duì)于某一已到達(dá)的現(xiàn)行狀態(tài), 如已到達(dá)圖中的n節(jié)點(diǎn), 它是否可能成為最佳路徑上的一點(diǎn)的估價(jià), 應(yīng)由估價(jià)函數(shù)f(n)值來(lái)決定。在使用分支限界搜索問(wèn)題的解空間樹時(shí)，先根據(jù)限界函數(shù)估算目標(biāo)函數(shù)的界[down, up]，然后從根結(jié)點(diǎn)出發(fā)，擴(kuò)展根結(jié)點(diǎn)的r1個(gè)孩子結(jié)點(diǎn)，從而構(gòu)成分量x1的r1種可能的取值方式。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。TSP問(wèn)題在本實(shí)驗(yàn)中的具體化：從A城市出發(fā)，到達(dá)每個(gè)城市并且一個(gè)城市只允許訪問(wèn)一次，最后又回到原來(lái)的城市，尋找一條最短距離的路徑。2． 算法描述 算法思想分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問(wèn)題的解空間樹。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。對(duì)這r1個(gè)孩子結(jié)點(diǎn)分別估算可能的目標(biāo)函數(shù)bound(x1)，其含義：以該結(jié)點(diǎn)為根的子樹所有可能的取值不大于bound(x1)，即：bound(x1)≥bound(x1,x2)≥…≥ bound(x1,…,xn)若某孩子結(jié)點(diǎn)的目標(biāo)函數(shù)值超出目標(biāo)函數(shù)的下界，則將該孩子結(jié)點(diǎn)丟棄；否則，將該孩子結(jié)點(diǎn)保存在待處理結(jié)點(diǎn)表PT中。假設(shè)g*(n)函數(shù)值表示從起始節(jié)點(diǎn)s 到任意一個(gè)節(jié)點(diǎn)n 的一條最佳路徑上的實(shí)際耗散值。 假設(shè)f 函數(shù)是對(duì)f* 函數(shù)的一種估計(jì), 并有f(n)=g(n)+h(n)，其中g(shù) 函數(shù)是對(duì)g* 的估計(jì)，h 函數(shù)是對(duì)h* 的一種估計(jì)。在A 算法的基礎(chǔ)上，進(jìn)一步限制h(n)函數(shù)，使得搜索圖中的每一個(gè)節(jié)點(diǎn)n，能滿足h(n)=h*(n)、稱h 函數(shù)取h* 的下界。H = 未走的城市數(shù)目前的最小距離；F = G + H 。 //當(dāng)前費(fèi)用 int rcost。 }。 //圖G的無(wú)邊標(biāo)記 int cc。 /*堆第一個(gè)元素*/ MinHeapNode* fq = 0。 // w = fqweight 。 /*一定不能丟了鏈表頭*/ fq = fqnext。 //將元素放入鏈表中 fq = lq = headnext。 headnext = hn。) { if(tmpnext != NULL amp。 break。 } } return 0。 headlcost = 0。 int *MinOut = new int[n + 1]。 i++) { int Min = NoEdge。amp。 //printf(%d\n,MinOut[i])。 E = (MinHeapNode*)malloc(sizeof(MinHeapNode))。 i n。 Ercost = MinSum。如果該葉結(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。 /*當(dāng)前頁(yè)節(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]。 Enext = NULL。由于當(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中的一條邊。 i n。 /
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1