算法设计与分析 - 王红梅 - 课后答案网（部分）

课后答案网（http://www.khdaw.com）

i=k+1 1

第九章分支限界法

5，解：应用贪心法求得近似解：(1,4,2,3)，其路径代价为：3+5+7+6=21，这可以作为该问题的上界。把每一个任务的最小代价相加，可以得到下界3+5+3+6=17。所以，目标函数的界为[17,21]。限界函数为：

n

lb= v + ∑ 第k 行的最小值 k = i+ 1 搜索空间如下：

1 start

lb = 17 ） 课后答案网（http://www.khdaw.com

2 a 1→ lb =17

6 ×

7 ×

b 3→ lb = 25 9 c 2→ lb = 21 1 6 → d 3 lb = 21

3 × a 2→

lb = 22 8 b 4 → lb =1 7 10 ×

3→ c

lb = 23

11 × b 1→ lb = 22 4

3→ a lb =1 8

12 × b 2→

lb = 25 4 × 1 c 1→ lb = 23 5 ×

4 →a lb = 26 13 b 4→ lb =1 8 1 5 × →c 2 lb = 22 b 2→ lb = 24

表示该结点被丢弃，结点上方的数字表示搜索顺序 ) (×

6：最优解为（110101），最优值为53，搜索空间树略 7：最优解为（4312），最优值为40，搜索空间树略略