1. 序章


このチュートリアルでは、制約充足問題（CSP）について説明し、それらを解決するための一般的なバックトラッキングアルゴリズムを示します。


2. 制約充足問題








CSPには、既知のドメインを持つ一連の変数と、それらの変数が取ることができる値に制限を課す一連の制約があります。 私たちのタスクは、すべての制約を満たすように各変数に値を割り当てることです。


したがって、CSPを正式に定義するには、次のように指定します。


    

  • 変数のセット 
    • 

  • それらの（有限または無限の）ドメインのセット 
    • 

  • 制約のセット。それぞれに任意の数の変数を含めることができます。

       
    

    • 



2.1. 例


たとえば、数独グリッドの正方形は、変数と考えることができます。 行、列、およびブロックの制約は、単一の関係を介して表すことができます。


      




すべてが互いに異なる場合、それは真実です。 次に、CSPとしての数独には制約があります。


      


2.2. 探索問題としてのCSP


ドメインと変数は一緒になって、完全または部分的なすべての可能な割り当て（ソリューション）のセットを決定します。 すべての制約を満たすものを見つけることは、グラフ内の2つのノード間の最短経路を見つけるような探索問題です。  CSP検索グラフのノードは割り当てを表し、ノードから頂点へのエッジは単一の変数の変化に対応します。


開始ノードは空のソリューションであり、すべての変数が割り当てられていません。 エッジを越えるたびに、1つの変数の値を変更します。 すべての制約を満たす完全な割り当てが見つかると、検索は停止します。 制約満足度チェックは、一般的な検索の目標テストに対応します。


2.3. CSPが古典的な探索問題と完全に似ていない理由


それでも、CSPは従来の探索問題と同じではありません。 2つの主な違いがあります。


まず、変数を設定する順序はCSPでは関係ありません。たとえば、最初に設定したか、数独を解いたかは関係ありません。 対照的に、マップ上の2点間の最短経路を検索する場合は、順序が重要になります。 に移動する前に、まずポイントからに移動する必要があります。 したがって、従来の検索問題の解決策は、順序付けられた一連のアクションですが、CSPの解決策は、任意の順序で実行できる一連の割り当てです。


 2番目の違いは、古典的な検索のソリューションはアルゴリズムの観点からアトミックであるということです。ゴールテストとコスト関数をソリューションに適用しますが、内部構造は検査しません。 一方、 CSPを解くためのアルゴリズムは、解を構成する個々の変数を認識し、それらを1つずつ設定します。


3. 制約グラフ


 CSPとそのソリューションの構造を制約グラフとして視覚化できます。すべての制約がバイナリの場合、グラフのノードはCSP変数を表し、エッジはそれらに作用する制約を表します。


ただし、制約に3つ以上の変数が含まれる場合（この場合、それらをグローバルと呼びます）、制約ハイパーグラフを作成します。 これらには、変数を表す通常のノードと制約を表すハイパーノードの2種類のノードが含まれています。 たとえば、数独には9つの制約があります。 したがって、ハイパーグラフの一部は次のようになります。


制約は単項にすることができます。つまり、単一の変数を制限します。 単項制約とバイナリ制約のみを持つCSPは、バイナリCSPと呼ばれます。 補助変数を導入することで、有限領域変数のグローバル制約を一連のバイナリ制約に変えることができます。したがって、バイナリCSPに焦点を当てることができ、考慮したソルバーを開発する必要はないようです。高次の制約。


ただし、グローバルな制約を処理することで成果を上げることができます。 その理由は、のような制限は、一連のバイナリ制約よりも簡単に実装および理解できるためです。 さらに、グローバル制約の詳細を利用するソルバーは、バイナリ制約と単項制約のみを操作するソルバーよりも効率的です。


4. バックトラッキングソルバー


ここでは、制約を満たすためのバックトラッキングアルゴリズムを紹介します。 空のソリューションから始めて、すべてに値を割り当てるまで変数を1つずつ設定するという考え方です。変数を設定するときは、以前に設定した変数の値と一致する値のみを考慮します。 制約に違反せずに変数を設定できないことに気付いた場合は、前に設定したものの1つに戻ります。 次に、それをそのドメイン内の次の値に設定し、他の割り当てられていない変数を続行します。


変数に値を割り当てる順序は解の正確さに影響しませんが、アルゴリズムの有効性には影響します。変数のドメインで値を試す順序についても同じことが言えます。 。 さらに、変数を設定するたびに、他の変数のどの値が現在の割り当てと矛盾しているかを推測し、サブツリー全体をトラバースせずにそれらを破棄できることがわかります。


4.1. 擬似コード


それを念頭に置いて、擬似コードを示します。




変数選択、値の順序付け、推論を実装する方法は、パフォーマンスにとって非常に重要です。従来の検索では、検索を効率的にガイドする問題固有のヒューリスティックを作成することにより、アルゴリズムを改善しました。 ただし、CSPのバックトラッキングソルバーを高速化するために使用できるドメインに依存しない手法があることがわかりました。


4.2. 推論


最初に推論について話しましょう。 これは、変数をそのドメイン内の値に設定した直後に行うステップです。 制約（ハイパー）グラフで接続されているすべての変数を反復処理し、ドメインから割り当てと矛盾する値を削除します。このようにして、検索ツリーを削除するときに削除します。事前に不可能な割り当て。 この手法は転送チェックとして知られています。 ただし、もっと多くのことができます。


から値を枝刈りするときはいつでも、グラフの隣人に何が起こるかを確認できます。 より具体的には、制約を介して接続されているすべてのものについて、の場合にのみ満たすような値があるかどうかを確認します。 を含む割り当ても不可能であるため、このような値は破棄できます。 ただし、これはすべての制約がバイナリであることを前提としています。


4.3. 変数選択


変数選択の簡単な戦略は、手元のCSPを解く前に、修正した静的な順序で変数を検討することです。 または、次の変数をランダムに選択することもできます。 ただし、これらは効率的な戦略ではありません。ドメイン内に値が1つしかない変数がある場合は、他の値の前に設定するのが理にかなっています。 その理由は、最悪の場合のパフォーマンスを最適化するためです。


最悪のシナリオでは、現在の部分的な割り当てを完了できないため、その割り当ての下のサブツリー全体をトラバースした後、バックトラッキング検索が返されます。 ただし、有効な値が1つしかない変数は、サブツリーの浅いレベルで他の変数と競合し、その不整合を明らかにする可能性が最も高くなります。 一般に、これが最小残存値ヒューリスティック（MRV）の理論的根拠です。  MRVは、ドメインに残っている有効な値が最も少ない変数を選択します。


4.4. バリューオーダー


値の順序付けヒューリスティックは、反対のロジックに従います。 値を設定するときは、のネイバーのドメインから最も少ない値を除外する値を選択する必要があります。 この選択の背後にある直感は、必要なソリューションは1つだけであり、小さなサブツリーよりも大きなサブツリーにそれが含まれる可能性が高いということです。 この戦略を最小制約値ヒューリスティック（LCV）と呼びます。


ある意味で、LCVは、検索ツリーを可能な限り削除するMRVの傾向とバランスを取ります。 両方のヒューリスティックを組み込んだCSPソルバーは、通常、実際には非常に効率的です。 ただし、MRVではCSPがバイナリである必要はありませんが、LCVではバイナリである必要があります。 任意のCSPをバイナリ形式に変換できるため、これは問題ではありません。 ただし、などの高次の制約に作用するカスタムメイドの推論規則を使用する場合は、バックトラッキングソルバーの実行中にCSPの両方の表現を維持する必要があります。


5. 結論


この記事では、制約充足問題を解決するための一般的なバックトラッキングアルゴリズムを紹介しました。 また、ソルバーをより効率的にするためのいくつかのヒューリスティック戦略についても話しました。