Backmarking

From Wikipedia, the free encyclopedia

You have new messages (last change).

In constraint satisfaction, backmarking is a variant of the backtracking algorithm.

Backmarking works like backtracking by iteratively evaluating variables in a given order, for example, x_1,\ldots,x_n. It improves over backtracking by maintaining information about the last time a variable xi was instantiated to a value and information about what changed since then. In particular:

An example, in which search has reached xi=d the first time.
An example, in which search has reached xi=d the first time.
  1. for each variable xi and value a, the algorithm records an information about the last time xi has been set to a; in particular, it stores the minimal index j < i such that the assignment to x_1,\ldots,x_j,x_i was then inconsistent;
  2. for each variable xi, the algorithm stores some information relative to what changed since the last time it has evaluated xi; in particular, it stores the minimal index k < i of a variable that was changed since then.

The first information is collected and stored every time the algorithm evaluates a variable xi to a, and is done by simply checking consistency of the current assignments for x1,xi, for x1,x2,xi, for x1,x2,x3,xi, etc.

When search reaches xi=d for the second time, part of the path is the same as the first time.
When search reaches xi=d for the second time, part of the path is the same as the first time.

The second information is changed every time another variable is evaluated. In particular, the index of the "maximal unchanged variable since the last evaluation of xi" is possibly changed every time another variable xj changes value. Every time an arbitrary variable xj changes, all variables xi with i > j are considered in turn. If k was their previous associated index, this value is changed to min(k,j).

The data collected this way is used to avoid some consistency checks. In particular, whenever backtracking would set xi = a, backmarking compares the two indexes relative to xi and the pair xi = a. Two conditions allow to determine partial consistency or inconsistency without checking with the constraints. If k is the minimal index of a variable that changed since the last time xi was evaluated and j is the minimal index such that the evaluation of x_1,\ldots,x_j,x_i was consistent the last time xi has been evaluated to a, then:

  1. if j < k, the evaluation of x_1,\ldots,x_j,x_i is still inconsistent as it was before, as none of these variables changed so far; as a result, no further consistency check is necessary;
  2. if j \geq k, the evaluation x_1,\ldots,x_k,x_i is still consistent as it was before; this allows for skipping some consistency checks, but the assignment x_1,\ldots,x_i may still be inconsistent.

Contrary to other variants to backtracking, backmarking does not reduce the search space but only possibly reduce the number of constraints that are satisfied by a partial solution.

[edit] Reference

Retrieved from "http://en.wikipedia.org../../../b/a/c/Backmarking.html"