Backtracking

The term reset method or English backtracking ( backtracking ) refers to a method of problem solving within the algorithms.

General algorithm

Backtracking going on after the trial-and- error approach ( trial and error ), that is, an attempt is made to develop an achieved partial solution to a complete solution. If it is foreseeable that a partial solution can not lead to a final settlement, is the final step or be withdrawn its last steps, and it will instead try alternative ways. In this way it is ensured that all can be tested in candidate solutions (the principle of Ariadne thread ). With backtracking algorithms an existing solution is either found (possibly after a very long run time), or it can be definitely stated that no solution exists. Backtracking is usually implemented recursively and easiest is a prototypical application of recursion.

Find function solution (step, vector)    1 repeat, as long as there are new partial solution steps:       a) choose a new partial solution step;       b) if the election is valid:                 I) extend vector about choice;                Ii) if vector is complete, return true; / / Solution found!                    otherwise:                         if ( find solution (level 1, vector) ) return true; / / Solution!                         otherwise make deselect it; / / Dead end ( backtracking )!    2 Since there is no new sub - step solution: return false / / No solution! time complexity

In the depth-first search be made ​​at the maximum possible ramifications of each partial solution and a solution tree with maximum depth of expanded nodes in the worst case.

Depth-first search and thus backtracking have in the worst case with an exponential runtime. In large search depth and degree of branching the search thus often takes a long time. Therefore, the backtracking is primarily suitable for problems with a small solution tree.

However, there are methods by which the time complexity of a backtracking algorithm can be reduced. These include:

• Heuristics
• Acceptance of approximate solutions and error tolerance
• Average amount of input

Examples

Known issues that can be solved with backtracking, include:

Many of these problems are NP-complete.

PROLOG

The programming language Prolog uses backtracking to answer generation. Here, the interpreter tries all possibilities evidence sequentially through. Decision points are referred to as ChoicePoint. The so-called cut- operator! can be used to discard choice points.