计算机算法基础 分枝－限界法.

Presentation on theme: "计算机算法基础 分枝－限界法."— Presentation transcript:

1 计算机算法基础 分枝－限界法

2 0 预备知识 问题状态 解状态 状态空间 答案状态 状态空间树 活结点 E-结点 死结点 等等…… 本节主要目的
通过对n-皇后问题的分析，学习以上概念，并且了解回溯法

3 解空间树结构的术语 树中每个结点确定求解问题的一个问题状态(problem state)
由根结点到其它结点的所有路径确定了这个问题的状态空间(state space) 解状态(solution states)是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组（满足显式约束） 答案状态(solution states)是这样一些解状态S，由根到S的路径确定了问题的一个解（满足隐式约束） 解空间的树结构为状态空间树(state space tree)

4 利用状态空间树解题 1 设想状态空间树 2 生成问题状态 3 确定问题状态中哪些是解状态 4 哪些解状态是答案状态
生成问题状态  构造状态空间树

5 状态空间树术语 活结点：自己已经生成而其所有的儿子结点还没有全部生成的结点。 E-结点（正在扩展的结点）：当前正在生成其儿子结点的活结点。
死结点：不再进一步扩展或者其儿子结点已全部生成的生成结点。 静态树(static trees)：树结构与所要解决的问题的实例无关。 动态树(dynamic trees)：根据不同的实例而使用不同的树结构。

6 构造状态空间树的两个方法 回溯法 分枝-限界方法 限界函数
当前E-结点R，生成一个新的儿子C，则C就变成一个新的E-结点，对子树C完全检测后，R结点再次成为E-结点 分枝-限界方法 一个E-结点一直保持到变成死结点为止 限界函数 以上两种方法都使用限界函数杀死还没有全部生成其儿子结点的那些活结点

7 分枝－限界法 在生成当前E-结点全部儿子之后再生成其它活结点的儿子 并且，用限界函数帮助避免生成不包含答案结点子树的状态空间
FIFO检索：活结点表采用队 LIFO检索：活结点表采用栈 LC检索：最小成本检索

8 FIFO分枝－限界法 例9.1（4-皇后问题） 39

9 4-皇后问题— 回溯 vs FIFO分枝-限界 回溯 Win！

10 LC-检索（Least Cost） 分枝-限界失败的原因 如何解决？ 排序的标准 对下一个E-结点的选择规则过于死板
排序，让答案结点排在前面！ 寻找一种“有智力”的排序函数C(·)，该函数能够让答案结点尽早生成 排序的标准 下一个E-结点应当是生成答案结点花费成本最小的结点，因此C(·)又称作结点成本函数。 LC：Least Cost

11 LC-检索（结点成本的两个标准） 一：在生成一个答案结点之前，子树X需要生成的结点数。
二：在子树X中离X最近的那个答案结点到X的路径长度。以图9.1为例 节点1、18和34、29和35、30和38的代价分别是4，3，2，1 其他2，3，4级上的点代价应分别大于3，2，1 生成结点（1> > >30 32>31）

12 39

13 LC-检索（结点成本函数） C(·)定义 如果X是答案结点，则C(X)是由状态空间树的根结点到X的成本（即花费的代价，可以是级数、计算复杂度等） 如果X不是答案结点且子树X不包含任何答案结点，则C(X)＝∞ 如果X不是答案结点但子树X包含答案结点，则C(X)等于子树X中具有最小成本的答案结点的成本

14 LC-检索（成本估计函数） 从前面的两个成本度量标准看， 计算C(·)的工作量与原问题的解具有相同复杂度。这是因为计算一个结点的代价通常要检索包含一个答案结点的子树才能确定，而这正是解决此问题所要作的检索工作，因此要得到精确的成本函数一般是不现实的 因此需要成本估计函数g^(X) 出现的新问题 仅利用g^(X) 会导致算法偏向纵深检查，无法有效处理下面这种情况：即g^(W)<g^(Z)，但Z比W更接近答案结点

15 LC分枝-限界检索 为使算法不过分偏向于纵深检查，需改进成本估计函数，使其不只考虑结点X到一个答案结点的估计成本，还应考虑根节点到结点X的成本 c^(X) ＝f (h(X)) + g^(X) h(X)为根结点到结点X的成本 g^(X)是由X到达一个答案结点所需做的附加工作的估计函数 LC-限界检索：选择c^(·)值最小的活结点作为下一个E-结点 BFS： g^(X)＝0； f (h(X)) ＝X的级数 D-Search：f (h(X)) ＝0；每当Y是X的一个儿子时，总有g^(X)>=g^(Y)， LC分枝-限界检索：伴之有限界函数的LC-检索

16 15-谜问题（问题描述） 一种初始排列 目标排列 1 3 4 15 2 5 12 7 6 11 14 8 9 10 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 通过一系列合法移动将初始排列转换成目标排列。 合法移动：将邻接于空格的牌移动到空格。

17 15-谜问题（是否有解） 棋盘存在16！种不同排列 任一初始状态，可到达的状态为这些排列中的一半
在求解问题前，需要判定目标状态是否在初始状态的状态空间中

18 15-谜问题（判定方法） 按目标状态给牌编号，空格为16
用POSITION(i)记录编号为i的牌在初始状态中的位置； POSITION(16)表示空格 图9.2(a)的POSITION ( ) LESS(i)是使得牌j小于牌i且POSITION(j) > POSITION(i)的数目 LESS(1)=0; LESS(4)=1; LESS(12)=6

19 15-谜问题（判定方法） 定理7.1 当且仅当sum(LESS(i) + X)是偶数时，目标状态可由此初始状态到达

20 15-谜问题(宽度优先)

21 15-谜问题(深度优先)

22 15-谜问题（“智能”方法） 针对不同实例用相同规则检索，过于呆板和盲目 是否能够找到一种“智能”方法，给每个结点赋予成本值:
如果结点在根结点到最近目标结点路径上，则成本为这条路径的长度：C(1)=C(4)=C(10)=C(23)=3 否则，成本为∞ 检索时杀死成本为∞的结点 该方法的实际可操作性？

23 15-谜问题 （成本估计值函数） C^(X) = f(X) + g^(X) f(X)：根到结点X的路径长度
1）g^(X) ：是子树X中，由X到目标状态的最短路径长度的估计值 2）状态X转换成目标状态所需的最小移动数 3）g^(X) = 不在其目标位置的非空白牌数目；该值应该比2）要小 C^(X) 是C(X)的下界

24 15-谜问题（使用C^(X)的LC-检索） 结点1为E-结点，生成其儿子结点 C^(2)=1+4 C^(3)=1+4 C^(4)=1+2

25 LC-检索的抽象化控制 line procedure LC(T, c^) //为找答案结点检索T
0 if T是答案结点 then 输出T; return endif 1 E  T 2 将活结点表初始化为空 3 loop 4 for E的每个儿子X do if X是答案结点 then 输出从X到T的路径 return endif call ADD(X) //X是新的活结点 PARENT(X)  E //指示到根的路径 10 repeat (Continue…) X加入到活结点表中

26 从活结点表中删除具有最小c^值的活结点，并且将该结点赋给E
LC-检索的抽象化控制 loop 11 if 不再有活结点 then print(“no answer code”) stop 13 endif 14 call LEAST(E) 15 repeat 16 end LC 从活结点表中删除具有最小c^值的活结点，并且将该结点赋给E

27 LC-检索的抽象化控制 （正确性证明） 过程略 结论 对于有限状态空间树，以及存在答案结点的无限状态空间树，算法能够终止

28 LC-检索的抽象化控制 （vs. BFS, D-Search）
LC算法与BFS及D-Search基本相同 活结点表采用队列 vs BFS 活节点表采用栈 vs D-Search 不同：活结点表的构造，即下一个E-结点的选择规则不同。

29 LC-检索的特性 LC是否一定找得到具有最小成本的答案结点呢？ 否

30 LC-检索的特性－定理7.2 定理7.2 在有限状态空间树T中，对于每一个结点X，令c^(X)是c(X)的估计值且具有以下性质：对于每一对结点Y、Z，当且仅当c(Y)<c(Z)时有c^(Y)<c^(Z)。那么在使c^( )作为c( )的估计值时，算法LC到达一个最小的成本答案结点终止。

31 LC-检索的特性 －定理7.2的证明 [略]

32 LC-检索的特性 －找最小成本答案结点 line procedure LC1(T, c^) //为找最小成本答案结点的LC-检索
0 if T是答案结点 then 输出T; return endif 1 E  T 2 将活结点表初始化为空 3 loop 3’ if E是答案结点 then 输出从E到T的路径 return end if 4 for E的每个儿子X do if X是答案结点 then 输出从X到T的路径 return endif call ADD(X) //X是新的活结点 PARENT(X)  E //指示到根的路径 10 repeat (Continue…)

33 LC-检索的特性 －找最小成本答案结点 loop 11 if 不再有活结点 then print(“no answer code”)
stop 13 endif 14 call LEAST(E) 15 repeat 16 end LC1

34 LC-检索的特性 －定理7.3 定理7.3 令c^()是满足如下条件的函数，在状态空间树T中，对于每一个结点X，有c^(X)<=c(X)，而对于T中的每一个答案结点X，有c^(X)=c(X)。如果算法在第3’行终止，则所找到的答案结点是具有最小成本的答案结点。 证明略

35 分枝-限界算法 限界的目的 下界 上界 减少算法的盲目性，减小搜索空间，从而降低计算量
使用使得c^(X) <= c(X)的成本估计函数c^(·)给出可由任一结点X得出的解的下界 上界 利用上界U，使具有c^(X)>U的所有活结点X可以被杀死

36 分枝-限界算法 (解最优化问题) 一般化的带限期的作业排序问题
假定n个作业和一台处理机 作业i对应一个三元组（pi,di,ti） ti表示作业i需要的单位处理时间 di表示完成期限 pi表示期限内未完成招致的罚款 目标：从n个作业选取子集J，要求J中所有作业都能在各自期限内完成并且使得不在J中的作业招致的罚款总额最小

37 分枝-限界算法 (实例) n = 4; (p1,d1,t1) = (5,1,1); (p2,d2,t2) = (10,3,2); (p3,d3,t3) = (6,2,1); (p4,d4,t4) = (3,1,1); 成本函数:圆形结点X,c(X)是根为X的子树中结点的最小罚款；方形结点， c(X)=∞ 下界函数 m=max{i|i∈ SX}，SX是在结点X对J所选择的作业的子集 上界

38 状态空间树—元组大小可变 其中：圆形结点是答案结点，方形结点代表不可行的子集合

39 状态空间树—元组大小固定

40 找最小成本答案结点的 FIFO分枝-限界方法
如何处理c^(X) = U的情况 为什么要处理？ 如何处理？引进ε，当u(X) < u(Y)时， u(X) < u(X) + ε < u(Y)。 在算法中，比较c^(X) 与U的时候，可以对U作以下处理： 当U是成本值，则不变 当U由一单纯上界得出，U= u(X) + ε

41 FIFO分枝-限界算法FIFOBB line procedure FIFOBB(T, c^, u,ε, cost)
c^(X) <= c(X) <= u(X) 1 E  T; PARENT(E)  0; 2 if T是解结点 then U  min(cost(T), u(T) + ε); ans  T 3 else U  u(T) + ε; ans  0 4 Endif 5 将队列置初值为空 （Continue…）

42 FIFO分枝-限界算法(续1) 6 loop 7 for E的每个儿子X do
if c^(X) < U then call ADDQ(X); PARENT(X)  E case :X是解结点 and cost(X)<U: U  min(cost(T), u(T) + ε); ans  X : u(X)+ ε<U: U  u(X)+ ε endcase endif repeat （Continue…）

43 FIFO分枝-限界算法(续2) 17 loop //得到下一个E-结点
if 队列为空 then print(‘least cost=‘, U) while ans <> 0 do print(ans) ans  PARENT(ans) repeat return endif call DELETEQ(X) if c^(X) < U then exit repeat 28 repeat 29end FIFOBB

44 LC分枝-限界的抽象化控制LCBB 18 if 不再有活结点or下一个E结点有c^(X) >=U
then print(‘least cost=‘, U) while ans<>0 do print(ans) ans  PARENT(ans) repeat return endif call LEAST(X) 27 repeat 28end LCBB

45 效率分析 上下界函数的选择是决定分枝-限界算法效率的主要因素 对U选择一个更好的初值是否能减少所生成的结点数？（否，根据定理7.4）
扩展一些c^(·)>U的结点是否能减少所生成的结点数？（否，根据定理7.5） 假定有两个成本估计函数c1^(·)和c2^(·)，对于状态空间树的每一个结点X，若有c1^(·)<=c2^(·)<=c(X)，则称c2^(·)比c1^(·)好。是否用较好的成本估计函数生成的结点数要少呢？（否，根据定理7.6和定理7.7）

46 0/1背包问题描述 极小化 约束条件 xi=0 或xi=1，1<=i<=n

47 0/1背包问题的函数定义 c(X)= （答案结点） c(X)=∞ （不可行的结点）
c(X)=min{c(LCHILD(X)), c(RCHILD(X))} c^(X)= - Bound( , , j-1, M) U(X) = - Bound( , , j-1, M) 其中j是结点X所在的层级

48 例7.2 n=4, M=15 (p1, p2, p3, p4) = (10, 10, 12, 18) (w1, w2, w3, w4) = (2, 4, 6, 9)

49 例7.2的LC分枝 –限界树 上面的数＝c^ 下面的数＝u 大小固定元组

50 LCBB求解背包问题分析 状态空间树中结点的结构 如何生成一给定结点的儿子 如何识别答案结点 如何表示活结点表

51 状态空间树中结点的结构 PARENT LEVEL TAG CU PE UB 父结点链接指针 状态空间树中的级数 Xi的取值 背包的剩余空间
已装入物品的效益值的和 UB c^(X)

52 如何生成一给定结点的儿子 左儿子生成 PARENT(Y) = X LEVEL(Y) = LEVEL(X) + 1
CU(Y) = CU(X) – WLEVEL(X) PE(Y) = PE(X) + P LEVEL(X) TAG = 1 UB(Y) = UB(X)

53 如何识别答案结点 当且仅当LEVEL(X) = n ＋ 1 X是答案结点

54 如何表示活结点表 Min-堆 测试活结点表是否为空 常量时间 加结点到活结点表 log(n) 删除最小UB值的结点

55 计算上界和下界的算法 line procedure LUBOUND(P, W, rw, cp, N, k, LBB, UBB)
1 LBB  cp; c  rw; 2 for i  k to N do if c<W(i) then UBB LBB+c*P(i)/W(i) for ji+1 to N do if c>=W(j) then c c-W(j) LBB LBB+P(j) endif repeat return endif c c-W(i); LBB LBB+P(i) 12 repeat 13 UBB LBB 14 end LUBOUND

56 生成一个新结点 line procedure NEWNODE(par, lev, t, cap, prof, ub)
1 call GETNODE(I) 2 PARENT(I) par； LEVEL(i) lev；TAG(I) t 3 CU(I) cap；PE(I) prof；UB(I) ub 4 call ADD(I) 5 end NEWNODE

57 背包问题的LC分枝-限界算法 line procedure LCKNAP(P, W, M, N, ε) // 大小固定元组表示状态空间树
// 假设P(1)/W(1)>=P(2)/W(2)>=…>=P(N)/W(N) real P(N), W(N), M, L, LBB, UBB, cap, prof int ANS, X, N 1 call INIT 2 call GETNODE(E) 3 PARENT(E) 0; LEVEL(e) 1; CU(E) M; PE(E) 0 4 call LUBOUND(P, W, M, N, 0, 1, LBB, UBB) 5 L LBB - ε; UB(E) UBB 6 loop i  LEVEL(E); cap CU(E); prof PE(E)

58 背包问题的LC分枝-限界算法 8 case 9 :i=N+1: 10 if prof>L then L prof; ANS E
endif :else: if cap>=W(i) then call NEWNODE(E,i+1,1,cap-W(i), prof+P(1)UB(E)) endif call LUBOUND(P,W,cap,prof,N,i+1, LBB,UBB) if UBB>L then call NEWNODE(E,i+1,0,cap,prof,UBB) L  max(L,LBB- ε) endif endcase

59 背包问题的LC分枝-限界算法 22 if 不再有活结点 then exit endif 23 call LARGEST(E)
until UB(E)<=L repeat call FINISH(L,ANS,N) 26 end LCKNAP

60 FIFO分枝限界树

61 背包问题FIFO分枝-限界算法 line procedure FIFOKNAP(P, W, M, N) // 大小固定元组表示状态空间树
// 假设P(1)/W(1)>=P(2)/W(2)>=…>=P(N)/W(N) real P(N), W(N), M, L, LBB, UBB, E, cap, prof int ANS, X, N 1 call INIT; i 1 2 call LUBOUND(P,W,M,0,N,1,L,UBB) 3 call NNODE(0,0,M,0,UBB) 4 call ADDQ(‘#’) 5 while i<=N do loop call DELETEQ(E)

62 背包问题FIFO分枝-限界算法 8 case 9 :E=‘#’: exit 10 :UB(E)>=L:
cap CU(E); prof PE(E) if cap>=W(i) then call NNODE(E,1,cap-W(i), prof+P(i),UB(E)) endif call LUBOUND(P,W,cap,prof,N,i+1, LBB,UBB) if UBB>=L then call NNODE(E,0,cap,prof,UBB) L  max(L,LBB) endif endcase repeat call ADDQ(‘#’) i  i + 1 24 repeat 25 ANS PE(X)=L的活结点X 26 call FINISH(L,ANS,N) 27 end FIFOKNAP