Please enable JavaScript.
Coggle requires JavaScript to display documents.
Backtraking and Branch-and-bound - Coggle Diagram
Backtraking and Branch-and-bound
Backtracking
usually
depth-first
.
is a more intelligent variation of exhaustive search.
The principal idea is to construct solutions one component at a time and evaluate such partially constructed candidates as follows.
It is convenient to implement this kind of processing by constructing a tree of choices being made, called the
state-space tree
.
A node in a state-space tree is said to be
promising
if it corresponds to a partially constructed solution that may still lead to a complete solution; otherwise, it is called
nonpromising
.
Problems do not become tractable (only some larger instances).
Time efficiency depends on the problem and the instance.
Optimisations
Explore symmetry of combinatorial problems.
Rearrange data of a given instance.
Other applications
Graph colouring
Knight’s tour
Applications
Subset-sum
Hamiltonian circuit
N-queens
Branch-and-bound
Optimisation problem
minimise or maximise some objective function
satisfies all constraints
feasible and the best value of the objective function
Compared to backtracking
Two additional items
For each node of the state-space tree, a bound
on the best value of the objective function.
The value of the best solution so far
expands based on the best-first
Nodes with bound lower than
best solution so far is pruned
Application
Assignment Problem
Assign n people to n jobs so that the total cost of assignment is as small as possible.
Travelling salesman person
Challenge of defining a good lower/higher bound
It needs to be easy to compute
It cannot be too simple (effect on pruning)
Best-first is not always the best option