• 在4×4的方格棋盘上,将数字1,2,3,…,15以任意 顺序放置在棋盘的各个方格中，空出一格 , 如 图8.2(a)为15谜问题的一种初始棋盘格局。
图8.2 15谜问题的一个实例Ⅰ
• 定理8.1 对于一个给定的状态
• 如果这个和数是偶数,则这个状态可达目标状 态,否则,其他任何初态都不可达目标状态。
• ④如果U是一个单纯的上界，它是由一可行 结点X的u值修改而得，U=u(X)+ε。对于X的 儿子只杀死c′(Y)＞U的Y，c′(Y)=U的Y不被杀 死，Y入堆； • ⑤虽然找到了一个答案结点X,但它的成本值 大于它的上界值 u(X), 这说明 , 这个答案结点 的 子 孙 中 还 有 成 本 更 小 的 答 案 结 点 ,U 取 u(X)+ε, 对于 X 的儿子结点 Y, 只杀死 c′(Y) ＞ U 的Y，c′(Y)=U的Y不被杀死,Y入堆。 • 8.3 0/1背包问题的LC-分枝—限界求解的 实现
• end • if 不再有活结点 or 下一个E-结点有C′≥U then • begin • print(′least cost=′，U) • while ans≠0 do • begin • print(ans) • ans←parent(ans) • end； • return；
• • • • • • •
• end • else • begin • U←u(T)+ε • ans←0 • end • • loop • for E的每个儿子 do • if C′(X)＜U then
• • • • • • • • • • •
begin call ADD(X) parent(X) ← E case ∶X是解结点and cost(X)＜U begin U←min(cost(X)，u(X)+ε) ans←X end ∶u(X)+ε＜U∶U←u(X)+ε endcase
end call least(E) repeat endp； 对算法LCBB还需强调以下几点： ①当下一个E-结点使C′≥U时，算法终止； ②子算法 ADD 是加入一个结点到活结点表中， LEAST 是从一个活结点表中删去一个结点，活结 点表作成一个min—堆； • ③如果U是已找到的一个解X的成本值，U=c(X)＜ u(X) ， 对 于 X 的 儿 子 Y ， 不 仅 c′(Y) ＞ U ， 而 且 c′(Y)=U的结点Y都要被杀死；
8.3 给定的初态，它需要产生更多的结点， 但是如果检索如
• 的状态空间树，按设想1,g(1)=1, 按设想2, g (1) = 14 。这里 f ( X ) +14=14 显然更接近 C(X),C(X) 是初态到目标状态的路径长度 , 即 需要移动空白牌的次数。 • 8.1.3 LC-检索的抽象化描述 • 算法8.1
• procedure LCBB(T，c′，u，ε，cost) • /为了找出最小成本结点,检索状态空间树T, 假定T至少包含一个解结点,且C′(X)≤C(X) ≤u(X)/ • begin • E←T；parent(E)←0 • if T是解结点 then • begin • U←min(cost(T)，u(T)+ε) • ans←T
• endp； • 8.2 分枝—限界法解最优化问题 • 例8.2 带限期的作业排序问题。假定有n个 作业Wi，i=1，…，n和一台处理机，每个作 业Wi与一个三元组(pi，di，ti)对应，其中ti是 完成作业Wi需要的时间，di是完成作业Wi需 要的期限，如果不在这个期限di之内完成Wi 则将受到 pi 的罚款。问题的目标是从 n 个作 业中选取一个子集J，要求J中的作业都能在 相应的限期内完成，且使不在J中的作业受 到的罚款总额最小,这样的J就是最优解。
图8.3 15-谜问题的一部分状态空间树
• 设想1：g(X)是结点X表示的状态中没有到达 目标位置的非空白牌的数目。显然，状态X 到达目标状态所需要的移动空白牌的次数 大于g(X)。比如状态X
• 设想2： f (x)同设想1， 这里 j 表示空格的位置。它也是一个可行的 方法,似乎不及设想1中的g (X)好，因为对图
图8.4 大小可变的元组表示对应的状态空间树
• X中最小成本答案结点的上界函数u(X)定义为：
图8.5 大小固定的元组表示对应的状态空间树
• 以图8.4元组大小不固定的状态空间树为例 说明作业排序的LC-分枝—限界算法。开始 时置最小成本答案结点的成本上界U=∞,或
• 由于图8.4中每个圆形结点都是答案结点， 按U的定义： • 算法8.2
• • • • • • • • • • • •
procedure LC(T，C′)； begin E←T
loop if E是答案结点 then begin 输出从E到T return end for E的每个儿子结点X do begin
• call add(x) • parent(x)←E • end • if 不再有活结点 then • begin • print(′No answer node′) • stop • end • call least(E)； • repeat
第8章 分枝一限界法
• 本章的内容是回溯法讨论的问题的继续和 扩展。使用限界函数的深度优先生成结点 方法是回溯法，E结点一直保持到死为止的 状态生成方法叫分枝 — 限界法。在这一章 里，首先介绍状态空间树上的三种检索方 式：FIFO，LIFO，LC检索，再重点介绍用 LC-分枝—限界法解最优化问题的一般实现， 最后得出一个实例0/1背包的解法以及用C语 言实现的程序。
• 8.1 状态空间树上的检索—FIFO，LIFO， LC检索 • 8.1.1 FIFO(first in first out)，LIFO(last in first out)检索
图8 LC-检索 • ①在生成一个答案结点之前，子树X需要生 成的结点数。 • ②在子树 X 中， X 到最近一个答案结点的路 径长。 • 例8.1 15谜问题(15-puzzle)。