采用 OpenMP 并行方法,实现用分支界限法解决的旅行售货员问题

  1. #include "StdAfx.h"  
  2. //源代码:  
  3. #include <stdio.h>   
  4. #include <malloc.h>  
  5. #include <stdlib.h>  
  6. #include <time.h>  
  7. #include <omp.h>  
  8.   
  9.   
  10. #define NoEdge 1000  
  11. struct MinHeapNode  
  12. {  
  13.     int lcost; //子树费用的下界  
  14.     int cc; //当前费用  
  15.     int rcost; //x[s:n-1]中顶点最小出边费用和  
  16.     int s; //根节点到当前节点的路径为x[0:s]  
  17.     int *x; //需要进一步搜索的顶点是//x[s+1:n-1]  
  18. struct MinHeapNode *next;  
  19. };  
  20. int n; //图G的顶点数  
  21. int **a; //图G的邻接矩阵  
  22. //int NoEdge; //图G的无边标记  
  23. int cc; //当前费用   
  24. int bestc; //当前最小费用  
  25. MinHeapNode* head = 0; /*堆头*/  
  26. MinHeapNode* lq = 0; /*堆第一个元素*/  
  27. MinHeapNode* fq = 0; /*堆最后一个元素*/  
  28. clock_t start, finish;    
  29. double  duration;    
  30.   
  31.   
  32. int DeleteMin(MinHeapNode*&E)  
  33. {  
  34. MinHeapNode* tmp = NULL;  
  35. tmp = fq;  
  36. // w = fq->weight ;  
  37. E = fq;  
  38. if(E == NULL)  
  39. return 0;  
  40. head->next = fq->next; /*一定不能丢了链表头*/  
  41. fq = fq->next;  
  42. // free(tmp) ;  
  43. return 0;  
  44. }  
  45. int Insert(MinHeapNode* hn)  
  46. {  
  47. if(head->next == NULL)  
  48. {  
  49. head->next = hn; //将元素放入链表中  
  50. fq = lq = head->next; //一定要使元素放到链中  
  51. }  
  52. else  
  53. {  
  54. MinHeapNode *tmp = NULL;  
  55. tmp = fq;  
  56. if(tmp->cc > hn->cc)  
  57. {  
  58. hn->next = tmp;  
  59. head->next = hn;  
  60. fq = head->next; /*链表只有一个元素的情况*/  
  61. }  
  62. else  
  63. {  
  64. for(; tmp != NULL;)  
  65. {  
  66. if(tmp->next != NULL && tmp->cc > hn->cc)  
  67. {  
  68. hn->next = tmp->next;  
  69. tmp->next = hn;  
  70. break;  
  71. }  
  72. tmp = tmp->next;  
  73. }  
  74. }  
  75. if(tmp == NULL)  
  76. {  
  77. lq->next = hn;  
  78. lq = lq->next;  
  79. }  
  80. }  
  81. return 0;  
  82. }  
  83. int BBTSP(int v[])  
  84. {//解旅行售货员问题的优先队列式分支限界法  
  85. /*初始化最优队列的头结点*/  
  86. head = (MinHeapNode*)malloc(sizeof(MinHeapNode));  
  87. head->cc = 0;  
  88. head->x = 0;  
  89. head->lcost = 0;  
  90. head->next = NULL;  
  91. head->rcost = 0;  
  92. head->s = 0;  
  93. int i = 0;  
  94. int numThreads = 0;  
  95. int *MinOut = new int[n + 1]; /*定义定点i的最小出边费用*/  
  96. //计算MinOut[i]=顶点i的最小出边费用  
  97. int MinSum = 0;//最小出边费用总合  
  98.   
  99.   
  100. printf("please input the number of threads : ");  
  101. scanf_s("%d",&numThreads);  
  102.   
  103.   
  104. start = clock();  //开始时间  
  105.   
  106.   
  107. for(i = 1; i <= n; i++)  
  108. {  
  109. int Min = NoEdge; /*定义当前最小值*/  
  110. for(int j = 1; j <= n; j++)  
  111. if(a[i][j] != NoEdge && /*当定点i,j之间存在回路时*/   
  112. (a[i][j] < Min || Min == NoEdge)) /*当顶点i,j之间的距离小于Min*/  
  113. Min = a[i][j]; /*更新当前最小值*/  
  114. if(Min == NoEdge)  
  115. return NoEdge;//无回路  
  116. MinOut[i] = Min; /*顶点i的最小出边费用*/  
  117. MinSum += Min; /*最小出边费用的总和*/  
  118. }  
  119. MinHeapNode *E = 0;  
  120. E = (MinHeapNode*)malloc(sizeof(MinHeapNode));  
  121. E->x = new int[n];  
  122. // E.x=new int[n];  
  123. for(i = 0; i < n; i++)  
  124. E->x[i] = i + 1;  
  125. E->s = 0;  
  126. E->cc = 0;  
  127. E->rcost = MinSum;  
  128. E->next = 0; //初始化当前扩展节点  
  129. int bestc = NoEdge; /*记录当前最小值*/  
  130. //搜索排列空间树  
  131. while(E->s < n - 1)  
  132. {//非叶结点  
  133. if(E->s == n - 2)  
  134. {//当前扩展结点是叶结点的父结点  
  135. if(a[E->x[n - 2]][E->x[n - 1]] != NoEdge && /*当前要扩展和叶节点有边存在*/  
  136. a[E->x[n - 1]][1] != NoEdge && /*当前页节点有回路*/  
  137. (E->cc + a[E->x[n - 2]][E->x[n - 1]] + a[E->x[n - 1]][1] < bestc /*该节点相应费用小于最小费用*/  
  138. || bestc == NoEdge))  
  139. {  
  140. bestc = E->cc + a[E->x[n - 2]][E->x[n - 1]] + a[E->x[n - 1]][1]; /*更新当前最新费用*/  
  141. E->cc = bestc;  
  142. E->lcost = bestc;  
  143. E->s++;  
  144. E->next = NULL;  
  145. Insert(E); /*将该页节点插入到优先队列中*/  
  146. }  
  147. else  
  148. free(E->x);//该页节点不满足条件舍弃扩展结点  
  149. }  
  150. else  
  151. {//产生当前扩展结点的儿子结点  
  152.   
  153. omp_set_num_threads(numThreads);  
  154. #pragma omp parallel for  
  155.   
  156.   
  157. for(i = E->s + 1; i < n; i++)  
  158. if(a[E->x[E->s]][E->x[i]] != NoEdge)  
  159. /*当前扩展节点到其他节点有边存在*/  
  160. //可行儿子结点  
  161. int cc = E->cc + a[E->x[E->s]][E->x[i]]; /*加上节点i后当前节点路径*/  
  162. int rcost = E->rcost - MinOut[E->x[E->s]]; /*剩余节点的和*/  
  163. int b = cc + rcost; //下界  
  164. if(b < bestc || bestc == NoEdge)  
  165. {//子树可能含最优解,结点插入最小堆  
  166. MinHeapNode * N;  
  167. N = (MinHeapNode*)malloc(sizeof(MinHeapNode));  
  168. N->x = new int[n];  
  169. for(int j = 0; j < n; j++)  
  170. N->x[j] = E->x[j];  
  171. N->x[E->s + 1] = E->x[i];  
  172. N->x[i] = E->x[E->s + 1];/*添加当前路径*/  
  173. N->cc = cc; /*更新当前路径距离*/  
  174. N->s = E->s + 1; /*更新当前节点*/  
  175. N->lcost = b; /*更新当前下界*/  
  176. N->rcost = rcost;  
  177. N->next = NULL;  
  178. Insert(N); /*将这个可行儿子结点插入到活结点优先队列中*/  
  179. }  
  180. }  
  181. free(E->x);  
  182. }//完成结点扩展  
  183. DeleteMin(E);//取下一扩展结点  
  184. if(E == NULL)  
  185. break//堆已空  
  186. }  
  187. if(bestc == NoEdge)  
  188. return NoEdge;//无回路  
  189. for(i = 0; i < n; i++)  
  190. v[i + 1] = E->x[i];//将最优解复制到v[1:n]  
  191. while(true)  
  192. {//释放最小堆中所有结点  
  193. free(E->x);  
  194. DeleteMin(E);  
  195. if(E == NULL)  
  196. break;  
  197. }  
  198. return bestc;  
  199. }  
  200. int main()  
  201. {  
  202. n = 0;  
  203. int i = 0;  
  204. printf("please input the number of cites : ");  
  205. scanf_s("%d", &n);  
  206. a = (int**)malloc(sizeof(int*) * (n + 1));  
  207. for(i = 1; i <= n; i++)  
  208. {  
  209. a[i] = (int*)malloc(sizeof(int) * (n + 1));  
  210. }  
  211. for(i = 1; i <= n; i++)  
  212. {  
  213. for(int j = 1; j <= n; j++)  
  214. /*scanf("%d", &a[i][j]);*/  
  215. {  
  216. //a[i][j] = (((i + j) * 99) % 14) + 1;  
  217. a[i][j] = i+j;  
  218. if(i == j)a[i][j]=0;  
  219. //printf("%d  ",a[i][j]);  
  220. }  
  221. //printf("\n");  
  222. }  
  223. // prev = (int*)malloc(sizeof(int)*(n+1)) ;  
  224. int*v = (int*)malloc(sizeof(int) * (n + 1));// MaxLoading(w , c , n) ;  
  225. for(i = 1; i <= n; i++)  
  226. {  
  227. v[i] = 0;  
  228. }  
  229.   
  230.   
  231. bestc = BBTSP(v);  
  232. printf("the best path is :");  
  233. for(i = 1; i <= n; i++)  
  234. {  
  235. printf("%d->", v[i]);  
  236. }  
  237. printf("1\nthe shortest cost is ");   
  238. printf("%d\n", bestc);  
  239.   
  240.   
  241.   
  242. finish = clock();    
  243. duration = (double)(finish - start) / CLOCKS_PER_SEC;    
  244.         printf( "the duaration time is :%f seconds\n", duration );    
  245.   
  246.   
  247.   
  248.   
  249.   
  250.   
  251. system("pause");  
  252. return 0;  
  253. }  
有关编译器优化的更完整信息,请参阅优化通知