tsp問題算法分析-文庫(kù)吧
2025-03-09 05:06 本頁面
【正文】 Node* tmp = NULL。 tmp = fq。 // w = fqweight 。 E = fq。 if(E == NULL) return 0。 headnext = fqnext。 /*一定不能丟了鏈表頭*/ fq = fqnext。 // free(tmp) 。 return 0。 } int Insert(MinHeapNode* hn) { if(headnext == NULL) { headnext = hn。 //將元素放入鏈表中 fq = lq = headnext。 //一定要使元素放到鏈中 }else { MinHeapNode *tmp = NULL。 tmp = fq。 if(tmpcc hncc) { hnnext = tmp。 headnext = hn。 fq = headnext。 /*鏈表只有一個(gè)元素的情況*/ }else { for(。 tmp != NULL。) { if(tmpnext != NULL amp。amp。 tmpcc hncc) { hnnext = tmpnext。 tmpnext = hn。 break。 } tmp = tmpnext。 } } if(tmp == NULL) { lqnext = hn。 lq = lqnext。 } } return 0。 } int BBTSP(int v[]) {//解旅行售貨員問題的優(yōu)先隊(duì)列式分支限界法 /*初始化最優(yōu)隊(duì)列的頭結(jié)點(diǎn)*/ head = (MinHeapNode*)malloc(sizeof(MinHeapNode))。 headcc = 0。 headx = 0。 headlcost = 0。 headnext = NULL。 headrcost = 0。 heads = 0。 int *MinOut = new int[n + 1]。 /*定義定點(diǎn)i的最小出邊費(fèi)用*/ //計(jì)算MinOut[i]=頂點(diǎn)i的最小出邊費(fèi)用 int MinSum = 0。//最小出邊費(fèi)用總合 for(int i = 1。 i = n。 i++) { int Min = NoEdge。 /*定義當(dāng)前最小值*/ for(int j = 1。 j = n。 j++) if(a[i][j] != NoEdge amp。amp。 /*當(dāng)定點(diǎn)i,j之間存在回路時(shí)*/ (a[i][j] Min || Min == NoEdge)) /*當(dāng)頂點(diǎn)i,j之間的距離小于Min*/ Min = a[i][j]。 /*更新當(dāng)前最小值*/ if(Min == NoEdge) return NoEdge。//無回路 MinOut[i] = Min。 //printf(%d\n,MinOut[i])。/*頂點(diǎn)i的最小出邊費(fèi)用*/ MinSum += Min。 // printf(%d\n,MinSum)。 /*最小出邊費(fèi)用的總和*/ } MinHeapNode *E = 0。 E = (MinHeapNode*)malloc(sizeof(MinHeapNode))。 Ex = new
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1