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

文章基本信息

  • 标题:SAT変換に基づく制約ソルバーとその性能評価
  • 本地全文:下载
  • 作者:田村 直之 ; 丹生 智也 ; 番原 睦則
  • 期刊名称:コンピュータ ソフトウェア
  • 印刷版ISSN:0289-6540
  • 出版年度:2010
  • 卷号:27
  • 期号:4
  • 页码:4_183-4_196
  • DOI:10.11309/jssst.27.4_183
  • 出版社:Japan Society for Software Science and Technology
  • 摘要:

    本論文では,SAT変換に基づく制約ソルバーであるSugarの概要とその性能評価結果について述べる.Sugarは,制約充足問題(CSP),制約最適化問題(COP)および最大制約充足問題(Max-CSP)を,命題論理の充足可能性判定問題(SAT問題) に変換し,MiniSat等の高速なSATソルバーを用いて求解を行うシステムである.SAT変換には,order encodingと名付けた新しい方法を用いており,従来広く用いられているdirect encodingやsupport encodingよりも,多くの問題に対して高速な求解が可能である.本論文では,order encodingの説明を含めたSugarの概要について述べた後,2008年に開催された第3回国際CSPソルバー競技会およびMax-CSPソルバー競技会での結果を基にSugarの性能評価結果を報告する.なお,Sugarは同競技会の10部門のうち4部門で第1位となった.

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