Backtracking
Prabodh C P
Asst Professor,
Dept of CSE,
SIT, Tumkur
Creative Commons Attribution-ShareAlike 4.0 International Public License
Backtracking
How to Tackle intractable Problems?
Use a strategy that guarantees solving the problem exactly but doesn’t
guarantee to find a solution in polynomial time.
Exhaustive Search (brute force)
Generate ALL candidate solutions and identify one with a desired
property
useful only for small instances
2
Backtracking
Improvement over exhaustive search: backtracking
The principal idea is to construct solutions one component at a time
and evaluate such partially constructed candidates as follows.
If a partially constructed solution can be developed further without
violating the problem’s constraints, it is done by taking the first
remaining legitimate option for the next component.
If there is no legitimate option for the next component, no
alternatives for any remaining component need to be considered.
In this case, the algorithm backtracks to replace the last component
of the partially constructed solution with its next option.
3
Backtracking
Construct the state space tree:
Root represents an initial state before the search for a solution
begins.
Nodes reflect specific choices made for a solution’s components.
Promising and nonpromising nodes
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.
leaves
4
Backtracking
Explore the state space tree using depth-first search
“Prune” non-promising nodes
DFS stops exploring subtree rooted at nodes leading to no
solutions and...
“backtracks” to its parent node
5
N Queens Problem
Place n queens on an n by n chess board so
that no two of them are on the same row,
column, or diagonal
6
State Space Tree of the Four-queens Problem
7
Sub Set Sum problem
find a subset of a given set A = {a1 , a2 . . . , an } of n positive
integers whose sum is equal to a given positive integer d.
For example, for A = {1, 2, 5, 6, 8} and d = 9, there are two
solutions:
{1, 2, 6} and {1, 8}.
The elements of the set should be arranged in ascending order
8
Sub Set Sum problem
A = {3, 5, 6, 7} and d = 15
Solution - {3,5,7}
9
Sub Set Sum problem (D = 6) S={1,2,3,4}
3
2 2
1 1 1
4
2 2 2
1 1 1
10
Sub Set Sum problem (D = 6) S={1,2,3,4}
4
3 3
1 1 1
3 4
1 1 1
11
Sub Set Sum problem (D = 6) S={1,2,3,4}
4
3
1 2 2
3 4
2 2 2
12
Sub Set Sum problem (D = 6) S={1,2,3,4}
2 3
4
3 3
13
Sub Set Sum problem (D = 6) S={1,2,3,4}
14
Hamiltonian Circuit Problem
Consider the problem of finding a Hamiltonian circuit in the
graph
Without loss of generality, we can assume that if a Hamiltonian
circuit exists, it starts at vertex a.
We construct a state space tree with vertex a as the root.
15
Hamiltonian Circuit Problem
After we have chosen a as the start vertex of our Hamiltonian
Circuit, we are supposed to find the remaining n-1 vertices in the
Hamiltonian circuit, one intermediary vertex at a time.
Ties can be resolved by using the alphabetic order.
Whrn we have found out n-1 intermediary vertex and if we can
reach to the start vertex from the last intermediary vertex we
have found out a Hamiltonian Circuit.
Otherwise if we reach a dead end we backtrack to the previously
visited vertex and continue exploring other paths.
Backtracking eventually terminates at the start vertex.
16
Hamiltonian Circuit Problem State Space Tree
17