06月12日(Tue) 15:30〜20:00 E会場(-山口県教育会館／第四研修室(72))
| 演題番号 | 1E3-OS-4-2 |
|---|---|
| 題目 | ハミルトン閉路問題のSAT符号化に関する研究 |
| 著者 | 船越 泰輔(神戸大学大学院システム情報学研究科情報科学専攻) 番原 睦則(神戸大学 情報基盤センター) 田村 直之(神戸大学 情報基盤センター) |
| 時間 | 06月12日(Tue) 15:50〜16:10 |
| 概要 | 本論文では，ハミルトン閉路問題を命題論理の充足可能性判定問題 (SAT)に符号化し解く新しい方法を提案する．提案手法の特徴は，閉 路が単一である条件を符号化せず，複数の閉路が求まるたびにその 否定の条件を追加する方法を用いている点にある．このようなイン クリメンタルSAT解法を導入することにより，SAT技術を用いた既存 手法よりも優れた性能を示すことが確認できた． |
| 論文 | PDFファイル |