Algorithm Series 2
Branch and Bound
What is branch and bound?
Branch-and-bound consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidates are discarded en masse, by using upper and lower estimated bounds of the quantity being optimized.
The key idea of the BB algorithm is: if the lower bound for some tree node (set of candidates) A is greater than the upper bound for some other node B, then A may be safely discarded from the search. This step is called pruning.
How?
Branch-and-bound is composed of two main actions:
The first step is the branching. This is where we define the tree structure from the set of candidates in a recursive manner.
The second action is called bounding since this procedure calculates the upper and lower bounds of each node from the tree.
Furthermore, there's the additional pruning step that we can add. It means that if the lower bound for some node of the tree is greater than the upper bound of some other node of the tree, then the first node of the tree can be "discarded" from the search. A variable always holds the value of the global minimum upper bound.
A branch and bound algorithm is based on an advanced breadth-first search. The said BFS is done with a priority queue instead of the traditional list.
Main steps is to branch and prune, then enqueue/and dequeue.
Normally branch and bound algorithm is implemented with breadth-first search and FIFO queue or priority queue.
Both the backtracking and divide and conquer traverse the tree of problem space in its depth, though they take opposite routes. The greedy strategy picks a single route and forgets about the rest. Dynamic programming approaches this in a sort of breadth-first search variation (BFS).
Examples
KnapSack
Knapsack Backtracking Solutions with/without bounding functions
KnapSack_Back.java 0/1 knapsack implemented in Java
IntKS_Back.java Integer knapsack implemented in Java
0/1 KnapSack
cw(i) = sum(j=1..i)w[j]*x[j]
Constraint function
C(i) = cw(i-1) + w[i] if C(i) > W then discard its subtree
Bound function
B(i) = C(i) + r(i)
r(i) = sum(j=i+1..n)v[j]
if B(i) <=bestw, then discard its subtree
Put special node to the queue (-1) to indicate we have done finishes this layer of the tree.
Max loading
Similar as 0/1 KnapSack
Travelling salesman problem
cw(i) = sum(j=2..i)w[x[j-1],x[j]]
Bound function
B(i) = cw(i-1) + w[x[j-1],x[j]] if B(i) >= bestw, then discard its subtree
Flow shop[to-do]
N queen [FIFO BB]
运动员最佳匹配
Resources:
