第9章回溯法2修改版.docx
- 文档编号:15704080
- 上传时间:2023-07-06
- 格式:DOCX
- 页数:33
- 大小:132.65KB
第9章回溯法2修改版.docx
《第9章回溯法2修改版.docx》由会员分享,可在线阅读,更多相关《第9章回溯法2修改版.docx(33页珍藏版)》请在冰点文库上搜索。
第9章回溯法2修改版
第9章回溯法
本章主要介绍回溯法。
回溯法(backtracking)是一种系统地搜索问题解的搜索算法。
它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。
算法搜索至解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解。
如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯。
否则,进入该子树,继续按深度优先的策略进行搜索。
回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。
而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可以结束。
这种以深度优先的方式系统地搜索问题的解的算法称为回溯法,它适用于解一些组合数较大的问题。
本章通过介绍几种常见的以回溯法思想为基础的问题解决方法,来深入的讲解回溯法。
9.1回溯法的算法框架
9.1.1问题的解空间
复杂问题常常有很多的可能解,这些可能解构成了问题的解空间,解空间也就是进行穷举的搜索空间。
所以,解空间中应该包括所有的可能解。
确定正确的解空间很重要,如果没有确定正确的解空间就开始搜索,可能会增加很多重复解,或者根本就搜索不到正确的解。
问题的解用向量表示:
X=(x1,x2,…,xn)。
在求一个或一组解向量的过程中要满足一定的约束条件,约束条件分为两种:
显示约束条件和隐式约束条件。
比如:
求一个或一组满足约束条件的解向量X=(x1,x2,…,xn),显示约束条件为xi∈Si,|Si|=mi,1≤i≤n,隐式约束条件为B(x1,x2,…,xn)。
例如下面的问题:
桌子上有6根火柴棒,要求以这6根火柴棒为边搭建4个等边三角形。
可以很容易用5根火柴棒搭建2个等边三角形,但却很难将它扩展到4个等边三角形,如图9.1(a)所示,是问题的描述产生了误导,因为它暗示的是一个二维的搜索空间(火柴是放在桌子上的),但是,为了解决这个问题,必须在三维空间中考虑,如图9.1(b)所示。
(a)二维搜索空间无解(b)三维搜索空间的解
图9.1错误的解空间将不能搜索到正确答案
对于任何一个问题,可能解的表示方式和它相应的解释隐含了解空间及其大小。
例如,对于有n个物品的0/1背包问题,其可能解的表示方式可以有以下两种:
(1)可能解由一个不等长向量组成,当物品i(1≤i≤n)装入背包时,解向量中包含分量i,否则,解向量中不包含分量i,解向量的长度等于装入背包的物品个数,则解空间由长度为0~n的解向量组成。
(2)可能解由一个等长向量{
…,
}组成,其中
=1(1≤i≤n)表示物品i装入背包,
=0表示物品i没有装入背包,则解空间由长度为n的0/1向量组成。
为了用回溯法求解一个具有n个输入的问题,一般情况下,将其可能解表示为满足某个约束条件的等长向量X=(
…,
),其中分量
(1≤i≤n)的取值范围是某个有限集合Si={
…,
},所有可能的解向量构成了问题的解空间。
例如,n个城市的TSP问题,将其可能解表示为向量X=(
…,
),其中分量
(1≤i≤n)的取值范围S={1,2,…,n},并且解向量必须满足约束条件
≠
(1≤i,j≤n)。
问题的解空间一般用解空间树(SolutionSpaceTrees,也称状态空间树)的方式组织,树的根结点位于第1层,表示搜索的初始状态,第2层的结点表示对解向量的第一个分量做出选择后到达的状态,第1层到第2层的边上标出对第一个分量选择的结果,依此类推,从树的根结点到叶子结点的路径就构成了解空间的一个可能解。
两类典型的解空间:
子集树和排列数。
当所给问题是从n个元素的集合中找出满足某种性质的子集时,相应的解空间树称为子集树。
在子集树中,一般地:
|S1|=|S2|=…=|Sn|=2,即每个结点有2棵的子树。
解空间为:
(0,0,……,0,0)
(0,0,……,0,1)
……
(1,1,……,1,1)
所以,解空间有
个元素。
若表示为树形结构就是一棵有
个叶结点的满二叉树,遍历子集树需Ω(
)的计算时间。
当所给问题是确定n个元素满足某种性质的排列时,相应的解空间树称为排列树。
通常情况下:
|S1|=n,|S2|=n-1,…,|Sn|=1,解空间为:
(1,2,3,……,n-1,n)
(2,1,3,……,n-1,n)
……
(n,n-1,……,3,2,1)
所以:
解空间有n!
个元素。
若表示为树形结构就是一个n度树,这样的树有n!
个叶结点,遍历排列树需Ω(n!
)计算时间。
9.1.2回溯法的基本思想
回溯法的基本思想是,在确定了解空间的组织结构后,回溯法就从开始结点(根结点)出发,以深度优先的方式搜索整个解空间。
这个开始结点就成为一个活结点,同时也成为当前的扩展结点。
在当前的扩展结点处,搜索向纵深方向移至一个新结点。
这个新结点就成为一个新的活结点,并成为当前扩展结点。
如果在当前的扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。
换句话说,这个结点不再是一个活结点。
此时,应往回移动(回溯)至最近的一个活结点处,并使这个活结点成为当前的扩展结点。
回溯法即以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已没有活结点时为止。
9.1.3递归回溯
由于回溯法对解空间作深度优先搜索,因此,在一般情况下用递归方法实现回溯法。
运用递归方法实现回溯法的一般框架如下:
voidbacktrack(intt)/*t表示递归深度*/
{
if(t>n)output(x);
else
for(inti=f(n,t);i<=g(n,t);i++)
/*f(n,t),g(n,t)表示当前扩展节点处未搜索过的子树的起始点和终止点*/
{
x[t]=h(i);/*当前扩展结点x[t]的第i个可选值*/
if(constraint(t)&&bound(t))backtrack(t+1);
/*constraint(t)和bound(t)是当前扩展节点处的约束函数和限界函数*/
}
}/*算法结束*/
9.1.4迭代回溯
采用树的非递归深度优先遍历算法,可将回溯法表示为一个非递归迭代过程。
迭代回溯的一般框架如下:
voidbacktrack(intt){
if(t>n)output(x);
else{
for(inti=f(n,t);i<=g(n,t);i++)
/*f(n,t),g(n,t)表示当前扩展节点处未搜索过的子树的起始点和终止点*/
{
swap(x[t],x[i]);/*得到一种排列*/
if(constraint(t)&&bound(t))backtrack(t+1);
/*constraint(t)和bound(t)是当前扩展节点处的约束函数和限界函数*/
swap(x[t],x[i]);/*回溯,还原*/
}
}
}
其中递归回溯和迭代回溯中的f(n,t),g(n,t)表示当前扩展结点处未搜索过的子树的起始标号和终止标号,h(i)表示当前扩展节点处,x[t]第i个可选值。
constraint(t)和bound(t)是当前扩展结点处的约束函数和限界函数。
constraint(t)返回true时,在当前扩展结点x[1:
t]取值满足约束条件,否则不满足约束条件,可减去相应的子树。
bound(t)返回的值为true时,在当前扩展结点x[1:
x]处取值未使目标函数越界,还需要由backtrack(t+1) 对其相应的子树进一步搜索。
用回溯法其实质上是提供了搜索解空间的方法,当我们能够搜遍解空间时,显然我们就能够找到最优的或者满足条件的解。
这便是可行性的问题,而效率可以 通过剪枝函数来降低。
但事实上一旦解空间的结构确定了,很大程度上时间复杂度 也就确定了,所以选择易于搜索的解空间很重要。
9.1.5回溯法求解问题的步骤
通过前面的讲解,我们可以归纳回溯法求解问题的一般步骤为:
(1)针对所给问题,定义问题的解空间;
(2)确定易于搜索的解空间结构;
(3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。
9.2装载问题
9.2.1问题描述
问题描述:
有n个集装箱要装到俩艘船上,每艘船的容载量分别问c1,c2,第i个集装箱的重量为w[i],同时满足:
w[1]+w[2]+...+w[n]<=c1+c2;求确定一个最佳的方案把这些集装箱装入这俩艘船上。
9.2.2解决方案
分析:
首先将第一艘船尽量装满,再把剩下的装在第二艘船上;第一艘船尽量装满等价于从n个集装箱选取一个子集,使得该子集的总重量与第一艘船的重量c1最接近,这样就类似于0-1背包问题。
问题解空间:
(x1,x2,x3...xn),其中每个xi为0表示不装在第一艘船上,为1表示在第一艘船上。
约束条件:
1.可行性约束条件:
w1*x1+w2*x2+...wi*xi+...+wn*xn<=c1,放在第一艘船上的集装箱总重量不能大于第一艘船的重量;
2.最优解约束条件:
remain+cw>bestw(remain表示剩余集装箱重量;cw表示当前已装上的集装箱的重量;bestw表示以前确定的集装箱装入c1中的重量)。
9.2.3算法实现
利用递归求解方法,相应的程序如下:
#include
#include
int*w;/*存放每个集装箱的重量*/
intnumber;/*集装箱的数目*/
intc;/*第一艘船的承载量*/
intcw;/*当前载重量*/
intremain;/*剩余载重量*/
int*x;/*存放搜索时每个集装箱是否选取*/
intbestw;/*存放最优的放在第一艘船的重量*/
int*bestx;/*存放最优的集装箱选取方案*/
voidbacktrace(intk)/*backtrace实现回溯搜索,搜索子集树中第k层结点*/
{
if(k>number)/*到达叶结点,更新最优解bestx,bestw*/
{
for(inti=1;i<=number;i++)
{
bestx[i]=x[i];
}
bestw=cw;
return;
}
else
{
remain-=w[k];
if(cw+w[k]<=c)/*如果当前剩余空间可以放下当前物品,则搜索左子树*/
{
x[k]=1;
cw+=w[k];
backtrace(k+1);
cw-=w[k];
}
if(remain+cw>bestw)/*搜索右子树*/
{
x[k]=0;
backtrace(k+1);
}
remain+=w[k];/*返回上层前,还原剩余载重量和*/
}
}
intbestSoution(int*w,intnumber,intc)/*bestSoution函数实现最优解决方案*/
{
remain=0;
for(inti=1;i<=number;i++)
{
remain+=w[i];
}
bestw=0;
backtrace
(1);
returnbestw;/*输出最优载重量*/
}
intmain()
{
printf("请输入集装箱的数目:
");
scanf("%d",&number);
w=newint[number+1];
x=newint[number+1];
bestx=newint[number+1];
printf("请输入第一艘船的装载量:
");
scanf("%d",&c);
printf("请输入每个集装箱的重量:
\n");
for(inti=1;i<=number;i++)
{
printf("i=");
scanf("%d",&w[i]);
}
bestw=bestSoution(w,number,c);
for(i=1;i<=number;i++)
{
printf("%d,",bestx[i]);
}
printf("\n");
printf("%d\n",bestw);
}
在此程序中,backtrace()函数实现回溯搜索。
如果到达叶结点,则判断当前的cw,如果比前面的bestw好,则替换原最优解。
如果当前剩余空间可以放下当前物品,也就是cw+w[k]<=c,则当前载重cw=cw+w[k],递归访问其左子树。
如果剩余载重量加上当前载重量大于bestw,即remain+cw>bestw,则访问其右子树。
程序运行结果如图9.2所示:
图9.2.递归求解实现装载问题
9.3批处理作业调度
9.3.1问题描述
问题描述:
给定n个作业的集合j={
...,
}。
每一个作业j[i]都有两项任务分别在两台机器上完成。
每一个作业必须先由机器1处理,然后由机器2处理。
作业j[i]需要机器j的处理时间为t[j][i],其中i=1,2,...,n,j=1,2。
对于一个确定的作业调度,设F[j][i]是作业i在机器j上的完成处理的时间。
所有作业在机器2上完成处理的时间之和f=sigmaF[2][i]称为该作业调度的完成时间之和。
批处理作业调度问题要求对于给定的n个作业,制定最佳作业调度方案,使其完成时间和达到最小。
9.3.2解决方案
分析:
批处理作业调度是要从n个作业的所有排列中找出有最小完成时间和的作业调度,所以批处理调度问题的解空间是一棵排列树。
按照回溯法搜索排列树的算法框架,设开始时x=[1,..,n]是所给的n个作业,则相应的排列树由所有排列构成。
比如:
机器1机器2
作业121
作业231
作业323
这3个作业的6种可能的调度方案是1,2,3;1,3,2;2,1,3;2,3,1;3,1,2;3,2,1;它们所相应的完成时间和分别是19,18,20,21,19,19。
易见,最佳调度方案是1,3,2,其完成时间和为18。
以1,2,3为例:
作业1在机器1上完成的时间为2,在机器2上完成的时间为3;作业2在机器1上完成的时间为5,在机器2上完成的时间为6;作业3在机器1上完成的时间为7,在机器2上完成的时间为10。
3+6+10=19,所以是19。
以1,3,2为例:
作业1在机器1上完成的时间为2,在机器2上完成的时间为3;作业3在机器1上完成的时间为4,在机器2上完成的时间为7;作业2在机器1上完成的时间为7,在机器2上完成的时间为8。
3+7+8=18,所以时间和为18
9.3.3算法实现
相应的程序如下:
#include
#include
#defineN3//作业数目
#defineMAX1000
intx[N+1]={0,1,2,3};
intm[3][N+1]={
0,0,0,0,
0,2,3,2,
0,1,1,3
};
intbestx[N+1];/*用于保存结果调度顺序*/
intf2[N+1];/*第i阶段机器2完成处理的时间*/
intf1=0;/*机器1完成处理时间*/
intf=0;/*当前完成时间和*/
intbestf=MAX;/*最优时间和*/
voidswap(int&a,int&b)/*swap()是一个指定两元素无条件交换函数*/
{
inttemp=a;
a=b;
b=temp;
}
voidBacktrace(intt)/*Backtrace()实现回溯搜索*/
{
if(t>N)/*如果到达叶结点,得到一个解*/
{
bestf=f;
for(inti=1;i<=N;i++)
{
bestx[i]=x[i];/*将当前记录保存在bestx[]中*/
}
}
else/*如果未到达叶结点*/
{
for(inti=t;i<=N;i++)
{
f1+=m[1][x[i]];
f2[t]=(f2[t-1]>f1?
f2[t-1]:
f1)+m[2][x[i]];/*当前扩展结点位于t-1层*/
f+=f2[t];
swap(x[t],x[i]);
if(f { Backtrace(t+1); } swap(x[t],x[i]); f1-=m[1][x[i]]; f-=f2[t]; } } } intmain() { /*memset函数将bestx所指内存区域的前4*(N+1)个字节设置成字符0*/ memset(bestx,0,(N+1)*sizeof(int)); memset(f2,0,(N+1)*sizeof(int)); Backtrace (1); printf("该作业调度的最优完成时间和为: %d\n调度顺序为: \n",bestf); for(inti=1;i<=N;i++) { printf("%d",bestx[i]); } return0; } 此程序中,Backtrace()函数实现回溯搜索。 如果到达叶结点,得到一个解,并将当前作业记录在bestx[]数组中,当前最优值存入变量。 如果未达到叶结点,当前扩展结点位于t-1层,采用深度优先的方式递归对相应子树进行搜索,计算新作业结点在机器1上的加工时间和在机器2上的加工时间。 在回溯搜索过程中,首轮搜索一直向下到底层叶结点,由于底层只有一个元素,可以得到一个可行解,将此解暂时看成最优解;注意此时回溯时的返回点,退到倒数第二层,即有两个元素的排列问题,进行交换后,产生另一个解,该解若优于前一个解就替换它,不优于则忽略;然后再退到倒数第三层,即有三个元素的排列问题,交换的次数依赖循环变量的初值i,每交换一次,又要深入下一层去求解,有更好的解就进行替换,并将调度情况记录下来。 依此类推,直到全部解空间树被扫描完毕。 程序运行结果如图9.3所示: 图9.3批处理作业调度问题 9.4符号三角形问题 9.4.1问题描述 问题描述: 如下图是由14个“+”和14个“-”组成的符号三角形,2个同号下面都是“+”,2个异号下面都是“-”。 -++-+++ -+--++ --+-+ +--- -++ -+ - 图9.4.1符号三角形 在一般情况下,符号三角形的第一行有n个符号,符号三角形问题要求对于给定的n,计算有多少个不同的符号三角形,使其所含的“+”和“-”的个数相同。 9.4.2解决方案 分析: 对于符号三角形问题,用n元组x[1: n]表示符号三角形的第一行的n个符号。 当x[i]=1时,表示符号三角形的第一行的第i个符号为“+”号;当x[i]=0时,表示符号三角形的第一行的第i个符号为“-”号;1≤i≤n。 由于x[i]是二值的,所以在用回溯法解符号三角形问题时,可以用一棵完全二叉树来表示其解空间。 在符号三角形的第一行的前i个符号x[1: i]确定后,就确定了一个由i*(i+1)/2个符号组成的符号三角形。 下一步确定了x[i+1]的值后,只要在前面已确定的符号三角形的右边加一条边,就可以扩展为x[1: i+1]所相应的符号三角形。 最终由x[1: n]所确定的符号三角形中包含的“+”号个数与“-”号个数同为n*(n+1)/4。 因此在回溯搜索过程中可用当前符号三角形所包含的“+”号个数与“-”号个数均不超过n*(n+1)/4作为可行性约束,用于剪去不满足约束的子树。 对于给定的n,当n*(n+1)/2为奇数时,显然不存在所包含的“+”号个数与“-”号个数相同的符号三角形。 由于第一行的每个符号需要不断改变,可以使用递归回溯搜索符合条件的解。 为了便于运算,设+为0,-为1,这样可以使用异或运算符表示符号三角形的关系 。 ++为+即0^0=0,--为+即1^1=0,+-为-即0^1=1,-+为-即1^0=1。 因为两种符号个数相同,可以对题解树剪枝, 当所有符号总数为奇数时无解,当某种符号超过总数一半时无解 。 9.4.3算法实现 相应的程序如下: #include"stdio.h" #include"stdlib.h" #include"string.h" typedefunsignedcharuchar; charcc[2]={'+','-'};/*便于输出*/ intn;/*第一行符号总数*/ inthalf;/*全部符号总数一半*/ intcounter;/*1计数,即“-”号计数*/ uchar**p;/*符号存储空间*/ longsum;/*符合条件的三角形计数*/ voidBacktrace(intt)/*t,第一行第t个符号*/ { inti,j; if(t>n)/*符号填充完毕*/ { sum++; printf("第%d个: \n",sum);/*打印符号*/ for(i=1;i<=n;++i) { for(j=1;j { printf(""); } for(j=1;j<=n-i+1;++j) { printf("%d",&cc[p[i][j]]); } printf("\n"); } } else { for(i=0;i<2;++i) { p[1][t]=i;/*第一行第t个符号*/ counter+=i;/*“-”号统计,因为"+"的值是0*/ /*当第一行符号>=2时,可以运算出下面行的某些符号,j可代表行号*/ for(j=2;j<=t;++j) { /*通过异或运算下行符号,t-j+1确定的很巧*/ p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2]; counter+=p[j][t-j+1]; } if((counter<=half)&&(t*(t+1)/2-counter<=half)) { /*若符号统计未超过半数,并且另一种符号也未超过半数,同时隐含两者必须相等才能结束*/ Backtrace(t+1);/*在第一行增加下一个符号*/ } /*回溯,判断另一种符号情况,像是出栈一样,恢复所有对counter的操作*/ for(j=2;j<=t;++j) { counter-=p[j][t-j+1]; } counter-=i; } } } intmain() { printf("请
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第9章 回溯法2修改版 回溯 修改