BackTracking : Elimination for the Optimal

As suggested by one of my friends, I would cover some of the algorithms here as part of my preparation for upcoming end-sem exams. So I start with Backtracking, the general algorithm which incrementally builds candidates of optimal solution while discarding every partial-candidate that wouldn’t lead to a valid solution. The term “backtrack” was coined by an American mathematician D. H. Lehmer in the 1950s.

Quite popular example of its application is the 8-queens puzzle where all partial-candidates with two mutually attacking queens are discarded. Other examples include crosswords, Sudoku, knapsack problem etc.

For any problem which accepts the concept of a “partial candidate solution” and provides a quick test of whether it could lead us to the accepted solution, the ‘Backtracking’ algorithm can be applied. It will not work for any problem out of the set defined in previous statement. But when applicable, it eliminates a large number of candidates with single test, thus offering a much faster calculation than the brute force.

The Backtracking Tree Concept
Backtracking Tree for 4-Queens Problem

Backtracking Tree for 4-Queens Problem

In Backtracking, each partial candidate is represented as a node of a Tree. For any node N, the parent node represents the partial candidate from which N has been obtained by incrementing it by one element. This creates a unidirectional graph with no circuits i.e. a tree. The leaves of this tree are the partial candidates that can’t be extended any further (because either they have been discarded or they are a valid candidate for the optimal solution).

Backtracking algorithm traverses this tree recursively in Depth-First order. If the value at any node does not satisfy the constraints, the node along with its sub-tree is discarded and the algorithm moves on to the next candidate. If it does, then the algorithm checks for it being a valid solution. Any valid solution is reported to the user. If neither of the above conditions come true, then it simply explores the sub-tree of that node.

So, the tree actually searched for valid solution is just a subset of the potential tree. This reduces the total cost of algorithm to the number of nodes in the actual tree instead of the potential tree.

Pseudo-Code

I would like to refer to Wikipedia… they have an easy one. Just click here…

Advertisements