Backtracking
Backtracking refers to a scheme for solving a problem by solving a series of constituent sub-problems. Each of the sub-problems has a number of possible solutions, and a solution chosen affects the possible solutions of the remaining sub-problems.
Backtracking algorithms date back to 1965, when Colomb and Baumert published the first algorithm. In 1983, Allen proposed that backtracking could be adapted for use to explore the logical computational solving of problems.
The fact that there can be more than one solution to a computational problem is known as nondeterminism. Backtracking is essential for the operation of a nondeterministic algorithm, that is, solving a problem that can have multiple solutions. Diagramming the possible combinations of sub-problems having multiple, possible solutions produces a tree-like image, with branches representing the possible paths of the various solutions. Thus, backtracking is described as a means of solving problems with tree structures. Negotiating through the tree can produce three solutions-- a path, all paths, and the shortest path--depending on the algorithm invoked to solve the problem, and on the nature of the problem itself. Typically the first choice for a solution will be the "just a path" approach. The shortest path option is possible only when all the paths, that is, all the possible solutions and their combinations, are known.
In backtracking, the solution to the problem is sought by finding a solution to one of the problems and then attempting to recursively solve the other sub-problems based on this initial solution. If the initial solution cannot be obtained, or if the simultaneous solution of all problems is desired, then a backtracking from the first selected sub-problem to the next is attempted. If this is unsuccessful, backtracking to the next sub-problem is tried and so on. Backtracking stops when there are no more solutions to the first sub-problem.
The backtracking scheme forms the basis of an algorithm used by logic programming languages--in which so-called goals invoked to solve a problem are dependent on goals that precede it--such as Prolog. The algorithm is designed to find all possible ways of proving a goal; in other words, to find all the possible combinations that will solve the problem at hand. If the choice of a sub-problem solution proves to be incorrect, the computation backtracks or restarts at the sub-problem and tries another choice.
In the Prolog programming language, a refinement of backtracking called intelligent backtracking keeps track of all the possible combinations of the inter-related sub-problem solutions. If the solutions to a problem change, intelligent backtracking adjusts other sub-problems and overall problem solutions accordingly. This behavior is known as recursion, and means that the computations must be reversible. Hence, the solution pathways must be saved. The pattern followed would be similar to the following example:
- check if the goal is achieved
- repeat
- check if the next step is possible
- check if the next step leads to a known position that is different from the preceding
- do this next step
This sequence is followed until the problem is solved, or until a computational roadblock is reached. If a roadblock occurs, backtracking is invoked and the sequence is repeated using another pathway.
This is the complete article, containing 511 words
(approx. 2 pages at 300 words per page).
