|
In this article:
- What is backtracking
- Implementation of backtracking
- Uses of backtracking
What is Backtracking
The term backtracking, first used by the American mathematician D.H. Lehmer in the 1950s, is an approach that helps find solutions to constraint satisfaction problems.
Constraint satisfaction problems or CSPs are a type of mathematical problems that require a person to find objects that fulfill a number of constraints, that is, certain criteria. They have very high importance in the field of artificial intelligence and operations research. Solving of CSPs in the least possible amount of time (to make such solving economical) requires the use of heuristics and combinational search methods. A typical feature of these problems is that they have a single, complete solution in which the order of the elements they contain does not have any effect on the solution. A set of variables are assigned a certain value which is based on the constraints that affect the problem. By backtracking, all possible combinations of these variables are tried to reach to the solution of the problem.
Implementation of Backtracking
For the purpose of implementing backtracking, a depth-first search is performed on the possible solutions. When the search is being performed and a point is reached where the current alternative being analyzed doesn’t work (that is, it is not a solution), we return to the starting point where we were provided with various alternatives. This coming back to the starting point is what gives ‘backtracking’ its name. Then, we run with the new set of values as present in the next alternative. This process is repeated until either a solution to the problem has been reached or there are no further alternatives left (which would mean that the search failed).
Since this is a repetitive series of steps, it is beneficial to implement this with the help of a recursive function. Backtracking is better than a depth-first search in that it uses lesser amount of space since it keeps into record only the current state of the problem and simply updates it with new variable values as required.
There are several techniques that may be put to use in order to speed up the whole process. A common practice is to try and run the most constrained variables first (those that have the least number of value options). This is possible as the variable order does not affect the ultimate result in a CSP. Due to this, it is possible that the solution to the problem is reached at an early stage of testing itself.
Certain implementations make use of bounding functions that help determine if a partial solution can lead to a complete solution of the problem. If it is found that the partial solution cannot lead to a complete solution, it is discarded without testing any further. Such bounding functions need to be very efficient so as to make the backtracking function more efficient in turn.
Since backtracking needs to keep record of the current condition of the problem as well as the variables, implementations of backtracking maintain a variable trail that store the change history. This is a general but small overhead of all backtracking implementations. However, there exists alternative ways to a variable trail. An example is that of a time stamp which stores the data about when the most current change to the value of the variable was made. This time stamp is then compared to a similar time stamp of the point where we were provided with alternatives. If the time at this point is greater than the first one (that is, it is more recent), then no changes are made to the variable.
Uses of Backtracking
Backtracking has been used for various purposes. The most common usage is to execute common expressions or regular expressions such as an operation like a*a. Parsing is also achieved with the help of backtracking. Some programming languages (like Prolog) make widespread usage of backtracking.
|
