バックマーキング

制約充足において、バックマーキングはバックトラッキングアルゴリズムの変形です。

バックマーキングは、例えば、変数を指定された順序で反復的に評価することで、バックトラッキングと同様に機能します。バックマーキングは、変数が最後に値にインスタンス化された時刻と、それ以降の変更内容に関する情報を保持する点で、バックトラッキングよりも優れています。具体的には、 ${\displaystyle x_{1},\ldots,x_{n}}$ ${\displaystyle x_{i}}$

検索が初めて到達した例。${\displaystyle x_{i}=d}$

1. 各変数および値について、アルゴリズムはが に設定された最後の時刻に関する情報を記録します。特に、への割り当てがに矛盾していた最小のインデックスを 保存します。${\displaystyle x_{i}}$ ${\displaystyle a}$ ${\displaystyle x_{i}}$ ${\displaystyle a}$ ${\displaystyle j<i}$ ${\displaystyle x_{1},\ldots,x_{j},x_{i}}$
2. 各変数について、アルゴリズムは、前回の評価以降に変更された内容に関する情報を保存します。特に、それ以降に変更された変数の最小インデックスを保存します。${\displaystyle x_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle k<i}$

最初の情報は、アルゴリズムが変数を に評価するたびに収集され、保存されます。これは、、、 など の現在の割り当ての一貫性を単にチェックすることによって行われます。${\displaystyle x_{i}}$ ${\displaystyle a}$ ${\displaystyle x_{1},x_{i}}$ ${\displaystyle x_{1},x_{2},x_{i}}$ ${\displaystyle x_{1},x_{2},x_{3},x_{i}}$

2 回目に検索が到達すると、パスの一部は 1 回目と同じになります。${\displaystyle x_{i}=d}$

2番目の情報は、他の変数が評価されるたびに変更されます。特に、「 の最後の評価以降に変化していない最大の変数」のインデックスは、他の変数の値が変化するたびに変更される可能性があります。任意の変数が変化するたびに、を持つすべての変数が順番に考慮されます。が以前の関連付けられたインデックスであった場合、この値は に変更されます。 ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{i}}$ ${\displaystyle i>j}$ ${\displaystyle k}$ ${\displaystyle min(k,j)}$

この方法で収集されたデータは、いくつかの整合性チェックを回避するために使用されます。特に、バックトラッキングによって が設定される場合は常に、バックマークによってと のペアに対する2つのインデックスが比較されます。2つの条件により、制約をチェックすることなく、部分的な整合性または不整合を判断できます。 が前回の評価以降に変更された変数の最小インデックスであり、 が前回の評価で の評価が と整合していた最小インデックスである場合、次の式が成り立ちます。 ${\displaystyle x_{i}=a}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}=a}$ ${\displaystyle k}$ ${\displaystyle x_{i}}$ ${\displaystyle j}$ ${\displaystyle x_{1},\ldots,x_{j},x_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle a}$

1. の場合、これらの変数はいずれもこれまで変更されていないため、 の評価は以前と同様に矛盾したままです。したがって、それ以上の一貫性チェックは必要ありません。${\displaystyle j<k}$ ${\displaystyle x_{1},\ldots,x_{j},x_{i}}$
2. の場合、評価は以前と同様に一貫しています。これにより、一部の一貫性チェックをスキップできますが、割り当ては依然として矛盾する可能性があります。${\displaystyle j\geq k}$ ${\displaystyle x_{1},\ldots,x_{k},x_{i}}$ ${\displaystyle x_{1},\ldots,x_{i}}$

バックトラッキングの他のバリエーションとは異なり、バックマーキングでは検索空間は縮小されませんが、部分的な解決によって満たされる制約の数のみが縮小される可能性があります。

参考文献

• デヒター、リナ（2003年）『制約処理』モーガン・カウフマン著、ISBN 1-55860-890-7。