文献

J-GLOBAL ID：201502210035928213   整理番号：15A1192332

順序符号化と対数符号化を融合した制約充足問題のハイブリッド符号化

著者 (3件)： 宋剛秀 (神戸大 情報基盤セ) ,  番原睦則 (神戸大 情報基盤セ) ,  田村直之 (神戸大 情報基盤セ)
資料名： 日本ソフトウェア科学会大会講演論文集(CD-ROM)  (日本ソフトウエア科学会大会講演論文集(CD-ROM))
巻： 32nd  ページ： ROMBUNNO.PPL6-3  発行年： 2015年 
JST資料番号： X0080B  ISSN： 1348-0901  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本論文では制約充足問題(CSP)から命題論理式の充足可能性判定問題(SAT)への新しい符号化として,順序符号化と対数符号化を融合したハイブリッド符号化を提案する。順序符号化は効率的な制約伝播が特長であり小中規模のドメイン/アリティを持つ制約に対して有効な符号化であるが,それらが大きくなるにつれて符号化によって生成されるSAT節が膨大になる。一方,対数符号化は大規模なドメイン/アリティを持つ制約でも比較的少ないSAT節で符号化できるが,桁上りのための推論が余分に必要なため制約伝播の効率はよくない。提案手法は両符号化の特長を活かし,小中規模のドメイン/アリティをもつ制約は順序符号化し,その他の制約については対数符号化する。人工的な問題12問とCSPソルバー競技会のベンチマーク問題1002問を用いた実験の結果,提案手法は両符号化よりも高速に多くの問題を求解できることを確認した。さらにどちらの符号化でも解けない問題を解くことにも成功し,融合の相乗効果を確認した。(著者抄録)

シソーラス用語： *制約充足問題 ,  *符号化 ,  順序 ,  対数 ,  ハイブリッド方式 ,  高速化 ,  性能評価 ,  ベンチマーク ,  制約条件
準シソーラス用語： *SAT符号化 ,  制約伝播

分類 (2件)： 論理代数  (JB03000H) ,  符号理論  (ND02030R)

タイトルに関連する用語 (5件)： 順序符号化 ,  対数 ,  符号化 ,  融合 ,  制約充足問題