算法笔记回溯法旅行员售货问题和圆排列问题

1、旅行员售货问题 问题描述 某售货员要到若干城市去推销商品，已知各城市之间的路程（旅费），他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（总旅费）最小。 问题分析 旅行售货员问题的解空间是一棵排列树。对于排列树的回溯法与生成1,2,n的所有排列的递归算法Perm类似。开始时x=1,2,n,则相应的排列树有x1:n的所有排列构成。 在递归算法Backtrack中，当i=n时，当前扩展节点是排列树的叶节点的父节点。此时算法检测图G是否存在一条从顶点xn-1到顶点xn的边和一条从顶点xn到顶点1的边。如果这两条边都存在，则找到一条旅行员售货回路。此时，算法还需要判断这条回路的费用是否优于已找到的当前最优回流的费用bestc。如果是，则必须更新当前最优值bestc和当前最优解bestx。 当in时，当前扩展节点位于排列树的第i-1层。图G中存在从顶点xi-1到顶点xi的边时，x1:i构成图G的一条路径，且当x1:i的费用小于当前最优值时算法进入树的第i层，否则将剪去相应的子树。 算法具体代码如下：cppview plaincopy1. /5d9旅行员售货问题回溯法求解2. #includestdafx.h3. #include4. #include5. usingnamespacestd;6. 7. ifstreamfin(5d9.txt);8. constintN=4;/图的顶点数9. 10. template11. classTraveling12. 13. template14. friendTypeTSP(Type*a,intn);15. private:16. voidBacktrack(inti);17. intn,/图G的顶点数18. *x,/当前解19. *bestx;/当前最优解20. Type*a,/图G的领接矩阵21. cc,/当前费用22. bestc;/当前最优值23. intNoEdge;/无边标记24. ;25. 26. template27. inlinevoidSwap(Type&a,Type&b);28. 29. template30. TypeTSP(Type*a,intn);31. 32. intmain()33. 34. cout图的顶点个数n=Nendl;35. 36. int*a=newint*N+1;37. for(inti=0;i=N;i+)38. 39. ai=newintN+1;40. 41. 42. cout图的邻接矩阵为:endl;43. 44. for(inti=1;i=N;i+)45. 46. for(intj=1;jaij;49. coutaij;50. 51. coutendl;52. 53. cout最短回路的长为：TSP(a,N)endl;54. 55. for(inti=0;i=N;i+)56. 57. deleteai;58. 59. deletea;60. 61. a=0;62. return0;63. 64. 65. template66. voidTraveling:Backtrack(inti)67. 68. if(i=n)69. 70. if(axn-1xn!=0&axn1!=0&71. (cc+axn-1xn+axn1bestc|bestc=0)72. 73. for(intj=1;j=n;j+)bestxj=xj;74. bestc=cc+axn-1xn+axn1;75. 76. 77. else78. 79. for(intj=i;j=n;j+)80. 81. /是否可进入xj子树?82. if(axi-1xj!=0&(cc+axi-1xibestc|bestc=0)83. 84. /搜索子树85. Swap(xi,xj);86. cc+=axi-1xi;/当前费用累加87. Backtrack(i+1);/排列向右扩展,排列树向下一层扩展88. cc-=axi-1xi;89. Swap(xi,xj);90. 91. 92. 93. 94. 95. template96. TypeTSP(Type*a,intn)97. 98. TravelingY;99. Y.n=n;100. Y.x=newintn+1;101. Y.bestx=newintn+1;102. 103. for(inti=1;i=n;i+)104. 105. Y.xi=i;106. 107. 108. Y.a=a;109. Y.cc=0;110. Y.bestc=0;111. 112. Y.NoEdge=0;113. Y.Backtrack(2);114. 115. cout最短回路为：endl;116. for(inti=1;i=n;i+)117. 118. coutY.bestxi;119. 120. coutY.bestx1endl;121. 122. deleteY.x;123. Y.x=0;124. deleteY.bestx;125. 126. Y.bestx=0;127. returnY.bestc;128. 129. 130. template131. inlinevoidSwap(Type&a,Type&b)132. 133. Typetemp=a;134. a=b;135. b=temp;136. 算法backtrack在最坏情况下可能需要更新当前最优解O(n-1)!)次，每次更新bestx需计算时间O(n)，从而整个算法的计算时间复杂性为O(n!)。 程序运行结果如图： 2、圆排列问题 问题描述 给定n个大小不等的圆c1,c2,cn，现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如，当n=3，且所给的3个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列如图所示。其最小长度为。 问题分析 圆排列问题的解空间是一棵排列树。按照回溯法搜索排列树的算法框架，设开始时a=r1,r2,rn是所给的n个元的半径，则相应的排列树由a1:n的所有排列构成。 解圆排列问题的回溯算法中，CirclePerm(n,a)返回找到的最小的圆排列长度。初始时，数组a是输入的n个圆的半径，计算结束后返回相应于最优解的圆排列。center计算圆在当前圆排列中的横坐标，由x2 = sqrt(r1+r2)2-(r1-r2)2)推导出x = 2*sqrt(r1*r2)。Compoute计算当前圆排列的长度。变量min记录当前最小圆排列长度。数组r表示当前圆排列。数组x则记录当前圆排列中各圆的圆心横坐标。 在递归算法Backtrack中，当in时，算法搜索至叶节点，得到新的圆排列方案。此时算法调用Compute计算当前圆排列的长度，适时更新当前最优值。 当in时，当前扩展节点位于排列树的i-1层。此时算法选择下一个要排列的圆，并计算相应的下界函数。 算法具体代码如下：cppview plaincopy1. /圆排列问题回溯法求解2. #includestdafx.h3. #include4. #include5. usingnamespacestd;6. 7. floatCirclePerm(intn,float*a);8. 9. template10. inlinevoidSwap(Type&a,Type&b);11. 12. intmain()13. 14. float*a=newfloat4;15. a1=1,a2=1,a3=2;16. cout圆排列中各圆的半径分别为：endl;17. for(inti=1;i4;i+)18. 19. coutai;20. 21. coutendl;22. cout最小圆排列长度为：;23. coutCirclePerm(3,a)endl;24. return0;25. 26. 27. classCircle28. 29. friendfloatCirclePerm(int,float*);30. private:31. floatCenter(intt);/计算当前所选择的圆在当前圆排列中圆心的横坐标32. voidCompute();/计算当前圆排列的长度33. voidBacktrack(intt);34. 35. floatmin,/当前最优值36. *x,/当前圆排列圆心横坐标37. *r;/当前圆排列38. intn;/圆排列中圆的个数39. ;40. 41. /计算当前所选择圆的圆心横坐标42. floatCircle:Center(intt)43. 44. floattemp=0;45. for(intj=1;jtemp)50. 51. temp=valuex;52. 53. 54. returntemp;55. 56. 57. /计算当前圆排列的长度58. voidCircle:Compute(void)59. 60. floatlow=0,high=0;61. for(inti=1;i=n;i+)62. 63. if(xi-rihigh)69. 70. high=xi+ri;71. 72. 73. if(high-lown)82. 83. Compute();84. 85. else86. 87. for(intj=t;j=n;j+)88. 89. Swap(rt,rj);90. floatcenterx=Center(t);91. if(centerx+rt+r1min)/下界约束92. 93. xt=centerx;94. Backtrack(t+1);95. 96. Swap(rt,rj);97. 98. 99. 100. 101. floatCirclePerm(intn,float*a)102. 103. CircleX;104. X.n=n;105. X.r=a;106. X.min=;107. float*x=newfloatn+1;108. X.x=x;109. X.Backtrack(1);110. deletex;111. returnX.min;112. 113. 114. template115. inlinevoidSwap(Type&a,Type&b)116. 117. Typetemp=a;118. a=b;119. b=temp;120. 如果不考虑计算当前圆排列中各圆的圆心横坐标和计算当前圆排列长度所需的计算时间按，则 Backtrac