MACC'97 一般セッション（分散制約充足）論文
マルチエージェントシステムにおける多くの問題は分散制約充足問題（分散 CSP）として記述可能である. 分散CSPの目標はすべての制約を満たす解を得る ことであるが, 現実の問題においては，それを分散CSPとして記述したときに 過制約で解が存在しないということがよくある．本論文では, 過制約な分散 CSPを扱うことができる新しい枠組として分散不完全制約充足問題（分散不完 全CSP）を提案する. さらに, 分散不完全CSPの重要な部分クラスの一つとして 分散最大CSPを提案し，それを解くアルゴリズムである同期型分枝限定法と反 復分散ブレイクアウト法を開発する. 過制約なランダムバイナリ分散CSPを用 いたアルゴリズムの性能評価実験では, 最適解を得るには同期型分枝限定法が, 低コストで準最適解を得るなら反復分散ブレイクアウト法が適していることが 示される.
分散問題解決，制約充足
論文PSファイル(+gzip)