Backmarking

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 $x_{i}$ 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.

for each variable $x_{i}$ and value $a$ , the algorithm records information about the last time $x_{i}$ 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;
for each variable $x_{i}$ , the algorithm stores some information relative to what changed since the last time it has evaluated $x_{i}$ ; 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 $x_{i}$ to $a$ , and is done by simply checking consistency of the current assignments for $x_{1},x_{i}$ , for $x_{1},x_{2},x_{i}$ , for $x_{1},x_{2},x_{3},x_{i}$ , etc.

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 $x_{i}$ " is possibly changed every time another variable $x_{j}$ changes value. Every time an arbitrary variable $x_{j}$ changes, all variables $x_{i}$ 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 $x_{i}=a$ , backmarking compares the two indexes relative to $x_{i}$ and the pair $x_{i}=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 $x_{i}$ 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 $x_{i}$ has been evaluated to $a$ , then:

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;
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.

References

Dechter, Rina (2003). Constraint Processing. Morgan Kaufmann. ISBN 1-55860-890-7.

This article is issued from Wikipedia - version of the 8/14/2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.