算法设计与分析 第七章回溯法.docx
- 文档编号:9198909
- 上传时间:2023-05-17
- 格式:DOCX
- 页数:22
- 大小:149.85KB
算法设计与分析 第七章回溯法.docx
《算法设计与分析 第七章回溯法.docx》由会员分享,可在线阅读,更多相关《算法设计与分析 第七章回溯法.docx(22页珍藏版)》请在冰点文库上搜索。
算法设计与分析第七章回溯法
第七章回溯法
§1.回溯法的基本思想
回溯法有“通用的解题法”之称。
应用回溯法解问题时,首先应该明确问题的解空间。
一个复杂问题的解决往往由多部分构成,即,一个大的解决方案可以看作是由若干个小的决策组成。
很多时候它们构成一个决策序列。
解决一个问题的所有可能的决策序列构成该问题的解空间。
解空间中满足约束条件的决策序列称为可行解。
一般说来,解任何问题都有一个目标,在约束条件下使目标达优的可行解称为该问题的最优解。
在解空间中,前k项决策已经确定的所有决策序列之集称为k定子解空间。
0定子解空间即是该问题的解空间。
例1.旅行商问题:
某售货员要到若干个城市去推销商品。
已知各个城市之间的路程(或旅费)。
他要选定一条从驻地出发,经过每个城市一遍,最后回到驻地的路线,使得总的路程(或总旅费)最小。
我们用一个带权图G(V,E)来表示,顶点代表城市,边表示城市之间的道路。
图中各边所带的权即是城市间的路程(或城市间的旅费)。
则旅行商问题即是:
在带权图G中找到一条路程最短的周游路线,即
权值之和最小的Hamilton圈。
如果假定城市A是驻地。
则推销员从A地出发,第一站有3种选择:
城市B、C或城市D;第一站选定后,第二站有两种选择:
如第一站选定B,则第二站只能选C、D两者之一。
当第一、第二两站都选定时,第三站只有一种选择:
比如,当第一、第二两站先后选择了B和C时,第三站只能选择D。
最后推销员由城市D返回驻地A。
推销员所有可能的周游路线可由下面的图反映出来。
例2.定和子集问题:
已知一个正实数的集合
和正实数M.试求A的所有子集S,使得S中的数之和等于M。
这个问题的解可以表示成0/1数组
,依据
是否属于S,
分别取值1或0。
故解空间中共有2n个元素。
它的树结构是一棵完全二叉树。
例3.4皇后问题:
在4×4棋盘上放置4个皇后,要使得每两个之间都不能互相攻击,即任意两个皇后都不能放在同一行、同一列及同一对角线上。
将4个皇后分别给以1到4的编号,这个问题的解决就是要安排4个皇后的位置。
因而,每个决策序列由4个决策组成:
P1,P2,P3,P4,这里Pk代表安排第k个皇后的位置,因而有16种可能。
该问题的解空间有164个决策序列。
这时的约束条件是:
任意两个皇后均不能位于同一行、同一列及同一个对角线上。
注意到这个解空间比较大,从中搜索可行解较为困难。
现在把约束条件中的“任意两个皇后均不在同一行”也放在问题中考虑,即:
将4个皇后放在4×4棋盘的不同行上,使得每两个皇后均不能位于同一列、同一对角线上。
则解空间中共有44个决策序列,因为此时可以假定第k个皇后处于第k行上。
此时的约束条件为:
任意两个皇后均不能位于同一列及同一个对角线上。
事实上,我们还可以用另一种方法描述,使得解空间进一步缩小。
将问题陈述为:
将4个皇后放在4×4棋盘的不同行、不同列上,使得任意两个皇后均不能处在同一对角线上。
这时的解空间应当由4!
个决策序列构成。
因为此时每个决策序列实际上对应于{1,2,3,4}的一个排列。
我们可以用树来描述解空间。
从例3来看,解空间的确定与我们对问题的描述有关。
如何组织解空间的结构会直接影响对问题的求解效率。
这是因为回溯方法的基本思想是通过搜索解空间来找到问题的可行解以至最优解。
当所给的问题是从n个元素的集合S中找出满足某种性质的子集时,相应的解空间树称为子集合树。
此时,解空间有
个元素,遍历子集树的任何算法均需
的计算时间。
如例2。
当所给的问题是确定n个元素的满足某种性质的排列时,相应的解空间树称为排列树,此时,解空间有
个元素。
遍历排列树的任何算法均需
计算时间,如例1和例3。
本章只讨论具有上两类解空间树的求解问题。
确定了解空间的组织结构后,回溯法就从开始顶点(解空间树的根顶点)出发,以深度优先的方式搜索整个解空间。
这个开始顶点就成为一个活顶点,同时也成为当前的扩展顶点。
在当前的扩展顶点处,搜索向纵深方向移至一个新顶点。
这个新顶点就成为一个新的活顶点,并且成为当前的扩展顶点。
如果在当前的扩展顶点处不能再向纵深方向移动,则当前的扩展顶点就成为死顶点。
此时应往回移动(回溯)至最近一个活顶点处,并使这个活顶点成为当前扩展顶点。
回溯法即以这种工作方式递归地在解空间中搜索,直至找到要求的解或解空间中已无活结点时为止。
事实上,当我们将问题的有关数据以一定的方式存储好以后(例如,旅行商问题存储赋权图的邻接矩阵、定和子集问题是存储已知的n+1个数、4皇后问题用整数对(i,j)表示棋盘上各个位置),不必先建立一个解空间树,然后再搜索该树寻找所需要的解。
回溯法实际上在搜索的同时逐步生成解空间树(实际只需要一部分)。
也就是说,对于实际问题我们不必要搜索整个解空间。
为了使搜索更加有效,我们常常在搜索过程中加一些判断以决定搜索是否该终止或改变路线。
通常采用两种策略来避免无效的搜索,提高回溯法的搜索效率。
其一是使用约束函数在扩展顶点处剪去不满足约束的子树;其二是用限界函数(后面将阐述)剪去不能得到最优解的子树。
这两种函数统称为剪枝函数。
运用回溯法解题通常包括以下三个步骤:
1).针对所给问题,定义问题的解空间;
2).确定易于搜索的解空间结构;
3).以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效的搜索。
§2.定和子集问题和0/1背包问题
定和子集问题可以描述成下列的数学问题:
确定所有向量
满足:
(7.2.1)
如果让
表示第i件物品的重量,M代表背包的容量,则0/1背包问题可以描述为:
确定一个向量
满足
(7.2.2)
这是一个优化问题,与定和子集问题比较,它多出优化函数,但只要求确定一个最优解,定和子集问题要求确定所有可行解。
1.定和子集问题
用回溯法求解定和子集问题的过程也即是生成解空间树的一棵子树的过程,因为,在搜索期间将剪掉不能产生可行解的子树(即不再对这样的子树进行搜索)。
按照前面关于回溯算法的基本思想的说明,搜索是采用深度优先的路线,算法只记录当前路径。
假设当前扩展顶点是当前路径的k级,也就是说当前路径上,
已经确定,算法要决定下一步搜索目标。
此时,有两种情况:
与
前一种情况说明当前路径已经建立一个可行解,当前扩展顶点即是一个答案顶点。
此时,应该记录已经获得的解(后面的变量取0),停止对该路径的继续搜索,返回到前面最近活结点。
后一种情况出现,算法需要判断是否需要继续向前搜索。
显然,只有当
时才有必要继续向前搜索。
如果集合
中的元素是按不降的次序排列的,则上述继续搜索的条件还可以加强为
(7.2.3)
上述不等式记做Bk。
程序7-2-1定和子集问题的回溯算法伪代码
SumSubset(s,k,r)//寻找W[1:
n]中元素和为M的所有子集。
W[1:
n]中元素按不降次序排列,进入此过程时,X[1],...,X[k-1]的值已经确定。
记
,
假定W[1]M,
1globalintegerM,n;globalrealW[1:
n];
2globalbooleanX[1:
n];
3realr,s;integerk,j;
//由于Bk-1=true,因此s+W[k]M
4X[k]=1;//生成左儿子。
5ifs+W[k]=Mthen
print(X[j],jfrom1tok);
6else
7ifs+W[k]+W[k+1]Mthen
8SumSubset(s+W[k],k+1,r-W[k]);
9endif
10endif
11ifs+r–W[k]Mands+W[k+1]Mthen
12X[k]=0;//生成右儿子
13SumSubset(s,k+1,r-W[k]);
14endif
15endSumSubset
因为假定W[1]M,
,所以程序开始执行时,B0=true。
同样,程序在递归执行过程中,总是以前提条件Bk-1=true开始处理第k级顶点的儿子们的生成过程,由第3~10语句完成,并在此过程中决定是否转到生成下一级顶点的儿子的生成过程,由11~14语句完成。
语句11是一个判断条件,如果这个条件不能满足,则没有必要生成k级顶点的右儿子。
而在左儿子被生成后,语句4和语句7决定是否沿着这个左儿子继续搜索。
所以该算法所生成的子树的叶顶点或是某个左儿子,此时找到一个可行解;或者是某个右儿子,此时由根顶点到该顶点的路径不能延伸为可行解。
例子:
n=6,M=30;W[1:
6]=(5,10,12,13,15,18).由算法SumSubset所生成的解空间树的子树参看文档SumSubset树。
2.0/1背包问题
0/1背包问题是一个优化问题,因此不仅可以使用约束函数,而且可以使用限界函数做剪枝函数.如果当前背包中的物品总重量是cw,前面k-1件物品都已经决定好是否放入包中,那么第k件物品是否放入包中取决于不等式cw+wkM是否满足.这即是搜索的约束函数.另外,我们可以如下确定限界函数.回忆背包问题的贪心算法,当物品按照
的规则排序时,最优解是
的形式,其中,
.设当前背包中物品的总效益值cp,如下方式确定限界函数:
程序7-2-2构造限界函数
BoundF(cp,cw,k,M)//返回效益值的当前限界
gloaln,p[1:
n],w[1:
n];
integerk,i;realb,c,cp,cw,M;
b=cp;c=cw;
forifromk+1tondo
c=c+w[i];
ifc elsereturnb+(1-(c-M)/w[i])*p[i]; endif endfor return(b); endBoundF 这样确定的限界函数表明,从当前确定的k-1定子解空间中寻求到的可行解所能达到的效益值以当前限界函数的值为上界.所以,如果搜索最优解的算法在此之前已经知道大于这个限界值的效益,则没有必要在当前确定的k-1定子解空间中搜索.据此我们给出0/1背包问题的回溯算法. 程序7-2-30/1背包问题的回溯算法 BackKnap(M,n,W,P,fw,fp,X)//M是背包容量.n件物品,数W[1: n]和P[1: n]分//别表示重量和价值,并按单位价值的不增顺序排列下标。 fw是背包的最后//重量,fp是背包的最大效益.X[1: n]中每个元素取0或1值.若物品k未放 //入背包,则X[k]=0;否则,X[k]=1. 1integern,k,Y[1: n],I,X[1: n]; 2realM,W[1: n],P[1: n],fw,fp,cw,cp; 3cw=0;cp=0;k=1;fp=-1; 4loop 5whilekn&&cw+W[k]Mdo//使用约束函数 6cw=cw+W[k];cp=cp+P[k];Y[k]=1;k=k+1; 7endwhile 8ifk>nthen 9fp=cp;fw=cw;k=n;X=Y;//修改解 10elseY[k]=0; 11endif 12whileBoundF(cp,cw,k,M)fpdo 13whilek0&&Y[k]1do 14k=k-1; 15endwhile 16ifk=0thenreturnendif 17Y[k]=0;cw=cw-W[k];cp=cp-P[k]; 18endwhile 19k=k+1; 20endloop 21endBackKnap 例子 算法采用一个大的循环搜索各条可能的路径.当一条路径的搜索到某一步不能继续往下搜索时,此时或是因为约束函数不满足,或是因为限界函数不满足.它们分别在语句5~7的子循环和语句12~18的子循环中达到.这是程序的两个主要部分,其余主要是处理边界条件,如k>n的验证等.第一种情况出现时,语句8~11给出部分处理,剩下的事情交给语句12~19来处理.这里给出了搜索退回的方案.下面的也许能够帮助理解本算法. §3.n-皇后问题和旅行商问题 在第一节已经给出了这两个问题的解空间.如果用 表示解,则它是自然数 的一个排列.对于旅行商问题,我们可以假定 表示售货员的驻地是城市1.采用回溯法,对于旅行商问题主要是给出限界函数,而对于n皇后问题,主要任务是给出约束函数。 此时我们可以假定带权图是完全图,这只要将实际不相邻的两个顶点间用带有权+ 的边连接即可. 1.n-皇后问题 这里的约束条件是: 任何两个皇后都不能位于同一对角线上.如果我们用 表示棋盘上第i行与第j列交叉的位置.则在同一条平行于主对角线的对角线上的两点 和 满足关系式 ;而处于同一条平行于副对角线的对角线上的两点 和 则满足关系式 .将这两个关系式略作变形即得两种情况的统一表示: (7.3.1) 反之,如果棋盘上的两点 和 满足关系式(7.3.1),则它们一定位于同一条对角线上.所以,如果 是n皇后问题的一个可行解,则对任何 等式 (7.3.2) 均不得成立.这即是约束条件.如果假定前面的k-1个皇后位置已经排好,现在要安排第k个皇后的位置,必须使得 而且等式(7.3.2)不成立, .算法可以这样设计: 对于 所有可能的取值,验证上述条件.对于每个取值 验证它是否满足上述两个条件,用一个boolean函数Place来完成. 程序7-3-1皇后问题放置函数 Place(k)//如果第k个皇后能放在第X[k]列,则返回true,否则返 //回false.X是一个全程数组,进入此过程时已经设置了k个值 globalX[1: k];integeri,k; i=1; whilei ifX[i]=X[k]or|X[i]-X[k]|=|i-k|then return(false); endif i=i+1; endwhile return(true); endPlace 使用函数Place能使求n-皇后问题的回溯算法具有简单的形式 程序7-3-2求n-皇后问题可行解的回溯算法 nQueens(n) integerk,n,X[1: n]; X[1]=0;k=1;//k是当前行,X[k]是当前列 whilek>0do X[k]=X[k]+1;//转到下一列 whileX[k]n&&Place(k)=falsedo X[k]=X[k]+1; endwhile ifX[k]nthen ifk=nthen Print(X); elsek=k+1;X[k]=0;//转到下一行 endif elsek=k-1;//回溯 endif endwhile endnQueens 程序nQueens处理4-皇后问题的执行过程参看文档”4-皇后结构树”. 2.旅行商问题 用1,2,…,n代表n个顶点,一个周游 用数组 表示,它是旅行商问题的一个可行解.如果可行解的前k-1个分量 已经确定,则判定 能否形成一条路径,只需做k-1次比较: (7.3.3) 此即构成旅行商问题的约束条件.用w(i,j)记边(i,j)的权值.cl记当前路径 的长度,即 .如果当前知道的最短周游的线路长度为 则当 (7.3.4) 时, 不会是最短周游路线的一部分,在解空间树中,相应的一枝被剪掉,(7.3.4)即是旅行商问题的限界条件.此外,当 时,若 (7.3.5) 则算法需要更新 令 (7.3.6) 程序7-3-3旅行商问题的约束条件函数 NextValue(k)//从顶点1出发的路径,如果第k个顶点是顶点X[k],则返回//true,否则返回false.X是一个全程数组,进入此过程时已经设置了k //个值,其中X[1]=1,X[k]是当前扩展顶点。 globalX[1: k];integeri,k; i=1; whilei ifX[i]=X[k]then return(false); endif i=i+1; endwhile return(true); endNextValue 使用函数NextValue能使求旅行商问题的回溯算法具有简单的形式 程序7-3-4求旅行商问题的回溯算法 BackTSP(n,W)//求图G的从顶点1出发的最短周游(Hamilton圈)路线。 W //是G的邻接矩阵。 X[k]是当前路径的第k个顶点,c是当前路径的长度,fl //是当前所知道的最短的周游(Hamilton圈)的长度 integerk,n,X[1: n]; realW[1: n,1: n],cl,fl; X[2]=1;k=2;cl=0;fl=+; whilek>1do X[k]=(X[k]+1)modn;//给X[k]预分配一个值 forjfrom1tondo ifNextValue(k)=truethenexit;endif X[k]=(X[k]+1)modn; endfor if[flcl+W[k-1,k]]or[k=nandfl +W[X[n],1]]thenk=k-1;//回溯 elifk=n&&flcl+W[k-1,k]+W[X[k],1]then fl=cl+W[k-1,k]+W[X[k],1];k=k-1;//回溯 elsecl=cl+W[k-1,k];k=k+1;//继续纵深搜索 endif endwhile endBackTSP 旅行商问题的例子 §4图的着色问题 已知一个无向图G和m种颜色,在只准使用这m种颜色对图G的顶点进行着色的情况下,是否有一种着色方法,使图中任何两个相邻的顶点都具有不同的颜色? 如果存在这样的着色方法,则说图G是m-可着色的,这样的着色称为图G的一种m-着色。 使得G是m-可着色的最小数m称为图G的色数。 这一节所讨论的图的着色问题是: 给定无向图G和m种颜色,求出G的所有m-着色。 用G的邻接矩阵W表示图G,W[i,j]=1表示顶点i与j相邻(有边相连),否则W[i,j]=0.m种颜色分别用1,2,…,m表示。 图G的每一种m-着色都可以用一个n-维数组X[1: n]表示。 X[i]=k表示顶点i被着上颜色k。 简单分析可知,解空间是一个完全的m-叉树,共有n+1级。 X是可行解,当且仅当 W[i,j]=1X[i]X[j],(7.4.1) 此即是约束条件。 假如已经给前j-1个顶点着好颜色,即X[1],…,X[j-1]已经确定,则确定第j个顶点所着的颜色X[j]时,根据约束条件,应该验证条件 W[i,j]=1X[i]X[j],1i 是否满足。 这可以由下面程序完成。 程序7-4-1下一步选颜色算法 NextColor(j)//进入此过程前,X[1],…,X[j-1]已经确定且满足约束条件。 //本过程给X[j]确定一个整数k,0km: 如果还有一种颜色k可以分配//给顶点j(满足约束条件),则令X[j]=k;否则,令X[j]=0。 globalintegerm,n,X[1: n],W[1: n,1: n]; integerj,k; loop X[j]=(X[j]+1)mod(m+1); ifX[j]=0thenreturnendif forifrom1toj-1do//验证约束条件 ifW[i,j]=1&&X[i]=X[j]thenexitendif endfor ifi=jthenreturnendif//找到一种颜色 endloop endNextColor 在程序NextColor开始执行之前,诸X[k]均已经有值。 这可在着色问题的回溯算法初次调用该函数时赋予初值: X[i]=0,i=1,2,…,n。 程序7-4-2图的着色问题回溯算法 GraphColor(k)//采用递归。 W[1: n,1: n]是图G的邻接矩阵,1,2, //…,m代表m种颜色。 k是下一个要着色的顶点。 globalintegerm,n,X[1: n],W[1: n,1: n]; loop NextColor(k);//确定X[k]的取值 ifX[k]=0thenexitendif//说明没有颜色可以分配给第k个点 ifk=nthen//已经找到一种着色方法 print(X); elseGraphColor(k+1);//递归 endif endloop endGraphColor 例子: n=4,m=3, 无向图G如右图G x1=123 x2=231312 x3=131223122313 x4=232233131313112212 一个4顶点的图和所有可能的3着色 正好用3种颜色的解只有12个。 §5.回溯法的效率分析 回溯法是以深度优先的方式系统地搜索问题的解空间。 解空间是由所有可能的决策序列 构成。 在搜索过程中,采用剪枝函数尽量避免无意义的搜索。 通过前面的具体实例的讨论容易看出,一个回溯算法的效率在很大程度上依赖于以下几个因素: 1).产生 的时间; 2). 的取值范围; 3).计算约束函数的时间和计算限界函数的时间;; 4).满足约条件及限界条件的 的个数。 一般来说,一个好的约束函数能够显著地减少所生成的顶点的数目。 但是,这样的约束函数往往计算量较大。 因此在选择约束函数时通常存在着顶点数与约束函数计算量之间的折中。 我们希望总的计算时间较少。 为了提高效率,通常采用所谓的“重排原理”。 对于许多问题而言,在进行搜索试探时,选取 值的顺序是任意的。 这提示我们,在其它条件相同的前提下,如果让取值最少的 优先。 则将会使算法更有效。 如文档“解空间树比较”中的图,是同一个问题的不同的解空间树,从中可以体会到这种策略的效力。 在第一个图中,若从第1级剪去一棵子树,则从所有应当考虑三元组中一次消去12个三元组;在第二个图中,虽然同样从第1级剪去一棵子树,却只从应当考虑的三元组中一次消去8个三元组。 前者的效果显然比后者好。 解空间的结构一经选定,影响回溯法效率的前三个因素就可以确定,只剩下生成顶点的数目是可变的,它将随问题的具体内容以及拟定的不同生成方式而变动。 即使是对于同一问题的不同实例,回溯法所产生的顶点的数目也会有很大变化。 对于一个实例,回溯法可能只产生 个顶点。 而对于另一个相近的实例,回溯法可能产生解空间中的所有顶点。 如果解空间的顶点数是 或 ,则在最坏情况下,回溯法的时间耗费一般为 或 。 其中, 和 均为 的多项式。 对于一个具体问题来说,回溯法的有效性往往就体现在当问题实例的规模
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法设计与分析 第七章回溯法 算法 设计 分析 第七 章回