16-10-2012, 12:09 PM
Backtracking and Branch & Bound
Backtracking and Branch.pdf (Size: 1.1 MB / Downloads: 44)
Backtracking:
•A given problem has a set of constraints and possibly an objective function
•The solution optimizes an objective function, and/or is feasible.
•We can represent the solution space for the problem using a state space tree
–The root of the tree represents 0 choices,
–Nodes at depth 1 represent first choice
–Nodes at depth 2 represent the second choice, etc.
–In this tree a path from a root to a leaf represents a candidate solution
•Search the solution space tree in a depth-first manner.
•May be done recursively or use a stack to retain the path from the root to the current node in the tree.
•The solution space tree exists only in your mind, not in the computer
Backtracking for optimization problems:
•To deal with optimization we compute:
best - value of best solution achieved so far
value(v) - the value of the solution at node v
–Modify promising(v)
•Best is initialized to a value that is equal to a candidate solution or worse than any possible solution.
•Best is updated to value(v) if the solution at v is “better”
•By “better” we mean:
–larger in the case of maximization and
–smaller in the case of minimization
•A node is promising when
–it is feasible and can lead to a feasible solution and
–“there is a chance that a better solution than best can be achieved by expanding it”
•Otherwise it is nonpromising
•A bound on the best solution that can be achieved by expanding the node is computed and compared to best
•If the bound > best for maximization, (< best for minimization) the node is promising
Branch and Bound:
•Branch and bound (BB) is a enhancement of Backtracking used for finding optimal solutions of various optimization problems.
•It consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidates are discarded, by using upper and lower estimated bounds of the quantity being optimized.