第六章回溯法 §1.回溯法的基本思想 回溯法有“通用的解题法”之称。应用回溯法解问题时,首先应 该明确问题的解空间。一个复杂问题的解决往往由多部分构成,即 一个大的解决方案可以看作是由若干个小的决策组成。很多时候它们 构成一个决策序列。解决一个问题的所有可能的决策序列构成该问题 的解空间。解空间中满足约束条件的决策序列称为可行解。一般说来, 解任何问题都有一个目标,在约束条件下使目标达优的可行解称为该 问题的最优解。在解空间中,前k项决策已经确定的所有决策序列之 集称为k定子解空间。0定子解空间即是该问题的解空间。 例1.旅行商问题:某售货员要到若干个城市去推销商品。已知各 个城市之间的路程(或旅费)。他要选定一条从驻地出发,经过每个 城市一次,最后回到驻地的路线,使得总的路程(或总旅费)最短。 我们用一个带权图G(VE来表示,顶点代表城市,边表示城市之 间的道路。图中各边所带的权即是城市间的距离(或城市间的旅费)。 A 6 10 具有四个顶点的带权图 则旅行商问题即是:在带权图G中找到一条路程最短的周游路线,即
第六章 回 溯 法 § 1. 回溯法的基本思想 回溯法有“通用的解题法”之称。应用回溯法解问题时，首先应 该明确问题的解空间。一个复杂问题的解决往往由多部分构成，即， 一个大的解决方案可以看作是由若干个小的决策组成。很多时候它们 构成一个决策序列。解决一个问题的所有可能的决策序列构成该问题 的解空间。解空间中满足约束条件的决策序列称为可行解。一般说来， 解任何问题都有一个目标，在约束条件下使目标达优的可行解称为该 问题的最优解。在解空间中，前 k 项决策已经确定的所有决策序列之 集称为 k 定子解空间。0 定子解空间即是该问题的解空间。 例 1．旅行商问题: 某售货员要到若干个城市去推销商品。已知各 个城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个 城市一次，最后回到驻地的路线，使得总的路程（或总旅费）最短。 我们用一个带权图 G(V, E)来表示，顶点代表城市，边表示城市之 间的道路。图中各边所带的权即是城市间的距离（或城市间的旅费）。 30 5 4 6 10 20 具有四个顶点的带权图 则旅行商问题即是：在带权图 G 中找到一条路程最短的周游路线，即 A C D B
权值之和最小的 Hamilton圈 如果假定城市A是驻地。则推销员从A地出发,第一站有3种选 择:城市B、C或城市D;第一站选定后,第二站有两种选择:如第 一站选定B,则第二站只能选C、D两者之一。当第一、第二两站都 选定时,第三站只有一种选择:比如,当第一、第二两站先后选择了 B和C时,第三站只能选择D。最后推销员由城市D返回驻地A。推 销员所有可能的周游路线可由下面的图反映出来。 例2.定和子集问题:已知一个正实数的集合A={,2…,wn} 和正实数M.试求A的所有子集S,使得S中的数之和等于M 这个问题的解可以表示成0/数组(x1,x2,,xn),依据w是否 属于S,x1分别取值1或0。故解空间中共有2个元素。它的树结构 是一棵完全二叉树 例3.4皇后问题:在4×4棋盘上放置4个皇后,且使得每两个之 间都不能互相攻击,即任意两个皇后都不能放在同一行、同一列及同 对角线上。 将4个皇后分别给以1到4的编号,这个问题的解决就是要安排 4个皇后的位置。因而,每个决策序列由4个决策组成:P1,P2,P3, P4,这里P代表安排第k个皇后的位置,因而有16种可能。该问题 的解空间有164个决策序列。这时的约束条件是:任意两个皇后均不 能位于同一行、同一列及同一个对角线上。注意到这个解空间比较大, 从中搜索可行解较为困难。现在把约束条件中的“任意两个皇后均不 在同一行”也放在问题中考虑,即:将4个皇后放在4×4棋盘的不
权值之和最小的 Hamilton 圈。 如果假定城市 A 是驻地。则推销员从 A 地出发，第一站有 3 种选 择：城市 B、C 或城市 D；第一站选定后，第二站有两种选择：如第 一站选定 B，则第二站只能选 C、D 两者之一。当第一、第二两站都 选定时，第三站只有一种选择：比如，当第一、第二两站先后选择了 B 和 C 时，第三站只能选择 D。最后推销员由城市 D 返回驻地 A。推 销员所有可能的周游路线可由下面的图反映出来。 例 2．定和子集问题：已知一个正实数的集合 { , , , } A = w 1 w2 L wn 和正实数 M．试求 A 的所有子集 S，使得 S 中的数之和等于 M。 这个问题的解可以表示成 0/1 数组(x1, x2, . . . , xn )，依据 wi是否 属于 S，xi分别取值 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″个元素,遍历子集树的任 何算法均需Ω2(2")的计算时间。如例2。当所给的问题是确定n个元 素的满足某种性质的排列时,相应的解空间树称为排列树,此时,解 空间有n个元素。遍历排列树的任何算法均需Ω(nl)计算时间,如例 1和例3。本章只讨论具有上两类解空间树的求解问题。 确定了解空间的组织结构后,回溯法就从开始顶点(解空间树的 根顶点)出发,以深度优先的方式搜索整个解空间。这个开始顶点就 成为一个活顶点,同时也成为当前的扩展顶点。在当前的扩展顶点处, 搜索向纵深方向移至一个新顶点。这个新顶点就成为一个新的活顶 点,并且成为当前的扩展顶点。如果在当前的扩展顶点处不能再向纵
同行上，使得每两个皇后均不能位于同一列、同一对角线上。则解 空间中共有 44个决策序列，因为此时可以假定第 k 个皇后处于第 k 行上。此时的约束条件为：任意两个皇后均不能位于同一列及同一个 对角线上。事实上，我们还可以用另一种方法描述，使得解空间进一 步缩小。将问题陈述为：将 4 个皇后放在 4×4 棋盘的不同行、不同 列上，使得任意两个皇后均不能处在同一对角线上。这时的解空间应 当由 4！个决策序列构成。因为此时每个决策序列实际上对应于{1, 2, 3, 4}的一个排列。我们可以用树来描述解空间。 从例 3 来看，解空间的确定与我们对问题的描述有关。如何组织 解空间的结构会直接影响对问题的求解效率。这是因为回溯方法的基 本思想是通过搜索解空间来找到问题的可行解以至最优解。当所给的 问题是从 n 个元素的集合 S 中找出满足某种性质的子集时，相应的解 空间树称为子集合树。此时，解空间有 n 2 个元素，遍历子集树的任 何算法均需 (2 ) n Ω 的计算时间。如例 2。当所给的问题是确定 n 个元 素的满足某种性质的排列时，相应的解空间树称为排列树，此时，解 空间有n!个元素。遍历排列树的任何算法均需Ω(n!) 计算时间，如例 1 和例 3。本章只讨论具有上两类解空间树的求解问题。 确定了解空间的组织结构后，回溯法就从开始顶点（解空间树的 根顶点）出发，以深度优先的方式搜索整个解空间。这个开始顶点就 成为一个活顶点，同时也成为当前的扩展顶点。在当前的扩展顶点处， 搜索向纵深方向移至一个新顶点。这个新顶点就成为一个新的活顶 点，并且成为当前的扩展顶点。如果在当前的扩展顶点处不能再向纵
深方向移动,则当前的扩展顶点就成为死顶点。此时应往回移动(回 溯)至最近一个活顶点处,并使这个活顶点成为当前扩展顶点。回溯 法即以这种工作方式递归地在解空间中搜索,直至找到要求的解或解 空间中已无活结点时为止。事实上,当我们将问题的有关数据以一定 的方式存储好以后(例如,旅行商问题存储赋权图的邻接矩阵、定和 子集问题是存储已知的n+1个数、4皇后问题用整数对(i,j)表示棋 盘上各个位置),不必先建立一个解空间树,然后再搜索该树寻找所 需要的解。回溯法实际上在搜索的同时逐步生成解空间树(实际只需 要一部分)。也就是说,对于实际问题我们不必要搜索整个解空间。 为了使搜索更加有效,我们常常在搜索过程中加一些判断以决定搜索 是否该终止或改变路线。通常采用两种策略来避免无效的搜索,提高 回溯法的搜索效率。其一是使用约束函数在扩展顶点处剪去不满足约 束的子树;其二是用限界函数(后面将阐述)剪去不能得到最优解的 子树。这两种函数统称为剪枝函数。 运用回溯法解题通常包括以下三个步骤: 1).针对所给问题,定义问题的解空间 2).确定易于搜索的解空间结构; 3).以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函 数避免无效的搜索 §2定和子集问题和0/1背包问题 定和子集问题可以描述成下列的数学问题:确定所有向量 x=(x1,x2,…,xn)满足
深方向移动，则当前的扩展顶点就成为死顶点。此时应往回移动（回 溯）至最近一个活顶点处，并使这个活顶点成为当前扩展顶点。回溯 法即以这种工作方式递归地在解空间中搜索，直至找到要求的解或解 空间中已无活结点时为止。事实上，当我们将问题的有关数据以一定 的方式存储好以后（例如，旅行商问题存储赋权图的邻接矩阵、定和 子集问题是存储已知的 n+1 个数、4 皇后问题用整数对(i,j)表示棋 盘上各个位置），不必先建立一个解空间树，然后再搜索该树寻找所 需要的解。回溯法实际上在搜索的同时逐步生成解空间树（实际只需 要一部分）。也就是说，对于实际问题我们不必要搜索整个解空间。 为了使搜索更加有效，我们常常在搜索过程中加一些判断以决定搜索 是否该终止或改变路线。通常采用两种策略来避免无效的搜索，提高 回溯法的搜索效率。其一是使用约束函数在扩展顶点处剪去不满足约 束的子树；其二是用限界函数（后面将阐述）剪去不能得到最优解的 子树。这两种函数统称为剪枝函数。 运用回溯法解题通常包括以下三个步骤： 1).针对所给问题，定义问题的解空间； 2).确定易于搜索的解空间结构； 3).以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函 数避免无效的搜索。 §2.定和子集问题和 0/1 背包问题 定和子集问题可以描述成下列的数学问题：确定所有向量 ( , , , ) 1 2 n x = x x L x 满足：
x∈{0,1},=1,2,…,n ∑x1=M (7.1) 如果让w;表示第i件物品的重量,M代表背包的容量,则0/1背 包问题可以描述为:确定一个向量x=( xn)满足 0,1},=1,2 ∑x≤M (7.2) l≤i≤n s!.max∑px 这是一个优化问题,与定和子集问题比较,它多出优化函数,但只要 求确定一个最优解,定和子集问题要求确定所有可行解。我们先来处 理定和子集问题。 ).定和子集问题 用回溯法求解的过程也即是生成解空间树的一棵子树的过程,因为期 间将剪掉不能产生可行解的子树(即不再对这样的子树进行搜索)。 按照前面关于回溯算法的基本思想的说明,搜索是采用深度优先的路 线,算法只记录当前路径。假设当前扩展顶点是当前路径的k级,也 就是说当前路径上,x,1≤i≤k已经确定,算法要决定下一步搜索目 标。此时,有两种情况 ∑x1=M与∑w1x<M 前一种情况说明当前路径已经建立一个可行解,当前扩展顶点即是 个答案顶点。此时应停止对该路径的继续搜索,返回到前面最近活顶 点。后一种情况出现,算法需要判断是否需要继续向前搜索。显然 只有当∑wx+∑≥M时才有必要继续向前搜索。如果集合 l≤i≤k k+l≤i≤n
w x M x i n i i n i i = ∈ = ∑ 1≤ ≤ {0,1}, 1,2,L, (7.1) 如果让 wi表示第 i 件物品的重量，M 代表背包的容量，则 0/1 背 包问题可以描述为：确定一个向量 ( , , , ) 1 2 n x = x x L x 满足 i i n i i i n i i st p x w x M x i n ∑ ∑ ≤ ≤ ≤ ≤ ≤ ∈ = 1 1 . . max {0,1}, 1,2,L, (7.2) 这是一个优化问题，与定和子集问题比较，它多出优化函数，但只要 求确定一个最优解，定和子集问题要求确定所有可行解。我们先来处 理定和子集问题。 (一).定和子集问题 用回溯法求解的过程也即是生成解空间树的一棵子树的过程，因为期 间将剪掉不能产生可行解的子树（即不再对这样的子树进行搜索）。 按照前面关于回溯算法的基本思想的说明，搜索是采用深度优先的路 线，算法只记录当前路径。假设当前扩展顶点是当前路径的 k 级，也 就是说当前路径上，xi，1≤i≤k 已经确定，算法要决定下一步搜索目 标。此时，有两种情况： w xi M i k ∑ i = 1≤ ≤ 与 w xi M i k ∑ i < 1≤ ≤ 前一种情况说明当前路径已经建立一个可行解，当前扩展顶点即是一 个答案顶点。此时应停止对该路径的继续搜索，返回到前面最近活顶 点。后一种情况出现，算法需要判断是否需要继续向前搜索。显然， 只有当 w x w M k i n i i i k ∑ i + ∑ ≥ 1≤ ≤ +1≤ ≤ 时才有必要继续向前搜索。如果集合
A={v,w2,…,wn}中的元素是按不降的次序排列的,则上述继续搜 索的条件还可以加强为 ∑x+∑≥Mamd∑wx+Wk+1≤M 7.3) k+l≤ 上述不等式记做Bk。 定和子集问题的回溯算法伪代码 SumSubset(s,k,r)/寻找W[1:n]中元素和为M的所有子集。 //w[l:n]中元素按不降次序排列,进入此过程时,X[1], //X[k-1]的值已经确定。记s=∑W小X[小,r=∑W l≤j≤k-1 k≤j≤n //假定W[1]≤M,∑W[门≥M l≤j≤n 1 global integer M, n; global real W[l: n]; 2 global boolean X[l: n] 3 real, s: integer k, j: //由于B-=true,因此s+W[k]≤M 4X[k]=1;//生成左儿子。 5 if s+Wk print (X[j], j from 1 to k) else fs+W[k]+W[k+1]≤Mthe Sum Subset(s+Wlk, k+1, r-WLkD 9 endif 10 dif
{ , , , } A = w 1 w2 L wn 中的元素是按不降的次序排列的，则上述继续搜 索的条件还可以加强为 w x w M and w xi wk M i k i k i n i i i k i + ≥ + + ≤ ≤ ≤ + ≤ ≤ ≤ ≤ ∑ ∑ ∑ 1 1 1 1 (7.3) 上述不等式记做 Bk。 定和子集问题的回溯算法伪代码 SumSubset(s,k,r) // 寻找 W[1:n]中元素和为 M 的所有子集。 //W[1:n]中元素按不降次序排列，进入此过程时，X[1], . . . , //X[k-1]的值已经确定。记 ∑ ≤ ≤ − = 1 1 [ ] [ ] j k s W j X j ， ∑ ≤ ≤ = k j n r W[ j] //假定 W[1] ≤ M, ∑ ≤ ≤ ≥ j n W j M 1 [ ] 1 global integer M, n; global real W[1:n]; 2 global boolean X[1:n]; 3 real r, s; integer k, j; //由于 Bk-1=true，因此 s + W[k]≤ M 4 X[k]=1; // 生成左儿子。 5 if s + W[k]= M then print (X[j],j from 1 to k); 6 else 7 if s + W[k] + W[k+1] ≤ M then 8 SumSubset(s+W[k], k+1, r-W[k]); 9 endif 10 endif
11ifs+r-W[k]≥ M and s+W[k+1]≤ m then 12 X[k]=0;//生成右儿子 13 SumSubset(s, k+l, r-WLkD 14 endif 15 end Sum Subset 因为假定W[1]≤M,∑W门≥M,所以程序开始执行时, l≤j≤n B=true。同样,程序在递归执行过程中,总是以前提条件B-1=true 开始处理第k级顶点的儿子们的生成过程,由第3~10语句完成,并 在此过程中决定是否转动生成下一级顶点的儿子的生成过程,由11~ 14语句完成。语句11是一个判断条件,如果这个条件不能满足,则 没有必要生成k级顶点的右儿子。而在左儿子被生成后,语句4和语 句7决定是否沿着这个左儿子继续搜索。所以该算法所生成的子树的 叶顶点或是某个左儿子,此时找到一个可行解;或者是某个右儿子 此时由根顶点到该顶点的路径不能延伸为可行解 例子:n=6,M30;W[1:6]=(5,10,12,13,15,18).由算法 SumSubset所生成的解空间树的子树参看文档 Sum Subset树。 (二).0/1背包问题 0/1背包问题是一个优化问题,因此不仅可以使用约束函数,而且可以 使用限界函数做剪枝函数.如果当前背包中的物品总重量是cw,前面 k-1件物品都已经决定好是否放入包中,那么第k件物品是否放入包 中取决于不等式cw+w≤M是否满足.这即是搜索的约束函数.另外
11 if s + r – W[k]≥ M and s + W[k+1] ≤ M then 12 X[k]=0; //生成右儿子 13 SumSubset(s,k+1,r-W[k]); 14 endif 15 end SumSubset 因为假定 W[1] ≤ M， ∑ ≤ ≤ ≥ j n W j M 1 [ ] ，所以程序开始执行时， 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 树。 (二).0/1 背包问题 0/1背包问题是一个优化问题,因此不仅可以使用约束函数,而且可以 使用限界函数做剪枝函数.如果当前背包中的物品总重量是 cw,前面 k-1 件物品都已经决定好是否放入包中,那么第 k 件物品是否放入包 中取决于不等式 cw + wk ≤ M 是否满足.这即是搜索的约束函数.另外
我们可以如下确定限界函数.回忆可分割的0/1背包问题的贪心算法, 当物品的按照P/w1≥P+1w的规则排序时,最优解是 (x1,…,x-1,x1,x1+1…,xn)=(1,…1,1,0,…,0)的形式,其中,0≤t≤1 设当前背包中物品的总效益值时cp,如下方式确定限界函数 构造限界函数 Bounde(cp,cw,k,M)//返回效益值的当前限界 gloal n, p[l:n], w[1:n] integer k, i; real b, c, cp, cw, M: B=cp; c=cw for i from k+1 to n do C-C if c< M then b=b+pli] else return (b+(1-(c-D)/wli])*p[i] endif enat or return(b) end bound 这样确定的限界函数表明,从当前确定的k-1定子解空间中寻求到的 可行解所能达到的效益值以当前限界函数的值为上界.所以,如果搜 索最优解的算法在此之前已经知道大于这个限界值的效益,则没有必 要在当前确定的k-1定子解空间中搜索.据此我们给出0/1背包问题 的回溯算法
我们可以如下确定限界函数.回忆可分割的 0/1 背包问题的贪心算法, 当物品的按照 1 1 / / i i ≥ i+ wi+ p w p 的规则排序时,最优解是 ( , , , , , , ) (1, ,1, ,0, ,0) x1 L xl −1 xl xl +1 L xn = L t L 的形式,其中,0 ≤ t ≤ 1. 设当前背包中物品的总效益值时 cp,如下方式确定限界函数: 构造限界函数 BoundF(cp,cw,k,M) //返回效益值的当前限界 gloal n, p[1:n],w[1:n]; integer k,i; real b,c,cp,cw,M; B=cp;c=cw; for i from k+1 to n do c=c+w[i]; if c < M then b=b+p[i]; else return (b+(1-(c-M))/w[i])*p[i]; endif endfor return (b); end BoundF 这样确定的限界函数表明,从当前确定的 k-1 定子解空间中寻求到的 可行解所能达到的效益值以当前限界函数的值为上界.所以,如果搜 索最优解的算法在此之前已经知道大于这个限界值的效益,则没有必 要在当前确定的 k-1 定子解空间中搜索.据此我们给出 0/1 背包问题 的回溯算法
0/1背包问题的回溯算法 BackKnap(M,n,W,P,fw,fp,X)/M是背包容量.n件物品,数W[1:n] //和P[l:n]分别表示重量和价值,fw是背包的最后重量,fp是 //背包的最大效益.X[1:n]中美国元素取0或1值.若物品k未放 /入背包,则X[k]=0;否则,X[k]=1 1 integer n,k, Y[l: n], 1, X[l: n] 2 real M, W[1:n], P[l:n], fw, fp, cw, cp: 3cw=0;cp=0;k=1;fp=-1 4 loop 5 while kn then 9 p=cp;fw=cw;k=n;X=Y;//修改解 10 else Y[K]=0 11 endif hile Bound(cp, cw, k, M)<fp do while k≠0&&Y[k]≠1do k=k-1 15 endwhile 16 if k=o then return endif Y[K]=0; cw=cw-W[k]: cp=cp-P[k]
0/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. 1 integer n,k,Y[1:n],I,X[1:n]; 2 real M,W[1:n],P[1:n],fw,fp,cw,cp; 3 cw=0; cp=0; k=1; fp=-1; 4 loop 5 while k≤n && cw+W[k]≤ M do //使用约束函数 6 cw=cw+W[k]; cp=cp+P[k]; Y[k]=1; k=k+1; 7 endwhile 8 if k>n then 9 fp=cp; fw=cw; k=n; X=Y;//修改解 10 else Y[k]=0; 11 endif 12 while BoundF(cp,cw,k,M)≤fp do 13 while k≠0 && Y[k]≠1 do 14 k=k-1; 15 endwhile 16 if k=0 then return endif 17 Y[k]=0;cw=cw-W[k];cp=cp-P[k];
18 endwhile 19k=k+1 endloop 21 end BackKnap 算法釆用一个大的循环搜索各条可能的路径.当一条路径的搜索到某 步不能继续往下搜索时,此时或是因为约束函数不满足,或是因为 限界函数不满足.它们分别在语句5~7的子循环和语句12~18的子循 环中达到这是程序的两个主要部分其余主要时处理边界条件,如k> n的验证等.第一种情况出现时,语句8~11给出部分处理,剩下的事情 交给语句12~19来处理这里给出了搜索退回的方案 §3.n-皇后问题和旅行商问题 在第一节已经给出了这两个问题的解空间.如果用 (x1,x2…,xn)表示解,则它是自然数{2…n}的一个排列.对于旅 行商问题,我们可以假定x=1,表示售货员的驻地是城市1.采用回 溯方法,对于n皇后问题,主要任务是给出约束函数,对于旅行商问题 主要是限界函数,因为此时我们可以假定带权图是完全图,这只要将 实际不相邻的两个顶点间用带有权∞的边连接即可 ().n-皇后问题 这里的约束条件是:任何两个皇后都不能位于同一对角线上.如 果我们用(i,j)表示棋盘上第i行与第j列交叉的位置.则在同一条平 行于主对角线的对角线上的两点(和(k,)满足关系式ij=k-l 而处于同一条平行于副对角线的对角线上的两点(i,)和(k,)则满足
18 endwhile 19 k=k+1; 20 endloop 21 end BackKnap 算法采用一个大的循环搜索各条可能的路径.当一条路径的搜索到某 一步不能继续往下搜索时,此时或是因为约束函数不满足,或是因为 限界函数不满足.它们分别在语句 5~7 的子循环和语句 12~18 的子循 环中达到.这是程序的两个主要部分,其余主要时处理边界条件,如 k > n 的验证等. 第一种情况出现时,语句 8~11 给出部分处理,剩下的事情 交给语句 12~19 来处理.这里给出了搜索退回的方案. §3.n-皇后问题和旅行商问题 在第一节已经给出了这两个问题的解空间.如果用 ( , , , ) 1 2 n x x L x 表示解,则它是自然数{1,2,L, n}的一个排列.对于旅 行商问题,我们可以假定 1 x1 = ,表示售货员的驻地是城市 1.采用回 溯方法,对于 n 皇后问题,主要任务是给出约束函数,对于旅行商问题 主要是限界函数,因为此时我们可以假定带权图是完全图,这只要将 实际不相邻的两个顶点间用带有权∞的边连接即可. (一).n-皇后问题 这里的约束条件是: 任何两个皇后都不能位于同一对角线上.如 果我们用(i, j)表示棋盘上第 i 行与第 j 列交叉的位置.则在同一条平 行于主对角线的对角线上的两点(i, j)和(k,l)满足关系式i − j = k − l ; 而处于同一条平行于副对角线的对角线上的两点(i, j)和(k,l)则满足
