Backtracking

Abstract Backtracking search algorithms are commonly used to solve a wide range of decision and optimization problems. Backtracking has the advantage of potentially requiring a search tree with less nodes, when compared with a brute force algorithm. For further reducing the search tree size, constraint propagation can be used to remove inconsistent assignments. In addition, when solving optimization problems, backtracking may be adapted to take into account the value of the objective function. As soon as a partial assignment cannot be extended to a solution that is better than the best solution found so far, the algorithm backtracks. Another technique used to improve backtracking performance is learning. Learning is performed whenever a conflict is found, and it serves to prevent similar conflicts in the future. Learning may also be used to backtrack nonchronologically, thus not exploring irrelevant parts of the search tree.