単語長を考慮した最長しりとり問題の実験的考察

• Item type: Trans(1)
• 公開日: 2005-12-15
• タイトル: 単語長を考慮した最長しりとり問題の実験的考察
• タイトル / 言語: en
• タイトル: Experiment on the Maximum-Shiritori-String-Length Shiritori Problem
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 事例紹介論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京農工大学工学部情報コミュニケーション工学科
• 著者所属: 東京農工大学工学部情報コミュニケーション工学科
• 著者所属: 東京農工大学工学部情報コミュニケーション工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Information and Communication Sciences Faculty of Engineering Tokyo University of Agriculture and Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Information and Communication Sciences Faculty of Engineering Tokyo University of Agriculture and Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Information and Communication Sciences Faculty of Engineering Tokyo University of Agriculture and Technology
• 著者名: 乾, 伸雄; 品野, 勇治; 小谷, 善行
• 著者名(英): Nobuo, Inui; Yuji, Shinano; Yoshiyuki, Kotani
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，先行研究の最長しりとり問題の一般化として，最長しりとり問題で単語の長さを考慮した文字数最大しりとり問題の厳密解法について述べ，その実験的評価を行う．文字数最大しりとり問題は，整数計画問題として記述した場合，単語の最大の長さをl としたとき，最長しりとり問題を記述するための変数のl 倍の変数が必要となり，現実的に解けるかどうかは未知である．l = 26 の既知の単語について，文字数最大しりとり問題は先行研究での最長しりとり問題に比べ，約41 倍の計算時間がかかることが分かった．さらに，これら2 つの問題の派生問題として，固定単語長文字数最大しりとり問題および固定文字数最長しりとり問題を取り上げる．これらの派生問題を用いて，広辞苑とICOT 形態素解析辞書について，最長しりとり問題の最適解と文字数最大しりとり問題の最適解の関係を分析した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper describes an exact algorithm of the maximum-shiritori-string-length shiritori problem (MS3 in short) which maximizes a shiritori-string length. This algorithm is obtained from a generalization of an exact algorithm of the longest shiritori problem (LS in short) proposed previously. We experimentally evaluate the algorithm and investigate the properties of the MS3 problem. Since the MS3 problem takes l times number of variables of the LS problem, where l is the maximum length of words, under the integer programming approach, it is unknown whether the problem instance can be solved or not. Our experimental results showed that 41 times calculation times of the LS problem is required to solve MS3 problem, when l = 26. In addition, two derived problem of these shiritori problems, called the fixedlength MS3 shiritori problem and the fixed-shiritori-string-length LS problem, are introduced. In this paper, we analyze the relations between the MS3 problem and the LS problem, using these derived problems.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464803
• 書誌情報: 情報処理学会論文誌数理モデル化と応用（TOM）; 巻 46, 号 SIG17(TOM13), p. 131-142, 発行日 2005-12-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7780
• 出版者 / 言語: ja
• 出版者: 情報処理学会