文档介绍：回溯算法原理
第 4 章回溯
寻找问题的解的一种可靠的方法是首先列出所有候选解,然后依次检查每一个,在检查完所有或部分候选解后,即可找到所需要的解。理论上,当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时,上述方法是可行的。不过,在实际应用中,很少使用这种方法,因为候选解的数量通常都非常大(比如指数级,甚至是大数阶乘),即便采用最快的计算机也只能解决规模很小的问题。对候选解进行系统检查的方法有多种,其中回溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少(无论对于最坏情形还是对于一般情形)。事实上,这些方法可以使我们避免对很大的候选解集合进行检查,同时能够保证算法运行结束时可以找到所需要的解。因此,这些方法通常能够用来求解规模很大的问题。
本章集中阐述回溯方法,这种方法被用来设计货箱装船、背包、最大完备子图、旅行商和电路板排列问题的求解算法。
算法思想
回溯(b a c k t r a c k i n g)是一种系统地搜索问题解答的方法。为了实现回溯,首先需要为问题定义一个解空间( solution space),这个空间必须至少包含问题的一个解(可能是最优的)。在迷宫老鼠问题中,我们可以定义一个包含从入口到出口的所有路径的解空间;在具有n 个对象的0 / 1背包问题中(见1 . 4节和2 . 2节),解空间的一个合理选择是2n 个长度为n 的0 / 1向量的集合,这个集合表示了将0或1分配给x的所有可能方法。当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 ) }。
下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。图1 6 - 1用图的形式给出了一个3×3迷宫的解空间。从( 1 , 1 )点到( 3 , 3 )点的每一条路径都定义了3×3迷宫解空间中的一个元素,但由于障碍的设置,有些路径是不可行的。
图1 6 - 2用树形结构给出了含三个对象的0 / 1背包问题的解空间。从i 层节点到i+ 1层节点的一条边上的数字给出了向量x 中第i个分量的值xi ,从根节点到叶节点的每一条路径定义了解空间中的一个元素。从根节点A到叶节点H的路径定义了解x= [ 1 , 1 , 1 ]。根据w 和c 的值,从根到叶的路径中的一些解或全部解可能是不可行的。
一旦定义了解空间的组织方法,这个空间即可按深度优先的方法从开始节点进行搜索。在迷宫老鼠问题中,开始节点为入口节点( 1 , 1 );在0 / 1背包问题中,开始节点为根节点A。开始节点既是一个活节点又是一个E-节点(expansion node)。从E-节点可移动到一个新节点。如果能从当前的E-节点移动到一个新节点,那么这个新节点将变成一个活节点和新的E-节点,旧的E-节点仍是一个活节点。如果不能移到一个新节点,当前的E-节点就“死”了(即不再是一个活节点),那么便只能返回到最近被考察的活节点(回溯),这个活节点变成了新的E-节点。当我们已经找到了答案或者回溯尽了所有的活节点时,搜索过程结束。
例4-1 [迷宫老鼠] 考察图16-3a 的矩阵中给出的3×3的“迷宫老鼠”问题。我们将利用图1 6 -1给出的解空间图来搜索迷宫。
从迷宫的入口到出口的每一条路径都与图1 6 - 1中从( 1 , 1 )到( 3 , 3 )的一条路径相对应。然而,图1 6 - 1中有些从( 1 , 1 )到( 3 , 3 )的路径却不是迷宫中从入口到出口的路径。搜索从点( 1 , 1 )开始,该点是目前唯一的活节点,它也是一个E-节点。为避免再次走过这个位置,置m a z e( 1 , 1 )为1。从这个位置,能移动到( 1 , 2 )或( 2 , 1 )两个位置。对于本例,两种移动都是可行的,因为在每一个位置都有一个值0。假定选择移动到( 1 , 2 ),m a z e( 1 , 2 )被置为1以避免再次经过该点。迷宫当前状态如图16-3b 所示。这时有两个活节点(1,1) (1,2)。( 1 , 2 )成为E-节点。
在图1 6 - 1中从当前E-节点开始有3个可能的移动,其中两个是不可行的,因为迷宫在这些位置上的值为1。唯一可行的移动是( 1 , 3 )。移动到这个位置,并置m a z e( 1 , 3 )为1以避免再次经过该点,此时迷宫状态为1 6 - 3 c。图1 6 - 1中,从( 1 , 3 )出发有两个可能的移动,但没有一个是可行的。所以E-节点( 1 , 3 )死亡,回溯到最近被检查的活节点( 1