分散制約充足問題における制約緩和
情報処理学会論文誌, Vol.36, No.2. pp. 275--282, 1995.


分散制約充足問題は 分散協調問題解決の様々な問題を表現できる枠組として近年注目を集めている. 本論文では, 制約の重要度という概念を導入して分散制約充足問題の枠組の拡張を行い, 制約が強過ぎて解が存在しない過制約である分散制約充足問題に関して, 制約を部分的に満たす解の定式化を行う. さらに, 制約充足問題を解くアルゴリズムである非同期バックトラッキング アルゴリズムを繰り返し適用して, 重要度の低い制約を段階的に緩和するアルゴリズム (非同期段階緩和アルゴリズム)により, 定義された基準で最適な解を求めることが可能であることを示す.

本アルゴリズムでは, 通常の逐次的なバックトラッキングアルゴリズムとは対照的に, エージェントは非同期に並行して動作するが, アルゴリズムの完全性, 解の最適性は保証される. さらに, 本アルゴリズムにおいて, 制約条件違反(nogood)と制約との間の依存関係を管理することにより, 無駄な計算を避けることができ, 例題において5倍程度の速度向上が得られることを示す.