Intelligent Backtracking Algorithm

From GM-RKB
(Redirected from Intelligent 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.

See: Logic Programming Language, Optimization Task, Constraint Programming Paradigm, Constraint Satisfaction Algorithm, Blind Search.



References

2017

2008

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.

1977