著者
乾 伸雄 品野 勇治 鴻池 祐輔 小谷 善行
出版者
一般社団法人情報処理学会
雑誌
情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)
巻号頁・発行日
vol.46, no.2, pp.105-117, 2005-01-15
参考文献数
10
被引用文献数
1 or 0

本論文では,最長しりとり問題をネットワークの問題としてモデル化し,整数計画問題として定式化を行う.この定式化では,変数の数が頂点数に対して,指数オーダで増加するため,事実上,整数計画問題として直接的に解くことは難しい.そのため,緩和問題を設定し,LP ベースの分枝限定法によって解決した.これによって,19 万語程度の辞書から最長しりとりをXeon2.8GHz プロセッサのPC を使って1 秒程度で作成することができた.また,本論文では,局所探索による解法と比較し,問題の困難さを実験的に調べた.さらに,様々なインスタンスにおける解を分析することで,最長しりとり問題の性質を調べた.This paper describes the definition of the longest Shiritori problem as a problem of network flow and the solution using the the integer problem. This formulation requires a large number of variables being of exponential order. To overcome the difficulty, we propose a solution based on the LP-based branch-and-bound method, which solves the relaxation problems repeatedly and enumerates all the solutions implicitly. This method is able to calculate the longest Shiritori sequences for 190 thousand words dictionary in a second in Xeon 2.8GHz PC. In this paper, we compare the performances for the heuristic local search and investigate the results for a variety of instances to explore characteristics of the longest Shiritori problem.

言及状況

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

Twitter (25 users, 27 posts, 6 favorites)

結局,品野先生が妥協案を出したんだったかな.準最適解. | CiNii 論文 -  最長しりとり問題の解法 https://t.co/fSFBUBAIOG
今話題になっている論文は、これ→ 最長しりとり問題の解法 : 乾 伸雄 品野 勇治 鴻池 祐輔 小谷 善行 https://t.co/y5t5MUD7Pk #ipsj #ipsj78
CiNii 論文 -  最長しりとり問題の解法 http://t.co/bjW15j2a8J
最長しりとり問題の解法 http://t.co/TmWDfyqPwi
“CiNii 論文 -  最長しりとり問題の解法” http://t.co/uHcymXCdR6
というか、いつも思うんですが、色んな事を研究している方がたくさんいるもんですよね。今年読んだ中での個人的な一番のヒットは、最長のしりとりを算出しようとしているこの論文です。 http://t.co/RpHoWGsd
これがたぶん一番使える http://t.co/QpgNw4T
@tomo_lpb これK谷先生が絡んでるのが面白いね http://t.co/B1YiPLm3
コレ(CiNii 論文 -  最長しりとり問題の解法 http://ci.nii.ac.jp/naid/110002768734 )が参考文献に載ってるのにコレとの関係が触れられてない...
http://ci.nii.ac.jp/naid/110002768734/ を元にしてるそうだがなるほど、分からん
RT @kake4413 : おもしろそう! RT @alaudide: ぷよぷよはNP完全の他にもこのような素朴なことを題材にした研究があるのか RT @h013: 素敵! http://ci.nii.ac.jp/naid/110002768734
おもしろそう! RT @alaudide: ぷよぷよはNP完全の他にもこのような素朴なことを題材にした研究があるのか RT @h013: 素敵! http://ci.nii.ac.jp/naid/110002768734/
RT @alaudide : ぷよぷよはNP完全の他にもこのような素朴なことを題材にした研究があるのか RT @h013: 素敵! http://ci.nii.ac.jp/naid/110002768734
素敵! http://ci.nii.ac.jp/naid/110002768734/

収集済み URL リスト