Backtracking


  Backtracking.ppt (Size: 11 KB / Downloads: 0)

A systematic way to iterate through all the possible configurations of a search space.
Solution: a vector a = (a1,a2,…,an)
At each step, we start from a given partial solution, say, a=(a1,a2,…,ak), and try to extend it by adding another element at the end.
If so, we should count (or print,…) it.
If not, check whether possible extension exits.
If so, recur and continue
If not, delete ak and try another possibility.

Pruning Search

To make a backtracking program efficient enough to solve interesting problems, we must prune the search space by terminating for every search path the instant that is clear not to lead to a solution.