β節集合に対するDavis-Putnamの手続きの一般化

• 山本, 雅人

• 大柳, 俊夫

• 大内, 東

書誌事項

タイトル別名

• Generalization of Davis-Putnam Procedure for a set of β clauses

抄録

節集合の充足可能性を判定するための方法として,Davis-Putnamの手続きがある.また,著者らはIEMSATと呼ばれる方法を提案し,Davis-Putnamの手続きとの密接な関係を明らかにしている.IEM-SATは0-1計画問題を解く一般的な方法である陰的列挙法に基づいたアルゴリズムである.一方,節を一般化したβ節といわれる節がある.β節とはその節中のβ個のリテラルが真であるとき,また,そのときに限り真となる節であり,β=1のとき通常の節と同じものになる.著者らは,既にβ節を用いることによって簡単に表現が可能な制約が存在することを示し,β節からなるβ節集合の充足可能性問題を解く方法としてIEMBSATを提案している.本稿では,IEMSATとDavis-Putnamの手続きとの密接な関係から,Davis-Putnamの手続きをβ節を扱う立場から見直しを行い,β節集合に対して適用可能となるような拡張を行う.また,β節の有効性について,最近注目されているGSATなどの局所探索法との比較実験などを通して検討する.

収録刊行物

• 全国大会講演論文集

  全国大会講演論文集 第50回 (人工知能及び認知科学), 1-2, 1995-03-15

詳細情報

• CRID: 1050292572099805312
• NII論文ID: 110002875821
• NII書誌ID: AN00349328
• Web Site: http://id.nii.ac.jp/1001/00127730/
• 本文言語コード: ja
• 資料種別: conference paper
• データソース種別:
  • IRDB
  • CiNii Articles