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

• Item type: Journal(1)
• 公開日: 1991-03-15
• タイトル: 並列論理型言語上の制約充足方式の比較
• タイトル / 言語: en
• タイトル: Comparison of Constraint Satisfaction Methods in Concurrent Logic Programming
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 並列論理言語
• 著者所属: NTT情報通信処理研究所
• 著者所属: （財）新世代コンピュータ技術開発機構
• 著者所属(英): en
• 著者所属(英): NTT Communications and Information Processing Laboratories
• 著者所属(英): en
• 著者所属(英): Institute for New Generation Computer Technology
• 著者名: 横尾, 真; 上田, 和紀
• 著者名(英): Makoto, Yokoo; Kazunori, Ueda
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では 従来から提案されている制約充足問題の解法である(1)単純なバックトラック型の解法 バックトラック型の解法の改良である(2)フォワードチェック型の解法と 近年提案された並列論理型言語向きの 処理の並列性を最大限に引き出すための新しい制約充足問題の解法である(3)レイャードストリーム型の解法の比較を行うレイャードストリーム型の解法は並列に得られた途中解を併合して解を求めるという 従来の解法と非常に異なった性質を持つが その処理量 並列度に関する考察が十分なされていなかった本論文は実験的な評価と統計的モデルを用いた評価により 他の2方式との比較を行い その性質を明らかにする実験的な評価で得られた結果は統計的なモデルで示される性質とよく一致しており 以下の新しい結論が導かれた(a)弱い制約が変数間に均一に存在する問題に対して 並列に得られた途中解を併合するレィャードストリーム型の解法は 複数のプロセスが途中解を共有するため 1つの途中解を生成するための処理畳が少ない生成する途中解の個数は多いが 全体としての処理量は バックトラック型の解法よりも少なく フォワードチェック型の解法と同程度であり 処理の並列性は最も大きい(b)一方 強い制約が一部の変数間にのみ存在する問題に対して フォワードチェック型の解法は強い制約を早期に利剛しうるが レィャードストリーム型の解法は 強い制約の存在により最終的な解の一部となりえない途中解を多く生成し フォワードチェック型の解法と比較して処理量が多くなる
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 32, 号 3, p. 296-303, 発行日 1991-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764