回溯-第九章算法设计与分析

9.5回溯法本章学习的主要内容9.5.1回溯法基本思想9.5.2

n皇后问题9.5.3批处理作业调度9.5.1回溯法基本思想本节学习的主要内容回顾0-1背包问题回溯法思想及搜索子集树的一般算法旅行售货员问题用回溯法搜索排列树的算法框架回顾0-1背包问题问题：给定n种物品和一个背包，背包容量为c。物品i的重量是wi，其价值为vi。选择物品装入背包时不能选择物品i的部分，问如何选择装入背包中的物品，使得装入背包中物品总价值最大？0-1背包问题的形式化描述给定c>0，wi>0，vi>0，1in，要求找出一个n元向量

(x1,x2,…xn)，xi{0，1}，使得:

且达到最大。

1.问题的解空间例如：0-1背包问题，其解空间是长度为n的0-1向量。当n=3时，其解空间是

{(0,0,0)，(0,1,0)，(0,0,1)，(1,0,0)，(0,1,1)，(1,0,1)，(1,1,0)，(1,1,1)}解空间的二叉树表示CA01B01D01HIJ01NOE01JKF01LM10考虑0-1背包的一个实例每个物品的重量W=[16,15,15]每个物品的价值V=[45,25,25]背包容量,C=30重量W=[16,15,15]，价值V=[45,25,25]，背包容量C=30,SV表示总价值，r表示背包剩余容量CA01B01D01HIJ01NOE01JKF01LM10r=14,sv=45r=14<w2=15r=14,sv=45r=14<w3=15r=14,sv=45重量W=[16,15,15]，价值V=[45,25,25]，背包容量C=30,SV表示总价值，r表示背包剩余容量CA01B01D01HIJ01NOE01JKF01LM10r=14,sv=45r=30,sv=0r=15,sv=25r=0,sv=50重量W=[16,15,15]，价值V=[45,25,25]，背包容量C=30,SV表示总价值，r表示背包剩余容量CA01B01D01HIJ01NOE01JKF01LM10r=0,sv=50r=15,sv=25重量W=[16,15,15]，价值V=[45,25,25]，背包容量C=30,SV表示总价值，r表示背包剩余容量CA01B01D01HIJ01NOE01JKF01LM10r=0,sv=50r=30,sv=0r=15,sv=25重量W=[16,15,15]，价值V=[45,25,25]，背包容量C=30,SV表示总价值，r表示背包剩余容量CA01B01D01HIJ01NOE01JKF01LM10r=0,sv=50r=30,sv=0r=30,sv=0重量W=[16,15,15]，价值V=[45,25,25]，背包容量C=30,SV表示总价值，r表示背包剩余容量CA01B01D01HIJ01NOE01JKF01LM10r=0,sv=50返回回溯法的思想从开始结点(根结点)出发，以深度优先的方式搜索整个解空间。开始结点是一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点，这个结点就成为当前扩展结点。如果当前的扩展结点不能再向纵深移动，则当前的扩展结点成为死结点。回溯法的框架-用回溯法搜索子集树的一般算法voidBacktrack(intt){if(t>n)Output(x);else{x[t]=1;//进入左子树

if(Constraint(t)&&Bound(t))Backtrack(t+1);x[t]=0;//进入右子树

if(Constraint(t)&&Bound(t))Backtrack(t+1);}}//X[i]表示子集树的边上的值,树根为第1层用回溯法搜索子集树的一般算法Constraint(t)表示在当前的扩展结点处的约束函数。如果返回true，则表示在当前的扩展结点处x[1:t]的取值满足问题的约束条件。如果返回false，则表示在当前的扩展结点处x[1:t]的取值不满足问题的约束条件。可以剪去相应的子树。用回溯法搜索子集树的一般算法Bound(t)表示在当前的扩展结点处的限界函数。如果返回true，则表示在当前的扩展结点处x[1:t]的取值没有使目标函数越界。需要调用Backtrack(t+1)进入其子树进一步搜索。如果返回false，则表示在当前的扩展结点处x[1:t]的取值使目标函数越界。可以剪去相应的子树。返回旅行售货员例子问题：某售货员要到若干城市去推销商品，已知各个城市之间的路程，要选定一条从驻地出发，经过每个城市一次，最后回到驻地，要求总的路程最小。1324610203054解空间的树表示CA24B43DHI3NOEJKF2LM44GPQ32423321111111周游解空间解旅行售货员问题CA24B43DHI3NOEJKF2LM44GPQ3242332111111130355559周游解空间解旅行售货员问题CA24B43DHI3NOEJKF2LM44GPQ32423321111111594060>59周游解空间解旅行售货员问题CA24B43DHI3NOEJKF2LM44GPQ32423321111111596112125周游解空间解旅行售货员问题CA24B43DHI3NOEJKF2LM44GPQ324233211111112526>25周游解空间解旅行售货员问题CA24B43DHI3NOEJKF2LM44GPQ32423321111111254141925周游解空间解旅行售货员问题CA24B43DHI3NOEJKF2LM44GPQ32423321111111252429>25周游解空间解旅行售货员问题CA24B43DHI3NOEJKF2LM44GPQ3242332111111125返回用贪心策略不能得到旅行售货员问题的最优解1423321281贪心：1->3->4->2->1总开销12最优：1->2->3->4->1总开销8用回溯法搜索排列树的算法框架voidBacktrack(intt){if(t>n)Output(x);elsefor(inti=t;i<=n;i+1){Swap(x[t],x[i]);if(Constraint(t)&&Bound(t))Backtrack(t+1);Swap(x[t],x[i]);}}//X[i]表示排列树的边上的值(数字序号),树根为第1层template<classType>voidSwap(Type&x,Type&y){Typetemp=x;x=y;y=temp;}通过排列问题理解排列树框架设R={r1，r2，…，rn}是要进行排列的n个元素，Ri=R-{ri}。集合X中元素的全排列记为Perm(X)。

(ri)Perm(Ri)表示在全排列Perm(Ri)的每一个排列前加上前缀ri得到的排列。R的全排列递归定义如下：当n=1时，Perm(R)=(r1),r1是R中唯一的元素。当n>1时，Perm(R)由(ri)Perm(Ri)(i=1,2,…,n)构成template<classType>voidPerm(Typelist[],intk,intm){if(k>m){ for(inti=0;i<=m;i++)cout<<list[i]; cout<<endl; } else{ for(inti=k;i<=m;i++){ Swap(list[k],list[i]); Perm(list,k+1,m);Swap(list[k],list[i]); }}}//完成list中下标索引从k到m的元素的排列。12341234k=1,表示集合起始索引m=4,表示集合终止索引集合起始索引为k+1=2m=4,表示集合终止索引listSwap(1,1)1234123412341234k=1,表示集合起始索引m=4,表示集合终止索引集合起始索引为k+1=2m=4,表示集合终止索引Swap(1,1)listSwap(1,2)Swap(1,1)1234123412341234k=1,表示集合起始索引m=4,表示集合终止索引集合起始索引为k+1=2m=4,表示集合终止索引Swap(1,1)listSwap(1,2)Swap(1,1)12342314Swap(1,2)Swap(1,3)1234123412341234k=1,表示集合起始索引m=4,表示集合终止索引集合起始索引为k+1=2m=4,表示集合终止索引Swap(1,1)listSwap(1,2)Swap(1,1)12342314Swap(1,2)Swap(1,3)12342431Swap(1,3)Swap(1,4)用回溯法搜索排列树的算法框架对于旅行售货员问题:调用Backtrack之前，应将数组x初始化为(1,2,…,n)，即x[1]=1,x[2]=2,…,x[n]=n主程序应调用Backtrack(2)回溯法解题步骤定义解空间确定易于搜索的解空间结构以深度优先方式搜索解空间，在搜索过程中，用剪枝函数避免无效搜索。子集树和排列树当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。当所给问题是确定n个元素的满足某种性质的排列时，相应的解空间树称为排列树。0-1背包问题是一棵子集树旅行售货员问题是一棵排列树返回9.5.2n皇后问题问题描述n后问题要求在一个n*n格的棋盘上放置n个皇后，使得他们彼此不受攻击。按照国际象棋的规则，一个皇后可攻击与之处在同一行或同一列或同一斜线上的其他任何棋子。因此，n后问题等价于要求在一个n*n格的棋盘上放置n个皇后，使得任何2个皇后不能被放在同一行或同一列或同一斜线上。算法设计对于n后问题，我们用n元组x[1:n]表示它的解。其中，x[i]表示第i个皇后放在棋盘的第i行的第x[i]列。由于不允许将任何2个皇后放在同一列上，所以解向量中的诸x[i]互不相同。在这里，任何两个皇后不能放在同一斜线上是问题的隐约束。将n*n格的棋盘看作是一个二维方阵，其行号从上到下，列号从左到右依次编号为1、2…、n。123123456456若两个皇后放置的位置分别为(i,j)和(k,l)，且i-j=k-l或i+j=k+l，则说明这两个皇后处于同一斜线上。以上2个方程分别等价于i-k=j-l和i-k=l-j。由此可知，只要|i-k|=|j-l|成立，就表明这2个皇后位于同一条斜线上。据此我们可以设计一个函数Place来测试：若将皇后k放在第k行的第x[k]列是否与前面已放置的k-1个皇后都不在同一列，而且都不在同一斜线上。boolQueen::Place(intk) { for(intj=1;j<k;j++) if(abs(k-j)==abs(x[j]-x[k]))|| (x[j]==x[k])) returnfalse; returntrue; }用回溯法解n后问题时，可以用一棵完全n叉树来表示其解空间。定义一个类Queen。函数Backtrack是类Queen的成员。递归函数Backtrack(1)实现对整个解空间的回溯搜索。Backtrack(t)搜索解空间中第t层子树。 用可行性约束函数Place可剪去不满足行、列和斜线约束的子树。函数nQueen负责类Queen的私有变量的初始化。sum记录当前已找到的可行方案数。解n后问题的回溯算法可描述如下：

classQueen{ friendintnQueen(int); private: boolPlace(intk);

voidBackTrack(intt); intn,//皇后个数 *x;//当前解

longsum;//当前已找到的可行方案数

};voidQueen::Backtrack(intt){ if(t>n)sum++; else for(inti=1;i<=n;i++) { x[t]=i; if(Place(t))Backtrack(t+1); }}在函数Backtrack中，当t>n时，表示算法已搜索至一个叶结点，得到一个新的n皇后互不攻击放置方案，因此当前已找到的可行方案数sum增1。当t<=n时，当前扩展结点Z是解空间中的一个内部结点。该结点有x[t]=1,2,…,n共n个儿子结点。对当前扩展结点Z的每一个儿子结点，由函数Place检查其可行性，并以深度优先的方式递归地对可行子树进行搜索，或减去不可行子树。intnQueen(intn){ QueenX; //初始化X X.n=n;X.sum=0; int*p=newint[n+1];

for(inti=0;i<=n;i++)p[i]=0;

X.x=p;X.Backtrack(1); delete[]p; ReturnX.sum;}313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123迭代回溯将上述回溯法表示成非递归的形式。这样一来，可省去O(n)的递归栈空间。解n后问题的非递归迭代回溯法Backtrack可描述如下.当n为３时，用三叉树回溯算法遍历时无解。当n为4时，用四叉树回溯算法遍历时有2个可行解。voidQueen::Backtrack(void){ x[1]=0; intk=1; while(k>0) { x[k]+=1; while((x[k]<=n)&&!(Place(k)))x[k]+=1; if(x[k]<=n){ if(k==n)sum++; else{ k++; x[k]=0; }} else k--; }}voidQueen::Backtrack(inti)//递归遍历所有子树{ if(i>n)sum++;//遍历到最下端时，可行解加1 else for(intj=i;j<=n;j++){ Swap(x[i],x[j]); if(Place(i))Backtrack(i+1);//若可行进下层

Swap(x[i],x[j]); }}把n叉树变成排列树C13A32DHI2NOEJKF1LM33GPQ21312213皇后问题的解空间树9.5.3批处理作业调度问题描述：给定n个作业的集合J=(J1,J2,…,Jn)。每一个作业Ji都有2项任务分别在2台机器上完成。每一个作业必须先由机器1处理，然后再由机器2处理。例如：先计算，再打印作业Ji需要机器j的处理时间为tij，i=1,2,…,n;j=1,2。例子tij机器1机器2作业121作业231作业323对于一个确定的作业调度(即n个作业的某个执行顺序)，Fij是作业i从提交到在机器j上完成处理所需要的时间。特别地，Fi2是作业i从提交到在机器2上完成处理所需要的时间，实际上，Fi2是在这一调度下作业Ji从提交到彻底完成所需的时间。为该作业调度下，所有作业完成时间和。对于给定的作业集合J，制订一个最佳作业调度方案，使f达到最小。调度方案为(1,2,3)，作业调度完成时间和计算过程123456089107213123F12=3F22=6F32=10对于调度方案(1,2,3)作业调度完成时间和为：f=F12+F22+F32

=3+6+10=19tij机器1机器2作业121作业231作业323调度方案为(1,3,2)，作业调度完成时间和计算过程123456089107212331F32=7F22=8对于调度方案(1,3,2)作业调度完成时间和为：f=F12+F22+F32

=3+7+8=18tij机器1机器2作业121作业231作业323F12=3调度方案为(2,3,1)，作业调度完成时间和计算过程123456089107312321F22=4F32=8F12=9对于调度方案(2,3,1)作业调度完成时间和为：f=F12+F22+F32

=9+4+8=21tij机器1机器2作业121作业231作业323调度方案为(3,1,2)，作业调度完成时间和计算过程123456089107232131F32=5F12=6F22=8对于调度方案(3,1,2)作业调度完成时间和为：f=F12+F22+F32

=6+8+5=19tij机器1机器2作业121作业231作业323批处理作业调度的算法设计(1)由于我们要从n个作业的所有排列中找出具有最小完成时间和的作业调度，所以批处理调度问题的解空间是一棵排列树。按照回溯法搜索排列树的算法框架，初始时X[1:n]=[1,2,3,…,n]，则相应的排列树为X[1:n]的所有排列构成。3个作业的解空间树C13A32DHI2NOEJKF1LM33GPQ2131221批处理作业调度的算法设计(2)当i<n时，当前扩展结点位于排列树的第i层。此时，算法需要选择下一个要安排的作业，以深度优先的方式递归地对相应子树进行搜索。f表示当前完成作业的时间和，bestf表示完成作业的时间和的当前最优值。如果f>=bestf，则以当前扩展结点为根的子树被剪切。批处理作业调度的算法设计(3)在递归函数Backtrack中，当i>n时，表示算法已搜索至一个叶子结点，得到一个新的调度方案。此时需要更新最优调度值bestx和当前最佳作业调度完成时间和bestf。f表示当前完成作业的时间和，bestf表示完成作业的时间和的最优值。初始:f=0,bestf=tifC13A32DHI2NOEJKF1LM33GPQ2131221tij机器1机器2作业121作业231作业323F12=3,f=3,bestf=tifF22=6,f=9,bestf=tifF32=10,f=19,bestf=19f表示当前完成作业的时间和，bestf表示完成作业的时间和的最优值。初始:f=0,bestf=0C13A32DHI2NOEJKF1LM33GPQ2131221tij机器1机器2作业121作业231作业323F32=10,f=19,bestf=19f表示当前完成作业的时间和，bestf表示完成作业的时间和的最优值。初始:f=0,bestf=0C13A32DHI2NOEJKF1LM33GPQ2131221tij机器1机器2作业121作业231作业323F32=10,f=19,bestf=19F12=3,f=3,bestf=19F32=7,f=10,bestf=19F22=8,f=18,bestf=1818<19f表示当前完成作业的时间和，bestf表示完成作业的时间和的最优值。初始:f=0,bestf=0C13A32DHI2NOEJKF1LM33GPQ2131221tij机器1机器2作业121作业231作业323F22=8,f=18,bestf=18f表示当前完成作业的时间和，bestf表示完成作业的时间和的最优值。初始:f=0,bestf=0C13A32DHI2NOEJKF1LM33GPQ2131221tij机器1机器2作业121作业231作业323F22=8,f=18,bestf=18F22=4,f=4,bestf=18F12=6,f=10,bestf=18F32=10,f=20,bestf=18f>bestff表示当前完成作业的时间和，bestf表示完成作业的时间和的最优值。初始:f=0,bestf=0C13A32DHI2NOEJKF1LM33GPQ2131221tij机器1机器2作业121作业231作业323F22=8,f=18,bestf=18f表示当前完成作业的时间和，bestf表示完成作业的时间和的最优值。初始:f=0,bestf=0C13A32DHI2NOEJKF1LM33GPQ2131221tij机器1机器2作业121作业231作业323F22=8,f=18,bestf=18F22=4,f=4,bestf=18F32=8,f=12,bestf=18F12=9,f=21,bestf=18f>bestff表示当前完成作业的时间和，bestf表示完成作业的时间和的最优值。初始:f=0,bestf=0C13A32DHI2NOEJKF1LM33GPQ2131221tij机器1机器2作业121作业231作业323F22=8,f=18,bestf=18f表示当前完成作业的时间和，bestf表示完成作业的时间和的最优值。初始:f=0,bestf=0C13A32DHI2NOEJKF1LM33GPQ2131221tij机器1机器2作业121作业231作业323F22=8,f=18,bestf=18F32=5,f=5,bestf=18F12=6,f=11,bestf=18F22=9,f=20,bestf=18f>bestff表示当前完成作业的时间和，bestf表示完成作业的时间和的最优值。初始:f=0,bestf=0C13A32DHI2NOEJKF1LM33GPQ2131221tij机器1机器2作业121作