I=24
11
a,b,d,e,c,a
I=16
9
Notes
Finding a good bounding is not a simple task. On the one hand. We want this function to be easy to
compute. On the other hand, it cann’t be too simplistic.—otherwise,
The value of the best solution seen so far.
4
The main idea
Set up a bounding function, which is used to compute a bound (for the value of the objective function) at a node on a state-space tree and determine if it is promising Promising (if the bound is better than the value of the best solution so far: expand beyond the node. Nonpromising (if the bound is no better than the value of the best solution so far--:not smaller for a
minimization problem and not larger for a
maxmization problem ): not expand beyond the node (pruning the state-space tree).
5
0
Start Ib=10
1
a￫1
Ib=17
5
b￫1
Ib=13
8
Traveling salesman
0
a
Ib=14
5
a,b,c
Ib=16
1
a,b
Ib=14
6
a,b,e Ib=19
2
a,c
7
a,b,d Ib=16
3
a,d
Ib=16
4
a,e
Ib=19
b is not before c
8
a,b,c,d,e,a
l=24
9
a,b,c,e,d,a
l=19
10
a,b,d,c,e,a
which nodes to explore
Combine depth-first search and breadth-first search. Selecting the node with the best estimated cost among all nodes.
3
Branch and Bound8来自c￫3Ib=13
9
c￫4
Ib=20
10
d￫4
Cost=13
2
a￫2
Ib=10
6
b￫3
Ib=14
3
a￫3
Ib=20
7
b￫4
Ib=17
4
a￫4
Ib=18
边界（下界）的选择：
初始节点边界：包括最优解在内，任 何解的成本都不会小于矩阵每行中的 最小元素的和。
节点其它边界：实际产生的成本+还 要付出的最小成本（估计）
Branch-and-bound
1
Branch and Bound
An enhancement of backtracking Similarity A state space tree is used to solve a problem Difference used only for optimization problems. The backtracking requires the using of DFS traversal and is used for nonoptimization problems. Branch and bound: does not limit us to any particular way of traversing the tree (Best-first)
It is NP-complete.
7
Traveling Salesman Problem—Bounding Function
边界（下界）函数的选择：
初如节点边界：对于每一个城市，求出该城市 到距离其最近的另外两个城市的距离之和，并 把所有城市的该距离和除以2取整。
其它节点边界：实际产生的成本+还要付出的最 小成本（估计）
it would fail in its principal task to prune as many branches of a state-space tree as soon as possible.
Compared to backtracking ,branch-and-bound requires two additional items.
A way to provide, for every node of a state-space-tree ,a bound on the best value of the objective function on any solution that can be obtained by adding further omponents to the partial solution represented by the node.
2
Branch and bound (cont.)
Branching strategy: how to partition solution space
Node selection strategy:
sequence of exploring nodes:
depth first (tries to obtain a solution fast) breadth/best bound first (tries to find the best solution)
6
The traveling salesperson optimization problem
Given a set of points and their pairwise distances, the task is to find a shortest tour that visits each point exactly once.