算法分析与设计回溯法ppt课件.ppt
《算法分析与设计回溯法ppt课件.ppt》由会员分享,可在线阅读,更多相关《算法分析与设计回溯法ppt课件.ppt(66页珍藏版)》请在三一办公上搜索。
1、第六章 回溯法,什么是回溯法,例:迷宫游戏,可用回溯法求解的问题,问题的解可以用一个n元组(x1,xn)来表示,其中的xi取自于某个有穷集Si,并且这些解必须使得某一规范函数P(x1,xn)(也称限界函数)取极值或满足该规范函数条件。例子:A(1:n)个元素的分类问题问题的解为n元组;xi取自有穷集;规范函数P:A(xi)A(xi+1),问题求解的方法,硬性处理法列出所有候选解,逐个检查是否为所需要的解理论上,候选解数量有限,并且通过检查所有或部分候选解能够得到所需解时,上述方法可行实际中则很少使用,因为候选解的数量通常都非常大(比如指数级,甚至是大数阶乘),即便采用最快的计算机也只能解决规模
2、较小的问题。回溯或分枝限界法避免对很大的候选解集合进行完全检查大大减少问题的求解时间通常用来求解规模较大的问题,回溯法概述,回溯法可以系统的搜索一个问题的所有解或任一个解它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。算法搜索到某一结点时,如果断定该结点肯定不包含问题的解,则跳过以该结点为根的子树的搜索,逐层向其祖先结点回溯这种以深度优先方式搜索问题的解的方法称为回溯法,回溯法思想,第一步:为问题定义一个状态空间(state space)。这个空间必须至少包含问题的一个解第二步:组织状态空间以便它能被容易地搜索。典型的组织方法是图或树第三步:按深度优先的方法从开
3、始结点进行搜索 开始结点是一个活结点(也是 E-结点:expansion node)如果能从当前的E-结点移动到一个新结点,那么这个新结点将变成一个活结点和新的E-结点,旧的E-结点仍是一个活结点。如果不能移到一个新结点,当前的E-结点就“死”了(即不再是一个活结点),那么便只能返回到最近被考察的活结点(回溯),这个活结点变成了新的E-结点。当我们已经找到了答案或者回溯尽了所有的活结点时,搜索过程结束。,回溯法如何提高效率?,由开始结点到当前E-结点构成解向量(x1,xi);其中的xi取自于某个有穷集Si,假设集合Si的大小是mi。如果判定(x1,xi)不能导致最优解,那么就将可能要测试的mi
4、+1mn个向量略去。因此回溯法的测试次数比硬性处理作的测试次数要少得多。如何判定(x1,xi)能否导致最优解?,约束条件,回溯法的解需要满足一组综合的约束条件,通常分为:显式约束和隐式约束显式约束条件限定每个xi只从一个给定的集合上取值,例如:Xi0 即si=所有非负实数xi=0或xi=1 即 si=0,1lxiu即si=a:lau满足显式约束的所有元组确定一个可能的解空间隐式约束描述了xi必须彼此相关的情况,如0/1背包问题中的背包重量M,回溯法求解的经典问题(1)8-皇后问题,在一个8*8棋盘上放置8个皇后,且使得每两个之间都不能互相“攻击”,也就是使得每两个都不能在同一行、同一列及同一条
5、斜角线上。8皇后问题的解可以表示为8-元组(x1,x8),其中其中xi是第i行皇后所在的列号。显式约束条件是si=1,2,3,4,5,6,7,8,1i8隐式约束条件是,没有两个xi可以相同且没有两个皇后可以在同一条斜角线上。,1 2 3 4 5 6 7 8,12345678,由于解向量之间不能相同,所以解空间的大小由88个元组减少到8!个元组。上图中的解表示为一个8-元组即(4,6,8,2,7,1,3,5)。,回溯法求解的经典问题(2)子集和数问题,已知(w1,w2,wn)和M,均为正数。要求找出wi的和数等于M的所有子集。例如:若n=4,(w1,w2,w3,w4)=(11,13,24,7),
6、M=31,则满足要求的子集是(11,13,7)和(24,7).子集和数问题解的一种表示方法若用Wi的下标表示解向量,这两个解向量为(1,2,4)和(3,4)。子集和数问题的解可以表示为k-元组(x1,x2,xk),1kn并且不同的解可以是大小不同的元组。显式约束条件是xi j|j为整数且1jn。隐式约束条件是1)没有两个xi是相同的;2)wxi的和为M;3)xixi1,1in(避免产生同一个子集的重复情况),子集和数问题解的另一种表达,解由n-元组(x1,x2,xn)表示显式约束条件xi0,1,1in,如果没有选择Wi,则xi=0;如果选择了Wi,则xi=1。于是上面的解可以表示为(1,1,0
7、,1)和(0,0,1,1)隐式约束条件(xi wi)的和数为M解空间的大小为2n个元组,解空间的树结构,回溯算法通过系统地检索给定问题的解空间来确定问题的解。这检索可以用这个解空间的树结构来简化。为了便于讨论,引进一些关于解空间树结构的术语。问题状态(problem state):树中的每一个结点确定所求解问题的一个问题状态。状态空间(state space):由根结点到其它节点的所有路径则确定了这个问题的状态空间。解状态(solution states):解状态是这样一些问题状态S,对于这些问题状态,由根到S的那条路径确定了这解空间中的一个元组。答案状态(answer states):对于这
8、些解状态而言,由根到S的这条路径确定了这问题的一个解(即,它满足隐式约束条件)。状态空间树(state space tree):解空间的树结构。,组织解空间(1),4-皇后问题解空间的树结构(解空间由从根结点到叶结点的所有路径所定义),n-皇后问题的状态空间树?,组织解空间(2),子集和数问题,解空间由树中的根结点到任何结点的所有路径所确定,这些可能的路径是()(这对应于由根结点到他自身的那条路径);(1);(1,2);(1,2,3);(1,2,3,4);(1,2,4);(1,3,4);(1,4);(2);(2,3)等等,组织解空间(3),子集和数问题,解空间由根结点到叶结点的所有路径确定,状
9、态空间树,对于任何一个问题,一旦设想出一种状态空间树,那么就可以先系统地生成问题状态,接着确定这些问题状态中的哪些是解状态,最后确定哪些解状态是答案状态从而将问题解出生成问题状态的两种方法 便于问题的描述,给出以下概念:活结点:自己已经生成而其所有的儿子结点还没有全部生成的结点。E-结点(正在扩展的结点):当前正在生成其儿子结点的活结点。死结点:不再进一步扩展或者其儿子结点已全部生成的生成结点。,生成问题状态的两种方法,第一种方法:当前的E-结点R一旦生成一个新的儿子C,这个儿子结点就变成一个新的E-结点,当完全检测了子树C之后,R结点就再次成为E-结点。这相当于问题状态的深度优先生成。第二种
10、方法:一个E-结点一直保持到变成死结点为止。在这两种方法中,将用限界函数杀死部分还没有全部生成其儿子结点的那些活结点。回溯法:使用限界函数的深度优先结点生成方法。分枝-限界方法:E-结点一直保持到死为止的状态生成方法。,4-皇后问题-回溯解,1 2 3 4,1234,4-皇后问题回溯期间生成的树,上图显示了在4-皇后问题中求上述一个解的树的实际生成部分。结点按它们生成的次序被编号。由限界函数所杀死的结点则在其下方写上B。,回溯法的算法,算法的三个步骤:针对所给问题,定义问题的解空间;应用回溯法解问题时,首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个(最优)解。确定易于搜索的解空间
11、结构;以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索;,回溯算法的形式描述,假设回溯算法要找出所有的答案结点而不是仅仅只找出一个。设(x1,x2,xi-1)是状态空间树中由根到一个结点(问题状态)的路径。T(x1,x2,xi-1)是下述所有结点的xi的集合,它使得对于每一个xi,(x1,x2,xi)是一条由根到结点xi的路径存在一些限界函数Bi(可以表示成一些谓词),如果路径(x1,x2,xi)不可能延伸到一个答案结点,则Bi(x1,x2,xi)取假值,否则取真值。因此,解向量X(1:n)中的第i个分量就是那些选自集合T(x1,x2,xi-1)且使Bi为真的xi。,回溯的一
12、般方法算法,procedure BACKTRACK(n)integer k,n;local X(1:n)k1 while k0 do if 还剩有没检验过的X(k)使得 X(k)T(X(1),X(k-1)and B(X(1),X(k)=true then if(X(1),X(k)是一条已抵达一答案结点的路径 then print(X(1),X(k)endif k k+1 else k k-1 endif repeatend BACKTRACK,回溯算法的递归表示,procedure RBACKTRACK(k)global n,X(1:n)for 满足下式的每个X(k)X(k)T(X(1),X(
13、k-1)and B(X(1),X(k)=true do if(X(1),X(k)是一条已抵达一答案结点的路径 then print(X(1),X(k)endif call RBACKTRACK(k+1)repeatend RBACKTRACK,算法说明:基本上是一棵树的后根次序周游。这个递归模型最初由call RABCKTRACK(1)调用。,效率分析应考虑的因素,(1)生成下一个X(k)的时间(2)满足显式约束条件的X(k)的数目(3)限界函数Bi的计算时间(4)对于所有的i,满足Bi的X(k)的数目权衡:限界函数生成结点数和限界函数本身所需的计算时间,效率分析,效率分析中应考虑的因素(1)
14、(3)与实例无关(4)与实例相关有可能只生成O(n)个结点,有可能生成几乎全部结点最坏情况时间O(p(n)2n),p(n)为n的多项式O(q(n)n!),q(n)为n的多项式,Monte Carlo效率估计(1),一般思想在状态空间中生成一条随机路径X为该路径上的一个结点,且X在第i级mi为X没受限界的儿子结点数目从mi随机选择一个结点作为下一个结点路径生成的结束条件:1)叶子结点;或者2)所有儿子结点都已被限界所有这些mi可估算出状态空间树中不受限界结点的总数m,Monte Carlo效率估计(2),使用蒙特卡罗方法的假设条件限界函数是固定的,即在算法执行期间当其信息逐渐增加时限界函数不变。
15、同一个函数正好用于这棵状态空间数同一级的所有结点。使用蒙特卡罗方法估算应用举例 设第二级没受限结点数为m1。如果这棵检索数是同一级上结点有相同的度的数,那么就可以预计到每一个2级结点平均有m2个没界限的儿子,从而得出在第3级上有m1m2个结点。第4级预计没受限的结点数是m1m2m3。一般在i+1级上预计的结点数是m1m2mi。于是,在求解给定问题的实例中所要生成的不受限界结点的估计数 m=1+m1+m1m2+m1m2m3+,Monte Carlo效率估计算法,procedure ESTIMATE m1;r 1;k 1 loop TkX(k):X(k)T(X(1),X(k-1)and B(X(1
16、),X(k)if SIZE(Tk)=0 then exit endif rr*SIZE(Tk)mm+r X(k)CHOOSE(Tk)KK+1 repeat return(m)end ESTIMATEESTIMATE是一个确定m值的算法,6.2 8-皇后问题,8-皇后问题实际上很容易一般化为n-皇后问题,即要求找出一个n*n棋盘上放置n个皇后并使其不能互相攻击的所有方案。令(x1,x2,xn)表示一个解,由于没有两个皇后可以放入同一列,因此所有的xi将是互不相同的。那么关键是应如何去测试两个皇后是否在同一条斜角线上呢?,6.2 8-皇后问题,如果用二维数组A(1:n,1:n)的下标来标记每个皇后
17、的位置,那么可以看到,对于在同一条斜角线上的由左上方到右下方的每一个元素有相同的“行-列”值,同样,在同一条斜角线上的由右上方到左下方的每一个元素则有相同的“行+列”值。,6.2 8-皇后问题,假设有两个皇后被放置在(i,j)和(k,l)位置上,那么根据以上所述,仅当i j=k-l 或 i+j=k+l时,它们才在同一条斜角线上。将这两个等式分别变换成 j-l=i-k 或 j-l=k-i因此,当且仅当|j-l|=|i-k|时(即两个皇后所在位置的行差距等于列差距时),两个皇后在同一条斜角线上。,算法6.4:可以放置一个新皇后吗?,Procedure PLACE(k)/如果一个皇后能放在第k行和X
18、(k)列,则返回true,否则返回false。X是一个全程数组,进入此过程时已置入了k个值。ABS(r)过程返回r的绝对值/global X(1:k);integer i,k;i1while ik doif X(i)=X(k)or ABS(X(i)-X(k)=ABS(i-k)thenreturn(false)end ifii+1repeatreturn(true)End PLACE,判断是否有其它的皇后与之在同一列或同一斜对角线上,算法6.5:n-皇后问题的所有解,Procedure NQUEENS(n)/此过程使用回溯法求出一个n*n棋盘上放置n个皇后,使其不能互相攻击的所有可能位置/int
19、eger k,n,X(1:n)X(1)0;k1/k是当前行;X(k)是当前列/while k0 do/对所有的行,执行以下语句/X(k)X(k)+1/移到下一列/while X(k)n and Not PLACE(k)do/此处能放这个皇后吗/X(k)X(k)+1/不能放则转到下一列/repeatif X(k)n then/找到一个位置/if k=n then print(X)/是一个完整的解则打印这个数组/else kk+1;X(k)0/否则转到下一行/end if else kk-1/回溯/end ifrepeatEnd NQUEENS,6.3 子集和数问题,假定有n个不同的正数,要求找出
20、这些数中所有使得某和数为M的组合。前面已经说明了如何用大小固定或变化的元组来表示这个问题。本节将利用大小固定的元组来研究一种回溯解法,解决这一问题。对于i级上的一个结点,其左儿子对应于X(i)=1,右儿子对应于X(i)=0。,6.3 子集和数问题,限界函数当且仅当W(i)X(i)(i=1 to k)+W(i)(i=k+1 to n)M 时,B(X(1),X(2),X(k)=True当W(i)以递增次序排列,则界限函数可强化:若W(i)X(i)(i=1 to k)+W(k+1)M,则X(1),X(2),X(k)就不能导致一个答案结点。因此将要使用的界限函数是:Bk(X(1),X(2),X(k)=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 分析 设计 回溯 ppt 课件
链接地址:https://www.31ppt.com/p-5451728.html