文献

J-GLOBAL ID：202502255691920634   整理番号：25A0106720

ハミルトン閉路問題に対するCut-arc集合制約を用いたSAT型CEGAR解法

著者 (6件)： 大橋瞭雅 (神戸大) ,  宋剛秀 (神戸大) ,  鍋島英知 (山梨大) ,  番原睦則 (名古屋大) ,  井上克巳 (情報研) ,  田村直之 (神戸大)
資料名： 日本ソフトウェア科学会大会講演論文集(Web)  (Proceeding of the JSSST Annual Conference (Web))
巻： 41st  ページ： ROMBUNNO.5-P (WEB ONLY)  発行年： 2024年 
JST資料番号： U1746A  ISSN： 1349-3515  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： ・本稿は,巡回セールスマン問題に応用されるハミルトン閉路問題(HCP)の解法であるSAT型の反例に基づく抽象化精錬法(CEGAR)の改良についての提案とその検証。
・従来の部分閉路にat-most制約を追加する手法に換えて,提案では,Cut-arc集合にat-least制約を追加。
・国際競技会のベンチマーク問題1001問を用いた評価実験では,従来手法では539問の解答に対し,提案手法では884問に解答できることを確認し,有効性を実証。

シソーラス用語： *Hamilton閉路 ,  *解法 ,  *制約条件 ,  巡回セールスマン問題 ,  閉路 ,  ベンチマーク ,  可能性 ,  定理証明 ,  抽象 ,  精錬 ,  NP完全問題
準シソーラス用語： 充足可能性 ,  制約 ,  精錬法 ,  抽象化 ,  反例

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (6件)： ハミルトン閉路 ,  ARC ,  集合 ,  制約 ,  SAT ,  解法