Backtracking

"

Backtracking algorithms try each possibility until they find the right one. It is a depth-first search of the set of possible solutions. During the search, if an alternative doesn't work, the search backtracks to the choice point, the place which presented different alternatives, and tries the next alternative. When the alternatives are exhausted, the search returns to the previous choice point and tries the next alternative there. If there are no more choice points, the search fails.

This is usually achieved in a recursive function where each instance takes one more variable and alternatively assigns all the available values to it, keeping the one that is consistent with subsequent recursive calls. Backtracking is similar to a depth-first search but uses even less space, keeping just one current solution state and updating it.

In order to speed up the search, when a value is selected, before making the recursive call, the algorithm either deletes that value from conflicting unassigned domains (forward checking) or checks all the constraints to see what other values this newly-assigned value excludes (constraint propagation). This is the most efficient technique for certain problems like 0/1 knapsack and n-queen problem. It gives better results than dynamic programming for these problems.

資料來源:http://en.wikipedia.org/wiki/Backtracking

[@more@]"