並列論理型言語上での制約充足方式の比較
横尾 真, 上田 和紀
情報処理学会論文誌, vol.32, No.3, pp.296-303, 1991.


本論文では, 従来から提案されている制約充足問題の解法である 単純なバックトラック型の解法, バックトラック型の解法の改良である フォワードチェック型の解法と, 近年提案された並列論理型言語向きの, 処理の並列性を最大限に引き出すための新しい 制約充足問題の解法であるレイヤードストリーム型の解法の比較を行う. レイヤードストリーム型の解法は 並列に得られた途中解を併合して解を求めるという, 従来の解法と非常に異なった性質を持つが, その処理量, 並列度に関する考察が十分なされていなかった. 本論文は実験的な評価と統計的モデルを用いた評価により, 他の2方式との比較を行い, その性質を明らかにする.

実験的な評価で得られた結果は統計的なモデルで示される性質とよく一致しており, 以下の新しい結論が導かれた.