並列論理型言語上の制約充足方式の比較

IPSJ

Bibliographic Information

Other Title
  • Comparison of Constraint Satisfaction Methods in Concurrent Logic Programming
  • 並列論理言語

Search this article

Abstract

本論文では 従来から提案されている制約充足問題の解法である(1)単純なバックトラック型の解法 バックトラック型の解法の改良である(2)フォワードチェック型の解法と 近年提案された並列論理型言語向きの 処理の並列性を最大限に引き出すための新しい制約充足問題の解法である(3)レイャードストリーム型の解法の比較を行うレイャードストリーム型の解法は並列に得られた途中解を併合して解を求めるという 従来の解法と非常に異なった性質を持つが その処理量 並列度に関する考察が十分なされていなかった本論文は実験的な評価と統計的モデルを用いた評価により 他の2方式との比較を行い その性質を明らかにする実験的な評価で得られた結果は統計的なモデルで示される性質とよく一致しており 以下の新しい結論が導かれた(a)弱い制約が変数間に均一に存在する問題に対して 並列に得られた途中解を併合するレィャードストリーム型の解法は 複数のプロセスが途中解を共有するため 1つの途中解を生成するための処理畳が少ない生成する途中解の個数は多いが 全体としての処理量は バックトラック型の解法よりも少なく フォワードチェック型の解法と同程度であり 処理の並列性は最も大きい(b)一方 強い制約が一部の変数間にのみ存在する問題に対して フォワードチェック型の解法は強い制約を早期に利剛しうるが レィャードストリーム型の解法は 強い制約の存在により最終的な解の一部となりえない途中解を多く生成し フォワードチェック型の解法と比較して処理量が多くなる

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top