《算法设计与分析》第8章1 回溯

第八章回溯法8.1一般方法8.2n-皇后问题8.3子集和数问题8.4图的着色问题8.5哈密顿环8.60/1背包问题8.7批处理作业调度什么是回溯回溯回溯入口出口回溯迷宫游戏什么是回溯法回溯法是一个既带有系统性又带有跳跃性的的搜索算法回溯法是以深度优先的方式系统地搜索问题的解,它适用于解一些组合数较大的问题。回溯为什么回溯？回溯(Trackback)是什么？怎样回溯？WhatWhyHow应用回溯法解问题时,首先应该明确问题的解空间一个复杂问题的解决方案可以看作是由若干个小的决策组成的,这些决策构成一个决策序列。解决一个问题的所有可能的决策序列就构成了该问题的解空间。解空间中满足约束条件的决策序列称为可行解。在约束条件下使目标达到最优的可行解称为该问题的最优解。通常将解空间画成树的形状,称为解空间树回溯法的基本概念回溯算法求解问题的类型同贪心算法和动态规划算法求解的问题类型相似，问题的解可以表示成一个n维向量，一般地，每个分量有两个或有限多个取值，而且它的取值要满足某个事先给定的约束条件。所有可能的取值的组合构成问题的解向量空间，简称解空间。由于一个解向量往往对应问题的某个状态，所以解空间又称为问题的状态空间。一般情况下，问题的解仅是问题解空间的一个子集，要求此子集对应的解必须满足问题的约束条件，满足约束条件的一组取值称为问题的一个可行解，使目标函数取最大或最小值的可行解称为最优解。回溯法在求问题的所有解时,要回溯到根结点,且根结点的所有子树都已被搜索过才结束。回溯法在求问题的任一解时,只要搜索到问题的一个解就可以结束。回溯法在包含问题所有解的解空间树中,按深度优先的策略,从根结点出发搜索解空间树。回溯法搜索至解空间树的任一结点时,先判断该结点是否肯定不包含问题的解。如果肯定不包含,则跳过以该结点为根的子树,逐层向其祖先结点回溯。否则就进入该子树,继续按深度优先的策略进行搜索。回溯法的基本概念问题的解可以用一个n元组(x1,…,xn)来表示，其中的xi取自于某个有穷集Si,并且这些解必须使得某一限界函数B(x1,…,xn)取极值。不断地用修改过的限界函数Bi(x1,…,xn)去测试正在构造的n元组的部分向量,看是否可能导致最优解,如果不能,就将可能要测试的mi+1…mn个向量略去。回溯法的解需要满足一组综合的约束条件,通常分为:显式约束和隐式约束显式约束条件:限定每个x只从一个给定的集合上取值,满足显式约束的所有元组确定一个可能的解空间例:xi=0,si={所有非负实数}隐式约束条件:描述了xi必须彼此相关的情况回溯法的基本概念回溯法的基本思想通过部分解向量逐步增加可行分量来求出解向量。对于一个解向量，假设已经构造得到问题的部分解向量(x1,x2,…,xk)，在部分解向量的基础上，考虑第k+1个分量xk+1的一个取值，可能遇到下面的两种情况：(1)部分解向量加入xk+1仍满足约束条件，那么以为基础继续添加新的分量；121(,,,,)kkxxxx(2)否则，那么就要考察xk+1的另外一个取值，如果对xk+1的所有取值，都不满足约束条件，那么就回溯到xk，即选取xk的另一个取值，同上考察部分解向量。kx12(,,,)kxxx从k=1开始，逐步扩展部分解(x1,x2,…,xk)，就是回溯求解的过程。如何表示解空间？树结构已有成熟的搜索算法，因此可以利用树结构表示问题的解空间。例:4-皇后问题在一个4*4棋盘上放4个皇后,使每两个皇后之间都不能互相“攻击”,即使得每两个皇后都不能在同一行、同一列及同一条斜线上。4皇后问题可以表示为4-元组(x1,…,x4)，其中xi是放置皇后i所在的列号。显式约束条件:si={1,2,3,4},1≤i≤4隐式约束条件:没有两个xi可以相同,且没有两个皇后可以在同一条斜线上Q1Q2Q3Q4145674334101112942421415161732322021222343432526272841143031323331133813341924291342183450342………4-皇后问题的解空间树x1=1x2=2问题描述:已知n+1个正数:wi(1≤i≤n)和M,要求找出wi的和数是M的所有子集。例:n=4,(w1,w2,w3,w4)=(11,13,24,7),M=31满足要求的子集是(11,13,7)和(24,7)用wi的下标来表示解向量更为方便,因此这两个解向量可以表示为:(1,2,4)和(3,4)显式约束条件:xi∈{j|j是wi的下标值,1≤j≤n}隐式约束条件:要求没有两个xi是相同的,且相应的wi的和数等于M为避免产生同一个子集的重复情况(如(1,2,4)和(1,4,2)),附加一个隐式约束条件:xi≤xi+1,1≤j≤n例:子集和数问题12345678910111213141516x2=2x2=3x2=4x2=3x2=4x2=4x1=1x1=2x1=3x1=4x3=3x3=4x3=4x3=4x4=4子集和数问题的解空间树1解空间树中的路径对应一个向量根结点到自身的空路径对应一个空向量()树中红色的路径分别对应向量:(4)(1,2,4)(2,3,4)子集和问题可变长度解空间树一个问题的解可以有多种表示形式,而这些表示形式都使得所有的解是满足某些约束条件的多元组子集和数问题的另一种列式表示:每一个解的子集由一个大小固定的n-元组(x1,…,xn)所表示,它使得xi∈{0,1},1≤i≤n;如果选择wi,则xi=1;否则xi=0解向量(1,2,4)和(3,4)可表示为(1,1,0,1)和(0,0,1,1)例:子集和数问题17123456789101112131415161820232425192122262728293031x1=1x1=0x2=1x3=1101010x2=0x3=0x3=1x3=0x2=1x2=0x3=1x3=0x3=1x3=01010101010子集和数问题的解空间树2注:结点按D-检索方式编号从根结点到叶结点的一条路径确定解空间中的一个元组树中红色路径表示元组(1,1,0,1)子集和问题固定长度解空间树解空间树(状态空间树)的术语问题状态(problemstate):树中的每一个结点确定所求解问题的一个问题状态状态空间(statespace):由根结点到其他结点的所有路径确定了这个问题的状态空间解状态(solutionstates):是这样一些问题状态S,对于这些问题状态,由根到S的那条路径确定了这个解空间中的一个元组答案状态(answerstates):是这样的一些解状态S,对于这些解状态而言,由根到S的这条路径确定了这问题的一个解静态树(statictrees):树结构与所要解决问题的实例无关动态树(dynamictrees):树结构是与实例相关的,且树结构是动态确定的活结点:自己已经生成而其所有的儿子结点还没有全部生成的结点E-结点(正在扩展的结点):当前正在生成其儿子结点的活结点死结点:不再进一步扩展或者其儿子结点已全部生成的生成结点解空间树(状态空间树)的术语在搜索过程中，如果搜索到一个活结点，则将该活结点转化为扩展结点，并继续搜索该结点的子结点；如果搜索到一个死结点，且还没有得到问题的解，则向上回溯到它的父结点，如果其父结点当前还是扩展结点，继续搜索其父结点的其它子结点；如果其父结点随着其子结点搜索完毕而变成死结点，则此时需要进一步向上回溯到其祖父结点。以上过程继续进行，直到得到问题的解，或者最后解空间树的根结点也成为死结点，此时回溯搜索结束。问题状态的生成第一种状态生成方法:当前的E-结点R一旦生成一个新的儿子结点C,这个C结点就变成一个新的E-结点,当检测完了子树C后,R结点就再次成为E-结点,生成下一个儿子结点。(该方法也称为深度优先结点生成法)第二种状态生成方法:一个E-结点一直保持到变成死结点为止。它又分为两种方法:宽度优先生成方法(队列方法)和D-检索方法(栈方法)第一种状态生成方法对应回溯法第二种状态生成方法对应分支-限界法（Ch9）结点2变成E-结点,它再生成结点3,路径变为(1,2),即皇后1在第1列上,皇后2在第2列上,所以结点3被杀死,此时应回溯13x2=22x1=1开始把根结点作为唯一的活结点,根结点就成为E-结点而且路径为();接着生成儿子结点,假定按自然数递增的次序来生成儿子,那么结点2被生成,这条路径为(1),即把皇后1放在第1列上kill112例:4-皇后问题8x2=3回溯到结点2生成结点8,路径变为(1,3),则结点8成为E-结点,它生成结点9和结点11都会被杀死(即它的儿子表示不可能导致答案的棋盘格局),所以结点8也被杀死,应回溯13x2=22x1=1kill11x3=49x3=2112123killkill例:4-皇后问题12313x2=415x4=3回溯到结点2生成结点13,路径变为(1,4),结点13成为E-结点,由于它的儿子表示的是一些不可能导致答案结点的棋盘格局,因此结点13也被杀死,应回溯8x2=313x2=22x1=1kill11x3=49x3=2killkill14x3=2kill112123412316x3=3kill例:4-皇后问题18x1=213x2=415x4=313x2=22x1=1kill11x3=49x3=2killkill8x2=314x3=2kill16x3=3kill结点2的所有儿子表示的都是不可能导致答案的棋盘格局,因此结点2也被杀死;再回溯到结点1生成结点18,路径变为(2)19x2=124x2=3killkill结点18的儿子结点19、结点24被杀死,应回溯11212例:4-皇后问题131x4=3结点18生成结点29,结点29成为E-结点,路径变为(2,4);18x1=213x2=415x4=313x2=22x1=1kill11x3=49x3=2killkill8x2=314x3=2kill16x3=3kill19x2=124x2=3killkill121231234结点29生成结点30,路径变为(2,4,1)结点30生成结点31,路径变为(2,4,1,3),找到一个4-皇后问题的可行解29x2=430x3=1可行解搜索树1、针对所给问题定义问题的解空间,解空间应至少包含问题的一个最优解2、确定易于搜索的解空间结构3、以深度优先方式搜索解空间,并在搜索过程中使用限界函数避免无效搜索回溯算法的三个步骤从根结点出发,以深度优先方式搜索整个解空间。首先根结点成为一个活结点,同时也成为当前的扩展结点。在当前扩展结点处,搜索向纵深方向移至一个新结点,该新结点成为一个新的活结点,并成为当前扩展结点。如果在当前扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。此时应回溯至最近的一个活结点处,并使该活结点成为当前的扩展结点。回溯法以这种方式递归地在解空间中搜索,直至找到所要求的解或解空间中已没有活结点时为止。回溯法搜索过程回溯算法的形式化描述假设回溯法要找出所有的答案结点设(x1,x2,…,xi-1)是状态空间树中由根到一个结点的路径，而T(x1,…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如果要求问题的最优解，除了约束条件外，我们还要考虑目标函数的界的满足问题。若问题最优解是使目标函数取最小值的可行解，当前目标函数的最小值为bound，扩展部分解(x1,x2,…,xi)时，需要考虑(x1,x2,…,xi)对应目标函数的取值是否已经大于bound，如果已经大于，则停止在部分解(x1,x2,…,xi)上的扩展，否则可以在部分解