回溯法如何提高效率? ◇由开始结点到当前E结点构成解向量 (X1…,x) 如果判定(x1y…,x不能导致最优解,那么就 将可能要测试的m+mn个向量略去。 因此回溯法的测试次数比硬性处理作的测 试次数要少得多。 如何判定(x1,x)能否导致最优解?
回溯法如何提高效率？ 由开始结点到当前E-结点构成解向量 (x1 ,…,xi ) 如果判定(x1 ,…,xi )不能导致最优解，那么就 将可能要测试的mi+1…mn个向量略去。 因此回溯法的测试次数比硬性处理作的测 试次数要少得多。 ◼ 如何判定(x1 ,…,xi )能否导致最优解？
约束条件 ◎回溯法的解需要满足一组综合的约束条件, 通常分为:显式约束和隐式约束 o显式约束条件限定每个x只从一个给定的集 合上取值,例如: x>=0 即s千所有非负实数} x=0或x=1即s={01} k<=x=u即s={a=a<=t 满足显式约束的所有元组确定一个可能的解 空间 ◎隐式约束描述了x必须彼此相关的情况,如 0/背包问题中的背包重量M
约束条件 回溯法的解需要满足一组综合的约束条件， 通常分为：显式约束和隐式约束 显式约束条件限定每个xi只从一个给定的集 合上取值，例如： ◼ xi>=0 即si={所有非负实数} ◼ xi=0或xi=1 即 si={0,1} ◼ l<=xi<=u 即si={a:l<=a<=u} 满足显式约束的所有元组确定一个可能的解 空间 隐式约束描述了xi必须彼此相关的情况，如 0/1背包问题中的背包重量M
回溯法求解的经典问题(1) 8-皇后问题 在一个8*8棋盘上放置8个皇后,且使得每两 个之间都不能互相“攻击”,也就是使得每 两个都不能在同一行、同一列及同一条斜角 线上。 8皇后问题的解可以表示为8元组(x1…,x), 其中其中x:是第行皇后所在的列号。 o显式约束条件是x{1,2345,7,8},1≤i≤8 o隐式约束条件是,没有两个x可以相同且没 有两个皇后可以在同一条斜角线上
回溯法求解的经典问题（1） 8-皇后问题 在一个8*8棋盘上放置8个皇后，且使得每两 个之间都不能互相“攻击”，也就是使得每 两个都不能在同一行、同一列及同一条斜角 线上。 8皇后问题的解可以表示为8-元组(x1 ,…,x8 ) ， 其中其中xi是第i行皇后所在的列号。 显式约束条件是xi={1,2,3,4,5,6,7,8}, 1≤i≤8 隐式约束条件是，没有两个xi可以相同且没 有两个皇后可以在同一条斜角线上
12345678 2 3 5 6 7 8 Q 由于解向量之间不能相同,所以解空间的大小由88个 元组减少到8:个元组。上图中的解表示为一个8-元组 即(4,6,8,2,7,1,3,5)
Q Q Q Q Q Q Q Q 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 由于解向量之间不能相同，所以解空间的大小由8 8个 元组减少到8!个元组。上图中的解表示为一个8-元组 即（4，6，8，2，7，1，3，5）
回溯法求解的经典问题(2) 子集和数问题 o已知(Ww1w2,…,wn和M,均为正数。要求找出w的和数等 于M的所有子集 求的子集是(11,13,7)和(24013,24,7),M=31,则满足要 例如:若n=4,(w1,W,W3,W)=(1 子集和数问题解的一种表示方法 若用W;的下标表示解向量,这两个解向量为(1,2,4)和 3,4 子集和数问题的解可以表示为k-元组(X1x2,…,x),1kn 并且不同的解可以是大小不同白 的元组。 o显式约束条件是x∈为整数且1jn} o隐式约束条件是 1)没有两个x是相同的; 2)wx的和为M; 3)x<x+1,1i<n(避免产生同一个子集的重复情况)
回溯法求解的经典问题（2） 子集和数问题 已知(w1 , w2 , …, wn )和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)。 子集和数问题的解可以表示为k-元组(x1 , x2 , …, xk ), 1≤k≤n 并且不同的解可以是大小不同的元组。 显式约束条件是xi∈{j|j为整数且1≤j≤n}。 隐式约束条件是 ◼ 1)没有两个xi是相同的; ◼ 2)wxi的和为M; ◼ 3)xi＜xi＋1 ,1≤i＜n（避免产生同一个子集的重复情况）