著者
乾 伸雄 品野 勇治 鴻池 祐輔 小谷 善行
雑誌
情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)
巻号頁・発行日
vol.46, no.SIG2(TOM11), pp.105-117, 2005-01-15

本論文では,最長しりとり問題をネットワークの問題としてモデル化し,整数計画問題として定式化を行う.この定式化では,変数の数が頂点数に対して,指数オーダで増加するため,事実上,整数計画問題として直接的に解くことは難しい.そのため,緩和問題を設定し,LP ベースの分枝限定法によって解決した.これによって,19 万語程度の辞書から最長しりとりをXeon2.8GHz プロセッサのPC を使って1 秒程度で作成することができた.また,本論文では,局所探索による解法と比較し,問題の困難さを実験的に調べた.さらに,様々なインスタンスにおける解を分析することで,最長しりとり問題の性質を調べた.

言及状況

はてなブックマーク (1 users, 2 posts)

 最長しりとり問題の解法 東京農工大学
 最長しりとり問題の解法 東京農工大学

Twitter (19 users, 20 posts, 20 favorites)

https://t.co/k0t70EtoOD これか・・・?
@tsujimotter 広辞苑から最大のしりとり可能集合を取り出す、という研究の報告が10年ちょっと前にありました https://t.co/AoXL5OW2Lx
@DEGwer3456 NP完全は完全にてきつーにしゃべっていたのですが、最長経路問題に帰着するのでNP困難という言及を見つけました。 https://t.co/2xxzcfGBXf
https://t.co/pPdguRVjoF

収集済み URL リスト