| backtracking A scheme for solving a series of sub-problems each of which may have multiple possible solutions and where the solution chosen for one sub-problem may affect the possible solutions of later sub-problems. To solve the overall problem, we find a solution to the first sub-problem and then attempt to recursively solve the other sub-problems based on this first solution. If we cannot, or we want all possible solutions, we backtrack and try the next possible solution to the first sub-problem and so on. Backtracking terminates when there are no more solutions to the first sub-problem. This is the algorithm used by languages such as to find all possible ways of proving a . An optimisation known as "" keeps track of the dependencies between sub-problems and only re-solves those which depend on an earlier solution which has changed. Backtracking is one which can be used to implement . It is effectively a of a . (1995-04-13) |
на заглавную 
к началу страницы