0032算法笔记回溯法电路板排列问题和连续邮资问题.docx
- 文档编号:10740526
- 上传时间:2023-05-27
- 格式:DOCX
- 页数:18
- 大小:138.73KB
0032算法笔记回溯法电路板排列问题和连续邮资问题.docx
《0032算法笔记回溯法电路板排列问题和连续邮资问题.docx》由会员分享,可在线阅读,更多相关《0032算法笔记回溯法电路板排列问题和连续邮资问题.docx(18页珍藏版)》请在冰点文库上搜索。
0032算法笔记回溯法电路板排列问题和连续邮资问题
1、电路板排列问题
问题描述
将n块电路板以最佳排列方式插入带有n个插槽的机箱中。
n块电路板的不同排列方式对应于不同的电路板插入方案。
设B={1,2,…,n}是n块电路板的集合,L={N1,N2,…,Nm}是连接这n块电路板中若干电路板的m个连接块。
Ni是B的一个子集,且Ni中的电路板用同一条导线连接在一起。
设x表示n块电路板的一个排列,即在机箱的第i个插槽中插入的电路板编号是x[i]。
x所确定的电路板排列Density(x)密度定义为跨越相邻电路板插槽的最大连线数。
例:
如图,设n=8,m=5,给定n块电路板及其m个连接块:
B={1,2,3,4,5,6,7,8},N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8};其中两个可能的排列如图所示,则该电路板排列的密度分别是2,3。
左上图中,跨越插槽2和3,4和5,以及插槽5和6的连线数均为2。
插槽6和7之间无跨越连线。
其余插槽之间只有1条跨越连线。
在设计机箱时,插槽一侧的布线间隙由电路板的排列的密度确定。
因此,电路板排列问题要求对于给定的电路板连接条件(连接块),确定电路板的最佳排列,使其具有最小密度。
问题分析
电路板排列问题是NP难问题,因此不大可能找到解此问题的多项式时间算法。
考虑采用回溯法系统的搜索问题解空间的排列树,找出电路板的最佳排列。
设用数组B表示输入。
B[i][j]的值为1当且仅当电路板i在连接块Nj中。
设total[j]是连接块Nj中的电路板数。
对于电路板的部分排列x[1:
i],设now[j]是x[1:
i]中所包含的Nj中的电路板数。
由此可知,连接块Nj的连线跨越插槽i和i+1当且仅当now[j]>0且now[j]!
=total[j]。
用这个条件来计算插槽i和i+1间的连线密度。
算法具体实现如下:
[cpp] viewplain copy
1.//电路板排列问题 回溯法求解
2.#include "stdafx.h"
3.#include
4.#include
5.using namespace std;
6.
7.ifstream fin("5d11.txt");
8.
9.class Board
10.{
11. friend int Arrangement(int **B, int n, int m, int bestx[]);
12. private:
13. void Backtrack(int i,int cd);
14. int n, //电路板数
15. m, //连接板数
16. *x, //当前解
17. *bestx,//当前最优解
18. bestd, //当前最优密度
19. *total, //total[j]=连接块j的电路板数
20. *now, //now[j]=当前解中所含连接块j的电路板数
21. **B; //连接块数组
22.};
23.
24.template
25.inline void Swap(Type &a, Type &b);
26.
27.int Arrangement(int **B, int n, int m, int bestx[]);
28.
29.int main()
30.{
31. int m = 5,n = 8;
32. int bestx[9];
33.
34. //B={1,2,3,4,5,6,7,8}
35. //N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}
36.
37. cout<<"m="< 38. cout<<"N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}"< 39. cout<<"二维数组B如下: "< 40. 41. //构造B 42. int **B = new int*[n+1]; 43. for(int i=1; i<=n; i++) 44. { 45. B[i] = new int[m+1]; 46. } 47. 48. for(int i=1; i<=n; i++) 49. { 50. for(int j=1; j<=m ;j++) 51. { 52. fin>>B[i][j]; 53. cout< 54. } 55. cout< 56. } 57. 58. cout<<"当前最优密度为: "< 59. cout<<"最优排列为: "< 60. for(int i=1; i<=n; i++) 61. { 62. cout< 63. } 64. cout< 65. 66. for(int i=1; i<=n; i++) 67. { 68. delete[] B[i]; 69. } 70. delete[] B; 71. 72. return 0; 73.} 74. 75.void Board: : Backtrack(int i,int cd)//回溯法搜索排列树 76.{ 77. if(i == n) 78. { 79. for(int j=1; j<=n; j++) 80. { 81. bestx[j] = x[j]; 82. } 83. bestd = cd; 84. } 85. else 86. { 87. for(int j=i; j<=n; j++) 88. { 89. //选择x[j]为下一块电路板 90. int ld = 0; 91. for(int k=1; k<=m; k++) 92. { 93. now[k] += B[x[j]][k]; 94. if(now[k]>0 && total[k]! =now[k]) 95. { 96. ld ++; 97. } 98. } 99. 100. //更新ld 101. if(cd>ld) 102. { 103. ld = cd; 104. } 105. 106. if(ld 107. { 108. Swap(x[i],x[j]); 109. Backtrack(i+1,ld); 110. Swap(x[i],x[j]); 111. 112. //恢复状态 113. for(int k=1; k<=m; k++) 114. { 115. now[k] -= B[x[j]][k]; 116. } 117. } 118. } 119. } 120.} 121. 122.int Arrangement(int **B, int n, int m, int bestx[]) 123.{ 124. Board X; 125. 126. //初始化X 127. X.x = new int[n+1]; 128. X.total = new int[m+1]; 129. X.now = new int[m+1]; 130. X.B = B; 131. X.n = n; 132. X.m = m; 133. X.bestx = bestx; 134. X.bestd = m+1; 135. 136. //初始化total和now 137. for(int i=1; i<=m; i++) 138. { 139. X.total[i] = 0; 140. X.now[i] = 0; 141. } 142. 143. 144. //初始化x为单位排列并计算total 145. for(int i=1; i<=n; i++) 146. { 147. X.x[i] = i; 148. for(int j=1; j<=m; j++) 149. { 150. X.total[j] += B[i][j]; 151. } 152. } 153. 154. //回溯搜索 155. X.Backtrack(1,0); 156. delete []X.x; 157. delete []X.total; 158. delete []X.now; 159. return X.bestd; 160.} 161. 162.template 163.inline void Swap(Type &a, Type &b) 164.{ 165. Type temp=a; 166. a=b; 167. b=temp; 168.} 算法效率 在解空间排列树的每个节点处,算法Backtrack花费O(m)计算时间为每个儿子节点计算密度。 因此计算密度所消耗的总计算时间为O(mn! )。 另外,生成排列树需要O(n! )时间。 每次更新当前最优解至少使bestd减少1,而算法运行结束时bestd>=0。 因此最优解被更新的额次数为O(m)。 更新最优解需要O(mn)时间。 综上,解电路板排列问题的回溯算法Backtrack所需要的计算时间为O(mn! )。 程序运行结果为: 2、连续邮资问题 问题描述 假设国家发行了n种不同面值的邮票,并且规定每张信封上最多只允许贴m张邮票。 连续邮资问题要求对于给定的n和m的值,给出邮票面值的最佳设计,在1张信封上可贴出从邮资1开始,增量为1的最大连续邮资区间。 例如,当n=5和m=4时,面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70。 问题分析 解向量: 用n元组x[1: n]表示n种不同的邮票面值,并约定它们从小到大排列。 x[1]=1是唯一的选择。 可行性约束函数: 已选定x[1: i-1],最大连续邮资区间是[1: r],接下来x[i]的可取值范围是[x[i-1]+1: r+1]。 计算X[1: i]的最大连续邮资区间在本算法中被频繁使用到,因此势必要找到一个高效的方法。 直接递归的求解复杂度太高,我们不妨尝试计算用不超过m张面值为x[1: i]的邮票贴出邮资k所需的最少邮票数y[k]。 通过y[k]可以很快推出r的值。 如果y[r]的值在上述动态规划运算过程中已赋值,则y[r] 语句while(y[r] 关键是如何计算数组y,分析过程如下: r表示由x[1…i]能贴出的最大连续区间,现在,要想把第i层的结点往下扩展,有两个问题需要解决: 一,哪些数有可能成为下一个的邮票面值,即x[i+1]的取值范围是什么;二,对于一个确定的x[i+1],如何更新r的值让它表示x[1…i+1]能表示的最大连续邮资区间。 第一个问题很简单,x[i+1]的取值要和前面i个数各不相同,最小应该是x[i]+1,最大就是r+1,否则r+1没有办法表示。 我们现在专注第二个问题。 第二个问题自己有两种思路: 一,计算出所有使用不超过m张x[1…i+1]中的面值能够贴出的邮资,然后从r+1开始逐个检查是否被计算出来。 二,从r+1开始,逐个询问它是不是可以用不超过m张x[1…i+1]中的面值贴出来。 两种思路直接计算其计算量都是巨大的,需要借助动态规划的方法。 模仿0-1背包问题,假设S(i)表示x[1…i]中不超过m张邮票的贴法的集合,这个集合中的元素数目是巨大的,例如,只使用1张邮票的贴法有C(i+1-1,1)=C(i,1)=i种,使用2张邮票的贴法有C(i+2-1,2)=C(i+1,2)=i*(i+1)/2种,……,使用m张邮票的贴法有C(i+m-1,m)种,其中C(n,r)表示n个元素中取r个元素的组合数。 于是,S(i)中的元素的数目总共有C(i+1-1,1)+C(i+2-1,2)+…+C(i+m-1,m)个。 S(i)中的每个元素就是一种合法的贴法,对应一个邮资。 当前最大连续邮资区间为1到r,那么S(i)中每个元素的邮资是不是也在1到r之间呢? 不一定,比如{1,2,4},当m=2时,它能贴出来8,但不能贴出来7。 总之,在搜索时,一定要保持状态的一致性,即当深度搜索到第i层时,一定要确保用来保存结点状态的变量中保存的一定是第i层的这个结点的状态。 定义S(i)中元素的值就是它所表示的贴法贴出来的邮资,于是,可以把S(i)中的元素按照它们的值的相等关系分成k类。 第j类表示贴出邮资为j的所有的贴法集合,用T(j)表示,T(j)有可能是空集,例如对于{1,2,4},T(7)为空集,T(8)={{4,4}}。 此时有: S(i)=T (1)UT (2)UT(3)U…UT(k),U表示两个集合的并。 现在考虑x[i+1]加入后对当前状态S(i)的影响。 假设s是S(i)中的一个元素,即s表示一种合法的贴法,x[i+1]对s能贴出的邮资的影响就是x[i+1]的多次重复增加了s能贴出的邮资。 x[i+1]对s的影响就是,如果s中贴的邮票不满m张,那就一直贴x[i+1],直到s中有m张邮票,这个过程会产生出很多不同的邮资,它们都应该被加入到S(i+1)中。 因为s属于S。 综上分析,考虑如果使用动态规划方法计算数组y的值,状态转移过程: 将x[i-1]加入等价类集S中,将会引起数组x能贴出的邮资范围变大,对S的影响是如果S中的邮票不满m张,那就一直贴x[i-1],直到S中有m张邮票,这个过程会产生很多不同的邮资,取能产生最多不同邮资的用邮票最少的那个元素。 例如: 如下图所示,设m=4,n=5。 当x[1]=1时,2张{1,1}可以贴出邮资2。 这时,设x[2]=3。 将3往{1,1}中添加,产生新的邮资贴法: 5: {3,1,1},8: {3,3,1,1}。 这时,程序需要更新数组y的值。 如果新的贴法比y[5],y[8]已有的贴法所用的张数更少,则更新之。 算法具体实现如下: [cpp] viewplain copy 1.//连续邮资问题 回溯法求解 2.#include "stdafx.h" 3.#include 4.using namespace std; 5. 6.class Stamp 7.{ 8. friend int MaxStamp(int ,int ,int []); 9. private: 10. int Bound(int i); 11. void Backtrack(int i,int r); 12. int n;//邮票面值数 13. int m;//每张信封最多允许贴的邮票数 14. int maxvalue;//当前最优值 15. int maxint;//大整数 16. int maxl;//邮资上界 17. int *x;//当前解 18. int *y;//贴出各种邮资所需最少邮票数 19. int *bestx;//当前最优解 20.}; 21. 22.int MaxStamp(int n,int m,int bestx[]); 23. 24.int main() 25.{ 26. int *bestx; 27. int n = 5; 28. int m = 4; 29. cout<<"邮票面值数: "< 30. cout<<"每张信封最多允许贴的邮票数: "< 31. 32. bestx=new int[n+1]; 33. for(int i=1;i<=n;i++) 34. { 35. bestx[i]=0; 36. } 37. 38. cout<<"最大邮资: "< 39. 40. cout<<"当前最优解: "; 41. for(int i=1;i<=n;i++) 42. { 43. cout< 44. } 45. cout< 46. 47. return 0; 48.} 49. 50.void Stamp: : Backtrack(int i,int r) 51.{ 52. /* 53. *动态规划方法计算数组y的值。 状态转移过程: 54. *考虑将x[i-1]加入等价类集S中,将会引起数组x 55. *能贴出的邮资范围变大,对S的影响是如果S中的 56. *邮票不满m张,那就一直贴x[i-1],直到S中有m张 57. *邮票,这个过程会产生很多不同的邮资,取能产生 58. *最多不同邮资的用邮票最少的那个元素 59. */ 60. for(int j=0;j<=x[i-2]*(m-1);j++) 61. { 62. if(y[j] 63. { 64. for(int k=1;k<=m-y[j];k++)//k x[i-1]的重复次数 65. { 66. if(y[j]+k 67. { 68. y[j+x[i-1]*k]=y[j]+k; 69. } 70. } 71. } 72. } 73. 74. //如果y[r]的值在上述动态规划运算过程中已赋值,则y[r] 75. while(y[r] 76. { 77. r++; 78. } 79. 80. if(i>n) 81. { 82. if(r-1>maxvalue) 83. { 84. maxvalue=r-1; 85. for(int j=1;j<=n;j++) 86. { 87. bestx[j]=x[j]; 88. } 89. } 90. return; 91. } 92. 93. int *z=new int[maxl+1]; 94. 95. for(int k=1;k<=maxl;k++) 96. { 97. z[k]=y[k]; 98. } 99. 100. for(int j=x[i-1]+1;j<=r;j++) 101. { 102. x[i]=j; 103. Backtrack(i+1,r); 104. for(int k=1;k<=maxl;k++) 105. { 106. y[k]=z[k]; 107. } 108. } 109. delete[] z; 110.} 111. 112.int MaxStamp(int n,int m,int bestx[]) 113.{ 114. Stamp X; 115. int maxint=32767;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 0032 算法 笔记 回溯 电路板 排列 问题 连续 邮资