大三-算法设计chap13回溯

回溯法要求在相对问题的输入规模按照指数级增长的数据集中，找出一个具有指定特性的元素在图的所有顶点排列中求一个哈密顿回路求背包中最有价值的物品子集蛮力方法：先生成所有的候选解，然后再找出那个具有需要特性的元素回溯法：每次只构造解的一个分量，然后评估这个部分构造解。若无法对下一个分量进行合法的选择，则进行回溯，将部分构造解的最后一个分量替换为它的下一个选择。回溯法如果把问题的解组织成一棵树的话，从根结点到达某个叶结点的路径就可以看作问题的一个解，叶子就是搜索的目标。回溯法就是搜索出所有的叶结点，然后选择一个满足要求的叶结点。回溯法可以系统地在所有可能的选择中搜索问题的一个最优解。若把做的决策序列用一个向量(x1,x2,…,xn)表示，回溯法就是以深度优先的方式逐步确定xi的值，直到找到问题的解。回溯法通过枚举所有的决策序列保证解的正确性。决策序列的多少，即解的多少极大地影响回溯法的效率。回溯法算法思想为了获得问题的解(x1,x2,…,xn)，从x1出发，逐步扩展部分解(x1,x2,…,xi)通过尝试解元素xi+1的一个值，测试扩展出的(x1,x2,…,xi+1)是否还是一个部分解若是，继续向下搜索若不是，尝试xi+1的其它取值。若x的所有取值都已试过了，则回溯到xi，尝试xi的下一个取值。依次类推，直到找到问题的一个解，或没有解。回溯法的解题步骤1)定义问题的解空间令Si表示解元素xi的取值范围，则问题的解空间为S1×S2×…×Sn

。通常解空间非常大，因此为了提高回溯法的效率，需要有效地组织解空间.2)组织解空间以便更容易地搜索问题的解，典型的解空间组织方式是一棵树或一个图.3)用深度优先搜索的方式搜索问题的解，并用剪枝函数来避免去搜索一个无解的子空间。解空间问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。显约束：对分量xi的取值进行限定。隐约束：为满足问题的解而对不同分量之间施加的约束。解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。问题举例8－皇后问题：在一个8×8的棋盘上放8个皇后，且使得每两个之间都不能互相“攻击”，即都不出现在同一行、同一列及同一条斜对角线上。解的表示：假定第i个皇后放在第i行，用8－元组(x1,x2,…,x8)表示解，其中xi示放置皇后i的列号。显示约束:Si=(1,2,3,…8),1i8隐示约束：没有两个xi(1i8)可以相同（在不同的列上），且没有两个皇后在同一斜对角线上。××××××××××××××１２１２３３４１２１２３４１１２３０５４６７８问题举例子集和数问题：已知n+1个正整数：w1,w2,…,wn和M，要求找出wi的和数等于M的所有子集。解的表示1：用其和数为M的wi的下标来表示解向量。则可以用k-元组(x1,x2,…,xk)来表示解(x表示下标),1kn。不同的解可以是大小不同的元组。显示约束：xi{j|j是一个整数且1jn}.隐示约束：没有两个xi是相同的且对应的wi的和数是M；为避免子集重复，要求xi<xi+1,1in.问题举例子集和数问题：已知n+1个正整数：w1,w2,…,wn和M，要求找出wi的和数示M的所有子集。解的表示2：用n-元组(x1,x2,…,xn)来表示解,xi{0,1},1in。如果没有选择wi，则xi＝0，否则xi＝1。解是大小相同的元组。显示约束：xi{0，1}.隐示约束：为1的xi对应的wi的和数是M.生成问题状态的基本方法扩展结点(E结点):一个正在产生儿子的结点称为扩展结点活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点死结点:一个所有儿子已经产生的结点称做死结点深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点回溯法回溯法:如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(boundingfunction)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。使用限界函数的深度优先结点生成方法称为回溯法.两种形式的问题的解问题的解是所搜索集合的子集，以达到某种优化目标问题的解是所搜索集合中元素的一个排列，以达到某种约束要求回溯法可以很方便地遍历一个集合的所有子集或所有的排列应用举例应用回溯法求解3着色问题；应用回溯法求解哈密顿回路问题。子集树当问题是需要求n个元素的子集，以便达到某种优化目标时，我们可以把这个解空间组织成一棵子集树。若Si的大小为k，则有kn个子集。当n很大时，解空间将非常巨大。…………………………S2S1SnS2第1层第2层第n层x1子集树的回溯法伪码Backtrack(i)

递归描述1ifi>nthenupdate(x)2else3foreacha∈Sido4xi←a5ifC(i)andB(i)then6Backtrack(i+1)约束函数C(i)和界限函数B(i)决定(x1,x2,…,xi)是否是一个部分解，这两个函数也统称为剪枝函数子集树的回溯法伪码InterateBacktrack(i)迭代描述1i←12whilei>0do3whileSiisnotexhausteddo//对Si中的元素进行枚举4xi←nextelementinSi5ifi=nthenUpdate(x)//搜索到叶结点6elseifC(i)andB(i)theni←i+1//满足条件继续搜索7i←i-1//进行回溯排列树当问题是需要求n个元素的一个排列，则可以将解空间组织成一棵排列树。建一个含n个元素的数组A,xi的值是数组A中下标从1到n的一个元素，并且之前从未出现过。共有n!个排列。……23n……23n……12n……S1S2S2SnnSniSn1第1层第2层第n层排列树的回溯法伪码BacktrackPerm(i)1ifi>nthenupdate(x)2else3forj←itondo4xi

↔xj5ifC(i)andB(i)then6BacktrackPerm(i+1)7xi↔xj搜索从一个给定的排列(x1,x2,…,xn)开始。假定已经搜索到部分解(x1,x2,…,xi-1)，通过尝试解元素xi的一个值，xi在{xi,xi+1,…,xn}中。为了保证排列中的每个元素不同，通过交换xi↔xj来实现。再利用C(i)和B(i)来测试扩展出的解是否还是一个可行的部分解。提高搜索效率搜索能否继续，取决于约束函数C(i)和界限函数B(i)。可以利用C(i)和B(i)来剪除无用的分支。改进搜索性能应考虑的问题如何找到约束函数对于求最大值（最小值）问题，怎样计算上界（下界），从而利用该信息构造界限函数如何利用约束函数和界限函数来剪除无用的分支用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。N皇后问题在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1234567812345678QQQQQQQQN皇后的解空间从n2个位置中选n个位置，则解空间的大小为令xi表示皇后i的列位置，问题的解向量表示为(x1,x2,…,xn)，因为限制皇后在不同的行，故解空间的大小为nn，解空间可以组织为一棵子集树进一步限制每个皇后在不同的列，解空间大小为n！,解空间可以组织为一棵排列树。解向量：(x1,x2,…,xn)解空间：子集树显约束：xi=1,2,…,n隐约束：

1)不同列：xixj2)不处于同一正、反对角线：|i-j||xi-xj|Place(k)1forj←1tok-1do2if|xk-xj|==|k-j|or(xk==xj)then3returnfalse;4returntrue;BacktNqueens(t)1ift>nthensum++;2else3fori←1tondo

4xt←i;5if(Place(t))BacktNqueens(t+1);BacktNqueens()x[1]←0k←1whilek>0do

whilex[k]<=n-1dox[k]←x[k]+1

ifPlace(k)=truethen

ifk==nthensum++

elsek←k+1x[k]←0k←k-10-1背包问题

解空间：子集树，大小为2n

解向量：(x1,x2,…,xn),xi∈{0,1}cw(i)表示部分解(x1,x2,…,xn)的重量

第i-1层结点取1分支的约束函数为C(i)=cw(i-1)+wi,若C(i)>W，则停止搜索该分支，否则继续搜索只考虑约束函数的0/1背包问题BtKnapsack(i)

递归描述1ifi>nthen//到达叶结点，则找到一个解2ifcv>bestvthen//比当前最好的bestv价值更大3bestv←cv//则更新最好价值4else//没有搜索到叶结点5ifC(i)<=Wthen//试探走1分支6cw←cw+w(i)7BtKnapsack(i+1)

8elsecw←cw-w(i)9BtKnapsack(i+1)//对于0分支，无条件回溯，尝试下一个i约束函数C(i)=cw+w[i]引入界限函数的0/1背包问题仅利用约束函数，搜索效率不高，因此需引进界限函数

B(i)=cv(i)+r(i)cv(i)表示目前到第i层结点已经装入背包的物品价值r(i)表示剩余物品的总价值bestv表示目前所得到的最好的价值若B(i)<=bestv，则停止搜索第i层及其下面的层当r(i)越小时，B(i)越小，剪掉的分支越多。引入界限函数的0/1背包问题如何构造更小的r(i)?首先将物品以单位重量价值递减的顺序进行排序v1/w1>=v2/w2>=…>=vn/wn考虑第i层，背包的剩余容量为W-cw(i)，用贪心算法把剩余的物品放入背包，直到装不进背包的物品k为止，即物品k放不进去。则依上式计算是r(i)是最优的，不存在比贪心装载更优的方案引入界限函数的0/1背包问题r(i)1rw←W-cw2b←cv3whilei+1<=nandw[i+1]<=rwdo4rw←rw-w[i+1]5b←b+v[i+1]6i←i+17ifi+1<=nthenb←b+v[i+1]/w[i+1]*rw8returnb结合约束函数和界限函数的背包回溯算法BtKnapsack(i)1ifi>nthen2ifcv>bestvthen3bestv←cv4forj←1tondo5bestx[j]←x[j]6else7ifC(i)<=Wthenx[i]←18cw←cw+w[i];vc←cv+v[i]9BtKnapsack(i+1)10cw←cw-w[i];vc←cv-v[i]11ifB(i)>bestvthenx[i]←012BtKnapsack(i+1)哈密顿回路哈密顿回路:设G=(V,E)是一个n结点的连通图.一个哈密顿回路是一条沿着图G的n条边环行的路径,它访问每个结点一次并且回到它的原始位置.找出一个图中哈密顿回路的回溯算法.解的表示:(x1,…,xn)表示解,其中,xi是找到的回路中第i个被访问的结点.约束:x(1)=1,如果1<k<n,则x(k)可以是不同于x(1),…,x(k-1)且和x(k-1)有边相连的任一结点.x(n)只能是必须与x(n-1)和x(1)有边相连的结点.12343010206541342422334232434旅行商问题BtTSP(i)1ifi=nthen2ifw[x[n-1],x[n]]<>∞andw[x[n],1]<>∞then3ifcw+w[x[n-1],x[n]]+w[x[n],1]<bestwthen4bestw←cw+w[x[n-1],x[n]]+w[x[n],1]5forj←1tondo6bestx[j]←x[j]7elseforj←itondo8ifw[x[i-1],x[j]]<>∞andcw+w[x[i-1],x[j]]<bestwthen9xi

↔xj10cw←cw+w[x[i-1],x[i]];11