制約満足問題 (CSP) におけるアーク整合性 (Arc Consistency) とバックトラッキング探索の活用
制約満足問題 (CSP) は、複数の変数とその値に対する制約が与えられた問題を解くための重要なアプローチです。本記事では、アーク整合性 (AC3 アルゴリズム) とバックトラッキング探索を活用して、効率的に CSP を解く方法を詳しく説明します。
1. アーク整合性 (Arc Consistency) の概要
アーク整合性とは、制約グラフにおいて、ある変数の値が他の変数の値と一致する可能性があるかを確認し、不整合な値を削除する手法です。この手法により、変数のドメインを削減し、探索空間を狭めることで効率的な探索が可能になります。
アーク整合性の仕組み
- 変数 ( X ) のドメイン内のすべての値について、隣接する変数 ( Y ) のドメインに少なくとも1つの値が一致するようにします。
- 一致しない場合、その値を ( X ) のドメインから削除します。
AC3アルゴリズム
以下は、AC3アルゴリズムの基本手順です：
-
初期化:
制約グラフのすべてのアークをキューに追加します。 -
アーク整合性の確認:
- キューからアーク ( (X, Y) ) を取り出し、アーク整合性を確認。
- ( X ) のドメインから不整合な値を削除。
-
隣接アークの再確認:
- ( X ) のドメインが変更された場合、( X ) に関連する他のアークをキューに追加。
-
終了条件:
- キューが空になれば終了。
2. バックトラッキング探索
バックトラッキング探索は、CSPの解を見つけるための再帰的な手法です。変数に値を割り当てる際に制約を満たしていない場合は、割り当てを「バックトラック」してやり直します。
基本のバックトラッキング手法
バックトラッキングの流れは以下の通りです：
-
初期状態:
すべての変数が未割り当て。 -
変数の選択:
未割り当ての変数を1つ選択。 -
値の割り当て:
選択した変数にドメインの値を1つ試す。 -
制約のチェック:
現在の割り当てが制約を満たしていれば次へ進む。 -
失敗時の処理:
制約を満たさない場合は、割り当てを取り消して他の値を試す。 -
再帰的探索:
すべての変数に値を割り当てた場合は解を返す。
アルゴリズム
def backtrack(assignment, problem):
if is_complete(assignment, problem):
return assignment
var = select_unassigned_variable(assignment, problem)
for value in order_domain_values(var, assignment, problem):
if is_consistent(var, value, assignment, problem):
assignment[var] = value
result = backtrack(assignment, problem)
if result is not None:
return result
del assignment[var]
return None
3. アーク整合性とバックトラッキングの統合
アーク整合性をバックトラッキングと組み合わせることで、探索の効率を大幅に向上させることができます。
- 事前整合性: 問題を探索する前に、AC3で初期のドメインを縮小。
- 逐次整合性: 新しい変数に値を割り当てた際、関連するアークについて整合性を再チェック。
改良されたバックトラッキング探索
以下は、アーク整合性を組み込んだバックトラッキング探索です：
def backtrack_with_arc_consistency(assignment, problem):
if is_complete(assignment, problem):
return assignment
var = select_unassigned_variable(assignment, problem)
for value in order_domain_values(var, assignment, problem):
if is_consistent(var, value, assignment, problem):
assignment[var] = value
if ac3(problem, var): # アーク整合性を確認
result = backtrack_with_arc_consistency(assignment, problem)
if result is not None:
return result
del assignment[var]
return None
4. CSPにおけるヒューリスティクス
効率的な探索を行うために、以下のヒューリスティクスを活用します：
-
最小残余値 (MRV):
- ドメインが最小の変数を優先的に選択。
- 制約の影響が大きい変数を先に処理。
-
最大制約次数 (Degree Heuristic):
- 他の変数に最も多く影響を与える変数を選択。
-
最小制約値 (Least Constraining Value):
- 他の変数のドメインを最小限に減らす値を優先。
5. 実践例：試験スケジューリング
問題設定
- 7つのクラス (A～G) に対し、月～水曜日の3つの試験スロットを割り当てる。
- 制約: 同じ日に複数の試験を受けられない。
結果
バックトラッキング探索をAC3と組み合わせた結果：
-
解: 各クラスの試験日を次のように割り当てた。
- A: 月曜日
- B: 火曜日
- C: 水曜日
- D: 水曜日
- E: 月曜日
- F: 火曜日
- G: 水曜日
まとめ
アーク整合性とバックトラッキング探索を組み合わせることで、CSPを効率的に解くことが可能です。さらに、ヒューリスティクスを活用することで探索を最適化できます。これらの技術を適用することで、現実世界の複雑な制約問題を効果的に解決できます。