日時：2004年 7月22日(木) 18:30 から
場所：東京農工大学 工学部情報コミュニケーション工学科 7号棟 3階3K室
JR中央線東小金井駅南口から，西へ向かって徒歩8分程度です．
農工大の東門に建物の配置図があります．
http://www.cs.tuat.ac.jp/access.html
に案内図があります.
話者：
品野勇治，乾伸雄（東京農工大学，大学院共生科学技術研究部）
話題：
最長しりとり問題の解法について
概要：
「トリビアの泉」というTV番組で，「広辞苑の見出し語を使って，最も長いし
りとりを作る」という話が放映されました．本発表では，TV番組制作会社から
の問い合わせに答えるべく開発した，この最も長いしりとりを求めるための解
法を紹介します．解法については，最適解を求める厳密解法と，準最適解を求
めるヒューリスティックな解法の両方を紹介するとともに，それらを実装して
行った数値実験結果を紹介します．また，TV番組中で実際に使われた「最長し
りとり作成プログラム」のデモも行います．
食事：
ありません．東小金井駅近辺のモスバーガー，途中のピーコック
（マクドナルドあり）などをご利用ください．
出席者：27名（名簿にお名前をお書き下さった方々）
和田 英一（IIJ），磯部 泰徳，金子 敬一，笹田 耕一，並木 美太郎，宮代 隆平，
宮村 浩子（東京農工大），井原 伸介，大日向 大地，白井 雄一郎，鈴木 信吾，
多田 好克，丸山 一貴（電通大），金子 知適，黒木 裕介，副田 俊介，田中 哲朗，
室田 朋樹，横山 大作，筧 一彦（東京大），森岡 靖太（東芝），石畑 清（明治大），
伊知地 宏（ラムダ数学教育研），山口 文彦（東京理科大），須賀 淳（芝浦工業大），
松野 徳大（東京都立高専），丹下 悠二（武蔵野美術大）
話者: 品野勇治，乾伸雄 （東京農工大学，大学院共生科学技術研究部）
題名: 最長しりとり問題の解法について
概要:
「トリビアの泉」というTV番組で，「広辞苑の見出し語を使って，最も長いし
りとりを作る」という話が放映されました．本発表では，TV番組制作会社から
の問い合わせに答えるべく開発した，この最も長いしりとりを求めるための解
法を紹介します．解法については，最適解を求める厳密解法と，準最適解を求
めるヒューリスティックな解法の両方を紹介するとともに，それらを実装して
行った数値実験結果を紹介します．また，TV番組中で実際に使われた「最長し
りとり作成プログラム」のデモも行います．
質疑応答：
- 使われなかった単語の割合は?
乾：単語数による違いや辞書の種類によって変わってきます．広辞苑から２種
類の方法で単語を取り出した場合と中学，高校の教科書からの単語の抜粋
，ＩＣＯＴ辞書による結果を示しましたが，広辞苑から抜き出した名詞の
場合，次の質問に対するコメント（表）にあるように最長しりとりの長さ
（使われた単語の数）が決まります．（始点終点が同じ単語の数を半分
(小数点以下切り捨て）にしていっています）
注）「切り上げ」にすると最長しりとりの長さが長くなるというまったく
別の結果が得られます．
- このしりとりでの利用単語の割合を使って, 辞書の偏りを調べることは可能か?
乾：広辞苑の単語を基準として，長めの最長しりとりができるのか短めの最長
しりとりができるのかなどの傾向を調べることは可能です．単純には，あ
る文字より始まる単語が多く，その文字で終わる単語が少ないような辞書
では，使われない文字が多くなります．つまり文字Ciで始まる単語の数を
B(Ci)，終わる単語の数をT(Ci)と書くと，
Σf(B(Ci)-T(Ci))
f(x)=x if x>0
0 otherwise
は，しりとりで使われることのない単語の数を表します．
前の表の192,687単語の場合，このような考えで使われることのない単語
は89606となり，46%の単語は使われることはないです．ただし，次表の結
果が示すように，使われない単語と最長のしりとりの長さには負の関係が
ありますが，最右欄が示すように，必ずしもそれだけではありません．
結局，広辞苑に対して偏りがあるかどうかを調べることはできますが，こ
れが何の偏りであるかははっきりしていません．グラフ理論に詳しい方な
ら答えを出せると思いますけど．
単語数(A) 最長しりとりの 使われること B/(A-C)
単語数に占める のない単語数の
単語数(B)と割合 占める単語数(C)と割合
196,983 89,606 45% 88,821 45% 83%
97,390 43,666 45% 44,363 46% 82%
47,636 20,759 44% 22,149 46% 81%
22,881 9,475 41% 11,019 48% 80%
10,654 4,019 38% 5,444 51% 77%
4,663 1,475 32% 2,622 56% 72%
1,902 420 22% 1,236 65% 63%
720 98 14% 540 75% 54%
- 外国語辞書を利用した場合どのような結果が得られそうか?
乾：ＬＰの定式化では，二つのひらがなを結ぶ単語の数を変数としているので
，実行時間はひらがなの文字数に依存します．そのため，英語などの場合
は，アルファベットの種類数が少ないため，日本語よりは高速に解を求め
られることが予測されます．前の質問に関連して，文字の種類数が少なく
，ある文字が先頭に来る場合の単語数と終わりに来る場合の単語数の差が
日本語よりも大きい場合，使われることのない単語の数が多くなり，最長
しりとりの長さは短くなります．しかしながら，これを持って，英語の場
合は最長しりとりの長さが短くなるとは言えず，「やってみて」始めてわ
かることかと思います．
しりとりは基本的に音のゲームだと思いますので，英語の場合でも，単語
の文字よりも発音で行った方がよろしいかと思います．その場合，日本語
よりも文字の種類数が多くなり，問題として面白そうです．
- 単語数ではなく文字数で数えた時の最長は求められるか?
品野：問題としては，文字数の数での最長も考えましたが，解法は考えていま
せん．定式化は簡単な変更で可能なのですが変数の数が増えます．
（翌日の朝１限が講義課目の試験で，その準備もあって懇親会の後，大
学に戻ったので考えてみました．変数の数は，大幅に増えますが，
線形計画問題が解ける範囲に思えたので解けそうな気がしました．
翌日，乾先生にお願いして，土日にプログラムを変更して実行しても
らいました．結局，解けることがわかりました．また，機会があった
ら報告します）
- 整数計画問題に定式化された問題の整数条件を緩和した問題の最適解は必ず
しも整数解ではない．完全ユニモジュラであれば，線形計画問題のソルバが
整数解を返すということでしょうか？
品野：私の説明が正確でなかったようです．正確には田中先生のご指摘の通り
です．最適となる整数解が必ず存在し，それが求まるということです．
われわれの分野では，線形計画問題の解として，基底解を求める
ことが当たり前の感覚でいたため，質問の意図が理解できずに申し訳
ありませんでした．今後，もう少し説明に気を配るように致します．
（さらに，念のためプレゼンテーションを見直すと，このようにな解釈
が不可な記述になっていて，何を気にされていたのかわかりました．
ご指摘ありがとうございました）
- 実験データの表で，「任意の品詞」よりも「名詞だけ」の方が単語数が
多いのはなぜ？
乾：「名詞だけ」広辞苑より名詞以外のタグが付いた単語を読みの重複を
含めて使ったものです．「任意の品詞」は清音で始まる単語を抜き出
し，読みの重複を除いたもので，全ての単語を使ったものではないです．
特に作為的に抜き出したものではないです．