计算复杂性之回溯法详解

回回 溯溯 法法回溯法1.概要回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。回溯法摘要：利用分治法的方法穷举搜索，分治法将一个问题分解成几个类似的小规模问题，再将子问题的解合成原问题的解。总纲：1.二进制字符串回溯法 2.K-ary字符串回溯法 3.修剪与删除 4.如何编写回溯法算法应用于：1.背包问题 2.汉密尔顿路径问题 3.旅行推销员问题穷举搜索穷举搜索，顾名思义，就是尝试所求问题的所有可能性。穷举搜索的时间往往很慢，但也有一些关于标准的工具来帮助我们使用：生成基本项目的算法，比如：1.长度为n的二进制字符串共有2n个字符。2.长度为n的k-ary字符串有kn个字符3.n!种排列方式4.在n样事物中选取r件事物，共有n!/r!(n-r)!种组合。回溯法可以通过“优化修剪”的方法加速穷举搜索。回溯基本问题1、位串问题问题：生成含有n个字符的所有字符串。解题思路：使用分治法。用数组A1.n来保存当前的二进制字符串。目的是调用process(A)一次，用数组A1.n保存每个二进制字符串。伪代码：Procedurebinary(m)commentprocessallbinarystringsoflengthmifm=0thenprocess(A)elseAm:=0;binary(m1)Am:=1;binary(m1)正确性证明要求：对任意的m1,binary(m)调用process(A)一次，数组A1.n包含每个有m个字符的字符串。证明：证明关于m使用归纳法。上述要求对于m=0明显成立。现在假设binary(m-1)调用process(A)一次，数组A1.m-1保存每个有m-1个字符的字符串.首先，binary(m)1.将Am值设为0；2.调用binary(m-1)由归纳假设，这会调用process(A)一次，数组A1.m包含每个有m个字符的字符串，以0结束。然后，binary(m)1.将Am值设为1；2.调用binary(m-1).由归纳假设，这会调用process(A)一次，数组A1.m包含每个有m个字符的字符串，以1结束。因此，binary(m)调用process(A)一次，数组A1.n包含每个有m个字符的字符串。分析设T(n)为binary(m)的运行时间.假设程序进程消耗时O(1),则因此，由上式的递推公式推导出此式子，T(n)=(c+d)2n-1d.因而,T(n)=O(2n),这意味着生成字符串的算法是最优的。k-ary字符串问题：生成所有来自0.k-1,n个数字的字符串.解决方案：用数组A1.n来保存当前的k-ary字符串。目的是调用process(A)一次用数组A1.n保存每个k-ary字符串。伪代码：procedurestring(m)commentprocessallk-arystringsoflengthmifm=0thenprocess(A)elseforj:=0tok1doAm:=j;string(m1)正确性证明：与二进制案例相似。分析：与二进制案例相似，算法最优回溯法则回溯通过一个树形结构来寻找解空间。举例来说长度为3的二进制字符串：回溯法会在这树上进行前序遍历，处理叶子。通过修剪法来减少计算时间：跳过没有用的树叶的节点。找到的是错误的则回到父节点k-ary字符串的剪切应用字符串数组填充过程从右到左,string(m,k)可以删除那些对Am而言不容于Am+1,.n的选择。procedurestring(m)commentprocessallk-arystringsoflengthmifm=0thenprocess(A)elseforj:=0tok1doifjisavalidchoiceforAmthenAm:=j;string(m1)创造一个回溯算法创造一个回溯算法的步骤：选择一个基本对象，如：字符串，排列组合(在本轮文中将是字符串)用分而治之代码来生成这些基本对象用这个代码测试其性能关于基本的递归在每一次递归调用前优化代码算法一般形式的生成算法:一般形式的回溯算法:proceduregenerate(m)proceduregenerate(m)ifm=0thenprocess(A)ifm=0thenprocess(A)elseforeachofabunchofelseforeachofabunchnumbersjdoofnumbersjdoAm:=j;generate(m1)ifjconsistentwithAm+1.nthenAm:=j;generate(m1)背包问题TheKnapsackProblem解决方案：给定n个支路，用一个数组A1n如果支路i被用上，则使得Ai=1。遍历A1n来寻找合值。n=3,s1=4,s2=5,s3=2,L=6.算法使用二进制字符串算法。优化剪切：设l为剩余长度，1，Am=0时是合适的；2，Am=1时是不合适的，如果sml；优化剪切程序knapsack(n,L)用长度分别为s1,.,sn的n个枝条输出背包问题的所有解，背包的长度大小为L。procedureknapsack(m,l)commentsolveknapsackproblemwithmrods,knapsacksizelifm=0thenifl=0thenprint(A)elseAm:=0;knapsack(m1,l)ifsmlthenAm:=1;knapsack(m1,lsm)分析：时间为O(2n)广义字符串注意k可以可以与字符串的每个数字不同,比如设数组D1.n，Am取值0.Dm-1.procedurestring(m)commentprocessallstringsoflengthmifm=0thenprocess(A)elseforj:=0toDm1doAm:=j;string(m1)应用：在一个有n个节点的图中，Dm可以是节点m的深度。汉密尔顿循环HamiltonianCycles在一个有向图中的汉密尔顿循环是每一个顶仅经过一次的循环。问题：给定一个有向图G=(V,E),找到一个汉密尔顿循环。用邻接表保存有向图(顶点v1,2,.n，保存一个顶点w的表使得(v,w)E).用A1.n保存一个汉密尔顿循环，循环为AnAn1.A2A1An汉密尔顿循环近邻表AdjacencylistN为neighboursD为degree（近邻个数）汉密尔顿循环:算法使用广义字符串算法。修剪优化：设定一个布尔数组U1.n,如果顶点m未用，Um未用。考虑点m1.Um=ture是合适的2.Um=false是不合适的；优化剪切为了解决汉密尔顿循环问题，为输入图建立数组N(邻接)和D(度)，并执行下列。假设n1.分析汉密尔顿程序花费多长时间找到一个哈密尔顿循环？假设没有找到.设T(n)是hanmilton(v,n)运行时间.假设图形有最大输出度d。因而，存在b,cIN,因此（通过重复替代）,T(n)=O(dn).因此在一个n结点的，无汉密尔顿循环的图中总运行时间是O(dn)。而有一个汉密尔顿循环被找到的运行时间则是O(dn+d)=O(dn).旅行推销员问题优化问题(TSP):给定有向标记图G=（V,E），找到最小代价的汉密尔顿循环（成本是指路径上标记的总和）。有界优化问题(BTSP):给定有向标记图G=（V,E）且BIN,找到一个成本小于B的汉密尔顿循环。解决边界问题是足够的。然后完整的问题可以通过二进制搜索完成。假设我们有一个程序BTSP(x),能够返回一个长度为最大x的汉密尔顿循环，如果循环存在。为了解决优化问题，调用TSP(1,B),其中B是所有边界成本的和(如果存在汉密尔顿循环，消耗最小的那个循环一定比TSP(1,B)少.)functionTSP(l,r)commentreturnmincostHam.cycleofcostrandlifl=rthenreturn(BTSP(l)elsem:=(l+r)/2ifBTSP(m)succeedsthenreturn(TSP(l,m)elsereturn(TSP(m+1,r)(注意，应该首先调用BTSP(B)来确保一个汉密尔顿环存在)程序TSP被称为O(logB)时间(分析与二进制搜索相似)。假设1.图有n个边2.图在最大b上有标记（所以Bbn)3.程序运行时间O(T(n).因而，程序TSP运行时间(logn+logb)T(n).BTSP的回溯设Cv,w是路径(v,w)E的成本,假如(v,w)E,Cv,w=.1.fori:=1ton1doUi:=true2.Un:=false;An:=n3.hamilton(n1,B)procedurehamilton(m,b)commentcompleteHamiltoniancyclefromAm+1withmunusednodes,costb4.ifm=0thenprocess(A,b)else5.forj:=1toDAm+1do6.w:=NAm+1,j7.ifUwandCAm+1,wbthen8.Uw:=false9.Am:=whamilton(m1,bCv,w)10.Uw:=trueprocedureprocess(A,b)commentcheckthatthecycleisclosed11.ifCA1,nbthenprint(A)分析:运行时间O(dn),对于汉密尔顿环1.成本最大的路径的额外修剪是在7行完成。2.程序(行11)通过使用邻接矩阵使得运算更简单。回溯法2摘要：排列回溯应用于：汉密尔顿路径问题和平皇后问题排列问题：生成n个不同数字的所有排列。解决方案：1.经过所有的长度为n的n元字符串，剪除所有的非排列。2.设一个布尔数组U1.n,如果m是未用的,Um是ture。3.用一个数组A1.n来表示当前的排列。4.目的是调用process(a),一旦A1.n包含当前排列。调用程序permute(n):procedurepermute(m)commentprocessallpermsoflengthm1.ifm=0thenprocess(A)else2.forj:=1tondo3.ifUjthen4.Uj:=false5.Am:=j;permute(m1)6.Uj:=true这里和前面的汉密尔顿环问题是一样的。一个汉密尔顿环就是图像节点的一个排列。分析很清楚，算法的运行时间为O(nn).但是这个分析并不紧密:它没有考虑到修剪的问题。第三行执行了多少次？运行的时间将会大于O(nn).当第3行被运行是是什么情形？0in,程序会用排列的一部分填充在A的顶部的i个空位，然后会在第2行的下一个空位尝试n个候选。前i个位置：从n个数中选i个数，没有重复，进行排列。有几种方法填写排列的一部分？因此，第三行被执行的次数是所以，排序所要花费的时间为O(n+1)!),这就比之前的一般算法要优越快速排序之前的排列生成算法不是最优化算法：对于因子n，生成了n!个排列，耗时O(n+1)!).一个更好的算法是：用分而治之算法去创造一个只有有一种排列方式的更快的回溯算法：1.首先对于所有的1in,设定Ai=i,2.用A1.n-1的值,依次从1.n替代An。排序代码procedurepermute(m)commentprocessallpermsinA1.m1.ifm=1thenprocess(A)else2.permute(m1)3.fori:=1tom1do4.swapAmwithAjforsome1j2.要求:对任意n1,T(n)2n!2.证明:对于n进行归纳法证明。对于n=1,要求明显成立，假设题设对于n成立。可有，T(n+1)=(n+1)T(n)+2n(n+1)(2n!2)+2n=2(n+1)!2.因此，排列程序运行时间为O(n!),是最优的。稠密图上的汉密尔顿循环使用邻接矩阵:Mi,j是真，如果(i,j)E.1.fori:=1tondo2.Ai:=i3.hamilton(n1)procedurehamilton(m)commentfindHamiltoniancyclefromAmwithmunusednodes4.ifm=0thenprocess(A)else5.forj:=mdownto1do6.ifMAm+1,Ajthen7.swapAmwithAj8.hamilton(m1)9.swapAmwithAjprocedureprocess(A)commentcheckthatthecycleisclosed10.ifMA1,nthenprint(A)分析因此，汉密尔顿换的运行时间为O(dn)(使用广义字符窜)O(n1)!)(使用排列).两个范围那个更小？取决于d的取值。当dn/e(e=2.7183.)，字符串算法更优。和平皇后问题该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。皇后问题用数组Ai来存储第i列皇后的位置，如图A=42736851发现这形成了一个排序算法procedurequeen(m)1.ifm=0thenprocesselse2.fori:=mdownto1do3.ifOKtoputqueenin(Ai,m)then4.swapAmwithAi5.queen(m1)6.swapAmwithAi如何确定将皇后放到位子(i,j)是否正确？当没有皇后在所放位子的对角线和反对角线上没有皇后。考虑下面的数组：entry(i,j)=i+_j要点：在同一反对角线上的函数值是相同的函数值的范围是2.2n考虑下面的数组：entry(i,j)=i-j要点：在同一对角线上的函数值是相同的函数值的范围是-n+1.n-1设定数组b2.2n和d-n+1.n-1(初始化为真)，使得bi是假的,如果反对角线i是被一个皇后占用的,2i2ndi是假的,如果对角线i是被一个皇后占用的,n+1in1.于前面的程序相比，增加的判定条件bAi+manddAimprocedure queen(m)1.if m=0 then process else2.for i:=m downto 1 do3.if bAi+m and dAi m then4.swap Am with Ai5.bAm+m:=false6.dAm m:=false7.queen(m 1)8.bAm+m:=true9.dAm m:=true10.swap Am with Ai实验结果如何将一个算法付诸实践？理论运行时间：O(n!)应用于BerkeleyUnixPascalonSunSparc2适用于n18通过因子2也许能够减少运行时间（没能实现）改进了原始回溯法（理论上O(nn!)）观察超过一个常数的多元Count为放置皇后的方式有count种时间纵轴用1e+t来表示，可看出随着皇后数量n的增加，运算时间增长很快回溯法3重点：组合回溯组合：从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合，例如OR=1,2,3,4,n=4,r=3则无重组合为：1,2,3;1,2,4;1,3,4;2,3,4.组合问题：n中一次选r生成所有组合。解：用数组A1.r来表示当前组合。调用程序choose(n,r)。procedurechoose(m,q)commentchooseqelementsoutof1.mifq=0thenprocess(A)elsefori:=qtomdoAq:=ichoose(i1,q1)正确性分三个部分进行证明：1.程序只生成组合；2.生成组合的正确的数目;3.没有组合被生成两次。要求1.如果0rn,被choose(n,r)生成的组合中，A1.r包含n中选r的组合。证明：关于r进行归纳证明。假设对于r=0显然成立。现在假设r0，对于任意的ir1,，在由程序choose(i,r-1)产生的组合中，A1.r-1包含从1.i中选r-1的组合。现在调用程序choose(i-1,r-1),i的取值由r到n,因此,由归纳假设和Ar的设定值i，在由程序choose(n,r)产生的组合中A1.r包含从1.i-1中选r-1的组合，遵循i的值。那意味着，A1.r中包含从1.n中选r的组合。要求2.程序choose(n,r)调用会产生的组合数目为证明：在r上使用归纳法证明。假设对于r=0是明显成立的。现在假设r0，对于任意的r1in，程序choose(i,r-1)一次将产生的组合数目为现在，choose(n,r)调用choose(i-1,r-1),i的取值rin.因此，由归纳假设，生成的组合数目为第一部遵从重索引，第二部遵从恒等式2恒等式1恒等式2要求：对于任意的n0和1rn,证明：关于n进行归纳假设证明。假设对于n=r是明显成立的，在这种情况下等式的两边为1现在假设nr时成立我们需要证明的是现在有归纳假设有，（由恒等式1）回到正确性证明要求3.程序choose(n,r)的一次调用，产生从1.n中选r的组合，没有组合是重复的。证明：这个证明关于r进行归纳法证明，证明过程与上面类似。现在我完成正确性证明：由有要求1，程序choose(n,r)的一次调用将会产生从1.n中选r的所有组合(因为r个元素一次性有数组A中选出，根据要求3，不会产生重复的组合)由要求2，将会产生生成组合的正确数目。因此它将会产生所有从1.n中选r个的正确组合。分析设T(n,r)是在choose(n,r)中产生的时间数量。要求：对于任意的n1和0rn,证明：choose(n,r)的一次调用将会生成下面的递归调用fori:=rtondoAr:=ichoose(i1,r1)因此，成本的总和为我们关于r进行归纳法证明要求对于r=0明显成立。现在假设对于r0和任意的i1.最优性由上面可知数组生产算法耗时为因为每个任务生成的额外计算是一个常数，因此组合算法对于常数多元而言并不是最优的。C为组合数量A为处理任务数Ratio(比例)为A/C最优rn/2可看出表格上下有一定的对称性，观察发现如果rn/2时有有没有这样的规律呢？需要证明要求：如果1rn/2,则有证明：首先我们需要证明要求要求对于r=1，2成立。然后我们应用归纳假设证明对于3rn/2成立当r=1T(n,1)=n(由观察得到),且因此，符合要求。当r=2时根据和我们要求这时成立的，因为n 4(回想一下,r n/2),因此n23n2 0 的最大根是当3rn/2要求：当3rn/2，时有关于n进行归纳假设证明。基本结为n=6.此时r的值只能为3，实验证明算法需要34步去生成20个组合。因为2202=3834,假设对于基本要求成立。现在假设n6,这意味着r3.由归纳假设和情况1，2可得最优性回顾因此，我们的算法对于rn/2，是最优的。有时这是一样有用的:如果rn/2,生成没有选择的项目,而不是有选择的项目。回溯法4继续讨论回溯的组合问题，它将应用于1团问题2独立集问题3拉姆齐数完整图Kn=(V,E)用来表示有n个顶点的完整图，其中V=1,2,.,n,E=VV.每个端点与另一个端点都有连线子图诱发型子图我们称B=(U,F)是G=(V,E)的子图，当UV且FE。我们称B=(U,F)是G=(V,E)的子图，当UV且F=(UU)E。诱发型子图与子图区别在于F的界定团问题一个团是一个完整图的诱导子图。团的大小就是顶点的数目。团问题：输入：一个图G=(V,E)，和一个整数r。输出：图G中一个大小为r的小团体，如果该小团体存在。假设:鉴于u,vV,我们可以在O(1)时间内检查是否(u,v)E。此图中有6元素的完整吗？答案是：当然有什么是团:一个诱发型子图里的一张完整图一个回溯算法使用回溯法在一个从V中选出，具有r个顶点的的组合A。假设程序Process(A)用来检查A中顶点是否形成团。A意味着在一个潜在团中的一系列顶点。调用clique（n,r）.无优化剪切回溯法：procedureclique(m,q)ifq=0thenprocess(A)elsefori:=qtomdoAq:=iclique(i1,q1)优化剪切回溯法（3行）：procedureclique(m,q)1.ifq=0thenprint(A)else2.fori:=qtomdo3.if(Aq,Aj)Eforallqn.不断运行下面程序，代入n=1,2,3,.，直至第一次不输出任何。n的值就是R(i,j)。foreachgraphGwithnverticesdoif(Gdoesnthaveacliqueofsizei)and(Gdoesnthaveanindept.setofsizej)thenprint(G)怎么实现这样的循环呢？寻找拉姆齐数遍历所有字符串数组A表现为一个上升的阶梯形影响矩阵G。一共有个入口。为了检验(i,j)E（ij），我们需要查阅关联矩阵的入口(i,j)，将被存储在An(i1)i(i+1)/2+j.寻找拉姆齐数Addressis：样例因为链接是两点间的，所以矩阵图是斜对称的。把每一排拆开后形成一维数组。谢谢！谢谢！