並列論理型言語上の制約充足方式の比較
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,従来から提案されている制約充足問題の解法である(1)単純なバックトラック型の解法,バックトラック型の解法の改良である(2)フォワードチェック型の解法と,近年提案された並列論理型言語向きの,処理の並列性を最大限に引き出すための新しい制約充足問題の解法である(3)レイャードストリーム型の解法の比較を行う.レイャードストリーム型の解法は並列に得られた途中解を併合して解を求めるという,従来の解法と非常に異なった性質を持つが,その処理量,並列度に関する考察が十分なされていなかった.本論文は実験的な評価と統計的モデルを用いた評価により,他の2方式との比較を行い,その性質を明らかにする.実験的な評価で得られた結果は統計的なモデルで示される性質とよく一致しており,以下の新しい結論が導かれた.(a)弱い制約が変数間に均一に存在する問題に対して,並列に得られた途中解を併合するレィャードストリーム型の解法は,複数のプロセスが途中解を共有するため,1つの途中解を生成するための処理畳が少ない.生成する途中解の個数は多いが,全体としての処理量は,バックトラック型の解法よりも少なく,フォワードチェック型の解法と同程度であり,処理の並列性は最も大きい.(b)一方,強い制約が一部の変数間にのみ存在する問題に対して,フォワードチェック型の解法は強い制約を早期に利剛しうるが,レィャードストリーム型の解法は,強い制約の存在により最終的な解の一部となりえない途中解を多く生成し,フォワードチェック型の解法と比較して処理量が多くなる.
- 一般社団法人情報処理学会の論文
- 1991-03-15
著者
関連論文
- 開放型プロダクションシステムにおけるデータ依存関係の管理
- 並列論理型言語GHCとそのプログラミング技術 (「第五世代コンピュータ」)
- GHCのメッセージ指向の並列処理 : 初期評価
- GHCのメッセージ指向の並列処理 : 概要
- GHCのメッセージ指向の処理方式
- GHCプログラムのモード解析
- GHCプログラムの最適化
- 汎用計算機上のGHC処理系
- 並列論理型言語上の制約充足方式の比較
- GHC (Guarded Horn Clauses)
- 第4回ロジックプログラミング国際会議に出席して
- 2. 言語 2.1 並列プログラミング言語 (並列処理技術)
- ATMSを用いた分散制約充足問題の解法
- Michel Raynal : Distributed Algorithms and Protocols, John Wiley & Sons (1988).