著者

乾 伸雄 品野 勇治 小谷 善行

出版者

一般社団法人情報処理学会

雑誌

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

巻号頁・発行日

vol.46, no.17, pp.131-142, 2005-12-15

---

本論文では,先行研究の最長しりとり問題の一般化として,最長しりとり問題で単語の長さを考慮した文字数最大しりとり問題の厳密解法について述べ,その実験的評価を行う.文字数最大しりとり問題は,整数計画問題として記述した場合,単語の最大の長さをl としたとき,最長しりとり問題を記述するための変数のl 倍の変数が必要となり,現実的に解けるかどうかは未知である.l = 26 の既知の単語について,文字数最大しりとり問題は先行研究での最長しりとり問題に比べ,約41 倍の計算時間がかかることが分かった.さらに,これら2 つの問題の派生問題として,固定単語長文字数最大しりとり問題および固定文字数最長しりとり問題を取り上げる.これらの派生問題を用いて,広辞苑とICOT 形態素解析辞書について,最長しりとり問題の最適解と文字数最大しりとり問題の最適解の関係を分析した.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.