最長しりとり問題の解法  [in Japanese] Solving the Longest Shiritori Problem  [in Japanese]

Access this Article

Search this Article

Author(s)

    • 乾 伸雄 INUI NOBUO
    • 東京農工大学大学院共生科学技術研究部 Institute of Symbiotic Science and Technology, Tokyo University of Agriculture and Technology
    • 品野 勇治 SHINANO YUJI
    • 東京農工大学大学院共生科学技術研究部 Institute of Symbiotic Science and Technology, Tokyo University of Agriculture and Technology
    • 小谷 善行 KOTANI YOSHIYUKI
    • 東京農工大学大学院共生科学技術研究部 Institute of Symbiotic Science and Technology, Tokyo University of Agriculture and Technology

Abstract

本論文では,最長しりとり問題をネットワークの問題としてモデル化し,整数計画問題として定式化を行う.この定式化では,変数の数が頂点数に対して,指数オーダで増加するため,事実上,整数計画問題として直接的に解くことは難しい.そのため,緩和問題を設定し,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.

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.8 GHz 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.

Journal

  • 情報処理学会論文誌数理モデル化と応用(TOM)

    情報処理学会論文誌数理モデル化と応用(TOM) 46(SIG2(TOM11)), 105-117, 2005-01-15

    Information Processing Society of Japan (IPSJ)

References:  10

Cited by:  1

Codes

  • NII Article ID (NAID)
    110002768734
  • NII NACSIS-CAT ID (NCID)
    AA11464803
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    1882-7780
  • NDL Article ID
    7237470
  • NDL Call No.
    Z74-C192
  • Data Source
    CJP  CJPref  NDL  NII-ELS  IPSJ 
Page Top