ABSTRACT
A backtracking algorithm is a recursive method of building up feasible solutions to a combinatorial optimization problem one step at a time. Many combinatorial search problems can be reduced to finding (maximal) cliques in an appropriately chosen graph. In this chapter, the authors present an algorithmic method to estimate the number of nodes in a state space tree for a backtracking algorithm. It is therefore a useful method to predict how long a big backtrack search might take to finish. A more sophisticated method of pruning is to use a bounding function. In the traveling salesman problem, a salesman must visit n cities and return home, doing so in such a way that the cost of the trip is minimized.
