课后答案网（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，搜索空间树略略