Davis-Putnam の手続きにおける分枝変数選択規則の提案

• 山本, 雅人

• 大内, 東

書誌事項

タイトル別名

• A propose of a blanching rule in the Davis-Putnam method

抄録

命題論理における充足可能性問題はNP-完全問題の一つとして知られており, 人工知能の分野における重要な問題の一つである. SATの解法として, Davis-Putnamの手続きの改良が効率的であることが報告されている。しかしながら, Davis-Putnamの手続きの計算効率は分枝変数選択規則に強く依存することも報告されている. 本稿では,難しい問題とされているランダム 3-SATを用いて, これまで提案されている分枝変数選択規則についての比較実験を行い, ランダム 3-SATに有効であるような分枝変数選択規則の性質について考察する.

収録刊行物

• 全国大会講演論文集

  全国大会講演論文集 第54回 (人工知能と認知科学), 329-330, 1997-03-12

詳細情報

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