Intelligent Backtracking Algorithm
(Redirected from Dependency Directed Backtracking)
Jump to navigation
Jump to search
An Intelligent Backtracking Algorithm is a Constraint Satisfaction Algorithm based on informed search that backtracks an unsolvable search problem to a previous solvable search problem.
- AKA: Dependency Directed Backtracking.
- Example(s):
- Counter-Example(s):
See: Logic Programming Language, Optimization Task, Constraint Programming Paradigm, Constraint Satisfaction Algorithm, Blind Search.
References
2017
- (Sammut & Webb, 2017) ⇒ (2017) "Intelligent Backtracking". In:(Sammut & Webb, 2017)
- QUOTE: Intelligent backtracking is a general class of techniques used to enhance search and constraint satisfaction algorithms. Backtracking is a general mechanism in search where a problem solver encounters an unsolvable search state and backtracks to a previous search state that might be solvable. Intelligent backtracking mechanisms provide various ways of selecting the backtracking point based on past experience in a way that is likely to be fruitful.
2008
- (Jones, 2008) ⇒ M. Tim Jones. (2008). “Artificial Intelligence: A Systems Approach." Jones & Bartlett. ISBN:0763773379
- The backtracking algorithm operates with a simple uninformed search algorithm, such as depth-first search. At each node, a variables is instantiated with a value and the constraint violations are checked. If the values are legal, search is permitted to continue, otherwise, the current branch is abandoned and the next node from the OPEN list is evaluated.
1992
- (Kumar,1992) ⇒ Vipin Kumar (1992). "Algorithms for constraint-satisfaction problems: A survey" (PDF). AI magazine, 13(1), 32.
- QUOTE: There is a backtracking-based method that eliminates both of these drawbacks to backtracking. This method is traditionally called dependency-directed backtracking (Stallman and Sussman 1977) and is used in truth maintenance systems (Doyle 1979; McDermott 1991). CSP can be solved by Doyle's RMS (Doyle 1979; Stallman and Sussman 1977), as follows: A variable is assigned some value, and a justification for this value is noted (the justification is simply that no justification exists for assigning other possible values). Then, similarly, a default value is assigned to some other variable and is justified. At this time, the system checks whether the current assignments violate any constraint. If they do, then a new node is created that essentially denotes that the pair of values for the two variables in question is not allowed. This node is also used to justify another value assignment to one of the variables. This process continues until a consistent assignment is found for all the variables. Such a system, if implemented in full generality, never performs redundant backtracking and never repeats any computation.
Although the amount of search performed by such a system is minimal, the procedures for determining the culprit of constraint violation and choosing a new value of the variables are complex (Petrie 1987). Hence, overall the scheme can take more time than even simple backtracking for a variety of problems.
- QUOTE: There is a backtracking-based method that eliminates both of these drawbacks to backtracking. This method is traditionally called dependency-directed backtracking (Stallman and Sussman 1977) and is used in truth maintenance systems (Doyle 1979; McDermott 1991). CSP can be solved by Doyle's RMS (Doyle 1979; Stallman and Sussman 1977), as follows: A variable is assigned some value, and a justification for this value is noted (the justification is simply that no justification exists for assigning other possible values). Then, similarly, a default value is assigned to some other variable and is justified. At this time, the system checks whether the current assignments violate any constraint. If they do, then a new node is created that essentially denotes that the pair of values for the two variables in question is not allowed. This node is also used to justify another value assignment to one of the variables. This process continues until a consistent assignment is found for all the variables. Such a system, if implemented in full generality, never performs redundant backtracking and never repeats any computation.
1977
- (Stallman & Sussman, 1977) ⇒ Richard M. Stallman and Gerald Jay Sussman (1976, 1977). "Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis. Artificial Intelligence, 9, 13500196. AIM-380
- QUOTE: The style of analysis performed by EL, which we call the method of propagation of constraints. Propagation requires the introduction and manipulation of some symbolic quantities. Though the system has routines for symbolic algebra, symbolic manipulation, they can handle only linear relationships. Nonlinear devices such as transistors are represented by piecewise-linear models that cannot be used symbolically; they can be applied only after one has guessed (advice) a particular operating region for each nonlinear device in the circuit. Trial-and-error can find the right regions but this method of assumed states Is potentially combinatorially explosive. ARS supplies dependency-directed backtracking, a scheme which limits the search as follows: The system notes a contradiction when it attempts to solve an impossible algebraic relationship, or when discovers that transistor's operating point is not within the possible range for its assumed region. The antecedents of the contradictory facts are scan to find which nonlinear devise state guesses (more generally, the backtrackable choicepoints) are relevant; ARS never tries that combination of guesses again. A short list of relevant choicepoints eliminates from consideration a large number of combination of answers to all the other (irrelevant) choices. This is how the justifications (or dependency records) are used to extract and retain more information from each contradiction than a chronological backtracking system …