首页    期刊浏览 2024年11月10日 星期日
登录注册

文章基本信息

  • 标题:GlueMiniSat 2.2.5: 単位伝搬を促す学習節の積極的獲得戦略に基づく高速SATソルバー
  • 本地全文:下载
  • 作者:鍋島 英知 ; 岩沼 宏治 ; 井上 克巳
  • 期刊名称:コンピュータ ソフトウェア
  • 印刷版ISSN:0289-6540
  • 出版年度:2012
  • 卷号:29
  • 期号:4
  • 页码:4_146-4_160
  • DOI:10.11309/jssst.29.4_146
  • 出版社:Japan Society for Software Science and Technology
  • 摘要:

    命題論理の充足可能性判定問題(SAT問題)を解くソルバーは,その飛躍的な性能向上に伴い,システム検証やプランニング・スケジューリング問題,制約充足・最適化問題等の様々な分野において活躍している.GlueMiniSat 2.2.5は,単位伝搬を促し矛盾の発生を促進する学習節を積極的に獲得する戦略に基づくSATソルバーである.学習節の評価尺度には,AudemardとSimonが開発したSATソルバーGlucoseで導入されたリテラルブロック距離を改良した尺度を用い,単位伝搬を促進する学習節を獲得・保持する.また良い学習節の獲得を促すため,非常に積極的なリスタート戦略を採る.我々は代表的SATソルバーであるMiniSat 2.2を基にこれらの手法を実装し,GlueMiniSat 2.2.5を開発した.GlueMiniSat 2.2.5は充足不能性の証明に強く,SAT 2011競技会のApplication部門において逐次型ソルバーとしてUNSATクラスで1位,SAT+UNSATクラスで2位を獲得している.また並列型ソルバーを含めても同部門UNSATクラスで2位を獲得している.

国家哲学社会科学文献中心版权所有