著者

乾 伸雄 品野 勇治 小谷 善行

雑誌

情報処理学会研究報告数理モデル化と問題解決(MPS)

巻号頁・発行日

vol.2004, no.92(2004-MPS-051), pp.5-8, 2004-09-13

---

本論文では、しりとり全体に含まれる文字数を最長とする文字数最大しりとり問題をネットワークフロー問題としてモデル化し、LPベースの分枝限定法による解法および実験結果について述べる。単語数を最大にする最長しりとり問題に対して、問題を記述するための変数が最大単語長に比例して多くなる特徴を持つ。実験は実際の辞書に含まれる単語について行った。実験の結果、最長しりとり問題と同じく文字数最大しりとり問題は現実的な時間で解ける問題であることがわかった。