1、0032算法笔记回溯法电路板排列问题和连续邮资问题1、电路板排列问题 问题描述 将n块电路板以最佳排列方式插入带有n个插槽的机箱中。n块电路板的不同排列方式对应于不同的电路板插入方案。设B=1, 2, , n是n块电路板的集合，L=N1, N2, , Nm是连接这n块电路板中若干电路板的m个连接块。Ni是B的一个子集，且Ni中的电路板用同一条导线连接在一起。设x表示n块电路板的一个排列，即在机箱的第i个插槽中插入的电路板编号是xi。x所确定的电路板排列Density (x)密度定义为跨越相邻电路板插槽的最大连线数。 例：如图，设n=8, m=5，给定n块电路板及其m个连接块：B=1, 2, 3
2、, 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难问题，因此不大可能找到解此问题的多项式时间算法。考虑采用回溯法系统的搜索问题解空间的排列树，找出电路板的最
3、佳排列。设用数组B表示输入。Bij的值为1当且仅当电路板i在连接块Nj中。设totalj是连接块Nj中的电路板数。对于电路板的部分排列x1:i，设nowj是x1:i中所包含的Nj中的电路板数。由此可知，连接块Nj的连线跨越插槽i和i+1当且仅当nowj0且nowj！=totalj。用这个条件来计算插槽i和i+1间的连线密度。 算法具体实现如下：cppview plaincopy1./电路板排列问题回溯法求解2.#includestdafx.h3.#include4.#include5.usingnamespacestd;6.7.ifstreamfin(5d11.txt);8.9.classBo
4、ard10.11.friendintArrangement(int*B,intn,intm,intbestx);12.private:13.voidBacktrack(inti,intcd);14.intn,/电路板数15.m,/连接板数16.*x,/当前解17.*bestx,/当前最优解18.bestd,/当前最优密度19.*total,/totalj=连接块j的电路板数20.*now,/nowj=当前解中所含连接块j的电路板数21.*B;/连接块数组22.;23.24.template25.inlinevoidSwap(Type&a,Type&b);26.27.intArrangement
5、(int*B,intn,intm,intbestx);28.29.intmain()30.31.intm=5,n=8;32.intbestx9;33.34./B=1,2,3,4,5,6,7,835./N1=4,5,6,N2=2,3,N3=1,3,N4=3,6,N5=7,836.37.coutm=m,n=nendl;38.coutN1=4,5,6,N2=2,3,N3=1,3,N4=3,6,N5=7,8endl;39.cout二维数组B如下：endl;40.41./构造B42.int*B=newint*n+1;43.for(inti=1;i=n;i+)44.45.Bi=newintm+1;46.4
6、7.48.for(inti=1;i=n;i+)49.50.for(intj=1;jBij;53.coutBij;54.55.coutendl;56.57.58.cout当前最优密度为:Arrangement(B,n,m,bestx)endl;59.cout最优排列为：endl;60.for(inti=1;i=n;i+)61.62.coutbestxi;63.64.coutendl;65.66.for(inti=1;i=n;i+)67.68.deleteBi;69.70.deleteB;71.72.return0;73.74.75.voidBoard:Backtrack(inti,intcd)/
7、回溯法搜索排列树76.77.if(i=n)78.79.for(intj=1;j=n;j+)80.81.bestxj=xj;82.83.bestd=cd;84.85.else86.87.for(intj=i;j=n;j+)88.89./选择xj为下一块电路板90.intld=0;91.for(intk=1;k0&totalk!=nowk)95.96.ld+;97.98.99.100./更新ld101.if(cdld)102.103.ld=cd;104.105.106.if(ldbestd)/搜索子树107.108.Swap(xi,xj);109.Backtrack(i+1,ld);110.Swa
8、p(xi,xj);111.112./恢复状态113.for(intk=1;k=m;k+)114.115.nowk-=Bxjk;116.117.118.119.120.121.122.intArrangement(int*B,intn,intm,intbestx)123.124.BoardX;125.126./初始化X127.X.x=newintn+1;128.X.total=newintm+1;129.X.now=newintm+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
9、和now137.for(inti=1;i=m;i+)138.139.X.totali=0;140.X.nowi=0;141.142.143.144./初始化x为单位排列并计算total145.for(inti=1;i=n;i+)146.147.X.xi=i;148.for(intj=1;j=m;j+)149.150.X.totalj+=Bij;151.152.153.154./回溯搜索155.X.Backtrack(1,0);156.deleteX.x;157.deleteX.total;158.deleteX.now;159.returnX.bestd;160.161.162.templat
10、e163.inlinevoidSwap(Type&a,Type&b)164.165.Typetemp=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、连续邮资问题
11、问题描述 假设国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，在1张信封上可贴出从邮资1开始，增量为1的最大连续邮资区间。例如，当n=5和m=4时，面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70。 问题分析 解向量：用n元组x1:n表示n种不同的邮票面值，并约定它们从小到大排列。x1=1是唯一的选择。 可行性约束函数：已选定x1:i-1，最大连续邮资区间是1:r，接下来xi的可取值范围是xi-1+1:r+1。 计算X1:i的最大连续邮资区间在本算法中被频繁使用到，因此势必要
12、找到一个高效的方法。直接递归的求解复杂度太高，我们不妨尝试计算用不超过m张面值为x1:i的邮票贴出邮资k所需的最少邮票数yk。通过yk可以很快推出r的值。如果yr的值在上述动态规划运算过程中已赋值，则yrmaxint。语句while(yrmaxint) r+可以很快的计算出r值。关键是如何计算数组y，分析过程如下： r表示由x1i能贴出的最大连续区间，现在，要想把第i层的结点往下扩展，有两个问题需要解决：一，哪些数有可能成为下一个的邮票面值，即xi+1的取值范围是什么；二，对于一个确定的xi+1，如何更新r的值让它表示x1i+1能表示的最大连续邮资区间。第一个问题很简单，xi+1的取值要和前面
13、i个数各不相同，最小应该是xi + 1，最大就是r+1，否则r+1没有办法表示。我们现在专注第二个问题。第二个问题自己有两种思路：一，计算出所有使用不超过m张x1i+1中的面值能够贴出的邮资，然后从r+1开始逐个检查是否被计算出来。二，从r+1开始，逐个询问它是不是可以用不超过m张x1i+1中的面值贴出来。 两种思路直接计算其计算量都是巨大的，需要借助动态规划的方法。模仿0-1背包问题，假设S(i)表示x1i中不超过m张邮票的贴法的集合，这个集合中的元素数目是巨大的，例如，只使用1张邮票的贴法有C(i+1-1,1)C(i,1)=i种，使用2张邮票的贴法有C(i+2-1,2)=C(i+1,2)=
14、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)中元素的值就是它所表
15、示的贴法贴出来的邮资，于是，可以把S(i)中的元素按照它们的值的相等关系分成k类。第j类表示贴出邮资为j的所有的贴法集合，用T(j)表示，T(j)有可能是空集，例如对于1,2,4,T(7)为空集，T(8)=4,4。此时有：S(i) = T(1) U T(2) U T(3) U U T(k)，U表示两个集合的并。 现在考虑xi+1加入后对当前状态S(i)的影响。假设s是S(i)中的一个元素，即s表示一种合法的贴法，xi+1对s能贴出的邮资的影响就是xi+1的多次重复增加了s能贴出的邮资。xi+1对s的影响就是，如果s中贴的邮票不满m张，那就一直贴xi+1，直到s中有m张邮票，这个过程会产生出很多
16、不同的邮资，它们都应该被加入到S(i+1)中。因为s属于S。 综上分析，考虑如果使用动态规划方法计算数组y的值，状态转移过程：将xi-1加入等价类集S中，将会引起数组x能贴出的邮资范围变大，对S的影响是如果S中的邮票不满m张，那就一直贴xi-1,直到S中有m张邮票，这个过程会产生很多不同的邮资，取能产生最多不同邮资的用邮票最少的那个元素。 例如：如下图所示，设m=4,n=5。当x1=1时，2张1,1可以贴出邮资2。这时，设x2=3。将3往1,1中添加，产生新的邮资贴法：5:3,1,1，8:3,3,1,1。这时，程序需要更新数组y的值。如果新的贴法比y5，y8已有的贴法所用的张数更少，则更新之。
17、 算法具体实现如下：cppview plaincopy1./连续邮资问题回溯法求解2.#includestdafx.h3.#include4.usingnamespacestd;5.6.classStamp7.8.friendintMaxStamp(int,int,int);9.private:10.intBound(inti);11.voidBacktrack(inti,intr);12.intn;/邮票面值数13.intm;/每张信封最多允许贴的邮票数14.intmaxvalue;/当前最优值15.intmaxint;/大整数16.intmaxl;/邮资上界17.int*x;/当前解18.
18、int*y;/贴出各种邮资所需最少邮票数19.int*bestx;/当前最优解20.;21.22.intMaxStamp(intn,intm,intbestx);23.24.intmain()25.26.int*bestx;27.intn=5;28.intm=4;29.cout邮票面值数:nendl;30.cout每张信封最多允许贴的邮票数:mendl;31.32.bestx=newintn+1;33.for(inti=1;i=n;i+)34.35.bestxi=0;36.37.38.cout最大邮资:MaxStamp(n,m,bestx)endl;39.40.cout当前最优解:;41.fo
19、r(inti=1;i=n;i+)42.43.coutbestxi;44.45.coutendl;46.47.return0;48.49.50.voidStamp:Backtrack(inti,intr)51.52./*53.*动态规划方法计算数组y的值。状态转移过程：54.*考虑将xi-1加入等价类集S中，将会引起数组x55.*能贴出的邮资范围变大，对S的影响是如果S中的56.*邮票不满m张，那就一直贴xi-1,直到S中有m张57.*邮票，这个过程会产生很多不同的邮资，取能产生58.*最多不同邮资的用邮票最少的那个元素59.*/60.for(intj=0;j=xi-2*(m-1);j+)61.
20、62.if(yjm)63.64.for(intk=1;k=m-yj;k+)/kxi-1的重复次数65.66.if(yj+kyj+xi-1*k)67.68.yj+xi-1*k=yj+k;69.70.71.72.73.74./如果yr的值在上述动态规划运算过程中已赋值，则yrmaxint75.while(yrn)81.82.if(r-1maxvalue)83.84.maxvalue=r-1;85.for(intj=1;j=n;j+)86.87.bestxj=xj;88.89.90.return;91.92.93.int*z=newintmaxl+1;94.95.for(intk=1;k=maxl;k+)96.97.zk=yk;98.99.100.for(intj=xi-1+1;j=r;j+)101.102.xi=j;103.Backtrack(i+1,r);104.for(intk=1;k=maxl;k+)105.106.yk=zk;107.108.109.deletez;110.111.112.intMaxStamp(intn,intm,intbestx)113.114.StampX;115.intmaxint=32767;
