併合法による制約充足の並列化効果について

スポンサーリンク

概要

論文の詳細を見る
制約充足問題(以下CSPと略記)が解を有するかどうかを決定する問題は、NP完全問題のクラスに属しており、その意味で効率のよい汎用アルゴリズムは存在しないと予想される。したがって、具体的な応用問題ごとに、その特徴を生かした解法を開発する心要がある。組合せ探索問題においては、並列処理の研究が盛んに行われている。分割統治を応用した並列化はその例である。CSPの解法の1つとして、制約間の関係を表す制約グラフ上で、制約の整合化を繰り返す方法、すなわち併合法があるが、併合法も割統治を応用して並列処理できる。しかし、分割統治による並列化は、CSPにおいて心ずしも有効とは限らないことが実験によって明らかにされている。本稿では、CSPの解法の1つである併合法を、分割統治を応用として並列化する効果について考察する。
1993-03-01

著者

関連論文

もっと見る

スポンサーリンク