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

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

言及状況

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

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

Twitter (4 users, 4 posts, 2 favorites)

最長しりとり問題の解法 https://t.co/krYMX4qX5c
@DEGwer3456 NP完全は完全にてきつーにしゃべっていたのですが、最長経路問題に帰着するのでNP困難という言及を見つけました。 https://t.co/2xxzcfGBXf

収集済み URL リスト