SATに対する陰的列挙法とDavis-Putnamの方法の関係について
スポンサーリンク
概要
- 論文の詳細を見る
命題論理の充足可能性問題(SAT)は、情報処理の分野における基本的な問題の一つで、現在まで多くの研究が行われている。最近になって若者らは、0-1整数計画法の解法の一つである、陰的列挙法に基づくSATアルゴリズムを提案している。その方法は、SATを0-1整数計画問題として定式化した場合の特徴を利用して、陰的列挙法をSAT向きに見直したものであり、計算機実験の結果、良好な結果を得ている。本稿では、陰的列挙法に基づくSATアルゴリズムとSATに対する古典的な方法であるDavis-Putnamの方法を比較検討し、両者の関係を明らかにする。そしてその結果に基づき、陰的列挙法に基づくSATアルゴリズムを改良した方法を提案し、その有効性を計算機実験により示す。
- 一般社団法人情報処理学会の論文
- 1993-03-01
著者
関連論文
- 大型疎線形計画問題に対する Reid の基底更新方法の改善
- 大型疎線形計画問題に対するReidのバンプ縮小方法の基本的性質
- 遺伝情報の統合処理支援モジュールの構築
- 命題論理充足可能性問題に対する定量的アプローチと記号的アプローチの比較
- β節充足可能性問題の解法についての考察
- 部分例示に基づく定理自動証明
- β節集合に対するDavis-Putnamの手続きの一般化
- 部分例示手法に基づく充足可能性判定手続き
- 部分例示手法に基づいた定理自動証明手続き
- IEMSATアルゴリズムの実験的評価
- 陰的列挙法に基づくβ SATアルゴリズム
- 命題論理におけるβ節充足可能性問題とその解法
- 陰的列挙法に基づく SAT アルゴリズム
- 部分例示手法に基づいた述語論理式の充足可能性判定手続き
- SATに対する陰的列挙法とDavis-Putnamの方法の関係について
- FISM/KJの理論的枠組み(モデリング)
- 命題論理充足可能性問題に対する定量的アプローチ(AIとOR)
- 充足可能性問題に対するJeroslowの手法の拡張
- 充足可能性問題の0-1整数計画問題への定式化と計算効率
- 論理推論に対する定量的方法 : 枠組と適用可能性
- 単体法の並列処理に関する基礎的検討
- 大型疎線形計画問題の基底の三角分解更新に対する改良Reid法の提案(LP単体法)
- 有理数演算によるゴモリーの小数法の基礎的検討
- 帯行列を係数行列とする連立一次方程式を誤差なく計算する場合のLU分解について