Backmarking

☆ Save On Wikipedia ↗

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 , … , x n {\displaystyle x_{1},\ldots ,x_{n}} {\displaystyle x_{1},\ldots ,x_{n}}. It improves over backtracking by maintaining information about the last time a variable x i {\displaystyle x_{i}} {\displaystyle x_{i}} was instantiated to a value and information about what changed since then. In particular:

An example, in which search has reached x i = d {\displaystyle x_{i}=d} {\displaystyle x_{i}=d} the first time.
  1. for each variable x i {\displaystyle x_{i}} {\displaystyle x_{i}} and value a {\displaystyle a} {\displaystyle a}, the algorithm records information about the last time x i {\displaystyle x_{i}} {\displaystyle x_{i}} has been set to a {\displaystyle a} {\displaystyle a}; in particular, it stores the minimal index j < i {\displaystyle j<i} {\displaystyle j<i} such that the assignment to x 1 , … , x j , x i {\displaystyle x_{1},\ldots ,x_{j},x_{i}} {\displaystyle x_{1},\ldots ,x_{j},x_{i}} was then inconsistent;
  2. for each variable x i {\displaystyle x_{i}} {\displaystyle x_{i}}, the algorithm stores some information relative to what changed since the last time it has evaluated x i {\displaystyle x_{i}} {\displaystyle x_{i}}; in particular, it stores the minimal index k < i {\displaystyle k<i} {\displaystyle 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 {\displaystyle x_{i}} {\displaystyle x_{i}} to a {\displaystyle a} {\displaystyle a}, and is done by simply checking consistency of the current assignments for x 1 , x i {\displaystyle x_{1},x_{i}} {\displaystyle x_{1},x_{i}}, for x 1 , x 2 , x i {\displaystyle x_{1},x_{2},x_{i}} {\displaystyle x_{1},x_{2},x_{i}}, for x 1 , x 2 , x 3 , x i {\displaystyle x_{1},x_{2},x_{3},x_{i}} {\displaystyle x_{1},x_{2},x_{3},x_{i}}, etc.

When search reaches x i = d {\displaystyle x_{i}=d} {\displaystyle x_{i}=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 {\displaystyle x_{i}} {\displaystyle x_{i}}" is possibly changed every time another variable x j {\displaystyle x_{j}} {\displaystyle x_{j}} changes value. Every time an arbitrary variable x j {\displaystyle x_{j}} {\displaystyle x_{j}} changes, all variables x i {\displaystyle x_{i}} {\displaystyle x_{i}} with i > j {\displaystyle i>j} {\displaystyle i>j} are considered in turn. If k {\displaystyle k} {\displaystyle k} was their previous associated index, this value is changed to m i n ( k , j ) {\displaystyle min(k,j)} {\displaystyle min(k,j)}.

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

  1. if j < k {\displaystyle j<k} {\displaystyle j<k}, the evaluation of x 1 , … , x j , x i {\displaystyle x_{1},\ldots ,x_{j},x_{i}} {\displaystyle 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 ≥ k {\displaystyle j\geq k} {\displaystyle j\geq k}, the evaluation x 1 , … , x k , x i {\displaystyle x_{1},\ldots ,x_{k},x_{i}} {\displaystyle 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 , … , x i {\displaystyle x_{1},\ldots ,x_{i}} {\displaystyle 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