名鉄乗鉄王にITの力で挑んでみた 〜2011冬〜
9時から17時の間、電車を乗り継ぎ、下車駅名でしりとりをしていくというルールで行われました。詳細については一緒に行ったlabeneko先生の記事にまとめられています。
http://d.hatena.ne.jp/labeneko/20111225/1324825332
名鉄の駅はイベント開催時点で275駅あり、しりとりできるペアの数（名鉄一宮→山崎、名鉄一宮→矢作橋、名鉄一宮→弥富、…）はおよそ2200通りあります。
乗り継ぎ計画を組み立てるのは私ではlabeneko氏に絶対敵いませんが、人手だけで1からルートを検討しても、どうしても漏れが出てしまうのではないか？と考えました。そこで、プログラムで全パターンを計算したのち、文字数や総乗車時間などから現実的なルートを洗い出す試みに挑戦しました。
その結果、人ではなかなか思いつかないようなルートを出すことができ、実戦で活かすことができたので、そんなデータの作成手順を紹介しようと思います。
駅名一覧を作成する
漢字駅名と、しりとりに使うための平仮名表記を作成します。平仮名表記については、今回のルールで同一とみなされる濁音や拗音は統一しておきます。（例:「じもくじ」は「しもくし」で格納）
名鉄岐阜 めいてつぎふ 加納 かのう 茶所 ちゃじよ 岐南 きなん 笠松 かさまつ 木曽川堤 きそがわづつみ 黒田 くろた 新木曽川 しんきそがわ 石刀 いわと 今伊勢 いまいせ
しりとりが成立する駅名の全ペアを作成する
上記平仮名表記をもとに、しりとり可能な駅名のペアをスクリプトで作成します。このペアには、「ん」で終わっているものも含めます。（最後に行く可能性を考慮するため）
冒頭でも述べましたが、このペアがおよそ2200通り存在します。
名鉄岐阜 二ツ杁 めいてつぎふ ふたついり 名鉄岐阜 富士松 めいてつぎふ ふじまつ 名鉄岐阜 藤川 めいてつぎふ ふじかわ 名鉄岐阜 福地 めいてつぎふ ふくち 名鉄岐阜 二子 めいてつぎふ ふたこ 名鉄岐阜 渕高 めいてつぎふ ふちだか 名鉄岐阜 藤浪 めいてつぎふ ふじなみ 名鉄岐阜 不破一色 めいてつぎふ ふわいしき 名鉄岐阜 富貴 めいてつぎふ ふき 名鉄岐阜 扶桑 めいてつぎふ ふそう
ペア間の移動時間を追加する
ジョルダンの乗り換え案内サービスを利用して、各ペア間の移動時間を取得します。
もちろん、何時に出発するかによって移動時間は異なりますが、簡略化のために全ての駅を午前10時に出発した場合の時間を追加しています。例えば名鉄岐阜-不破一色間が21分かかるのであれば、
名鉄岐阜 不破一色 めいてつぎふ ふわいしき 21
というtsvを出力します。
ルート探索
作成したペアと所要時間のデータを使うと、出発点を与えればそこから辿れる駅を再帰的に探索していくプログラムを書くことができます。あまりに長いルートは現実的ではないため、総乗車時間や総駅数に閾値を決めておき、超えた時点で探索を終了するようにしておきます。
そのようにして得られた探索結果は以下の形式で出力しており、条件に合わせて駅名でgrepしたり、乗車時間でソートしたりすると、それっぽいルートがずらっと出るようになります。
総文字数 総駅数 総乗車時間(分) 駅名1 駅名2 … 110 18 377 半田口(0,5) 知多半田(3,5) 巽ヶ丘(16,6) 金山(22,4) 丸ノ内(15,5) 中京競馬場前(39,14) 榎戸(66,4) 常滑(4,4) 名鉄一宮(48,9) 山崎(16,4) 木曽川堤(31,7) 妙興寺(22,6) 島氏永(2,6) 苅安賀(22,5) 観音寺(1,5) 新清洲(24,5) 須ケ口(2,4) 中部国際空港(44,12) 110 18 379 半田口(0,5) 知多半田(3,5) 高横須賀(23,6) 金山(17,4) 丸ノ内(15,5) 中京競馬場前(39,14) 榎戸(66,4) 常滑(4,4) 名鉄一宮(48,9) 山崎(16,4) 木曽川堤(31,7) 妙興寺(22,6) 島氏永(2,6) 苅安賀(22,5) 観音寺(1,5) 新清洲(24,5) 須ケ口(2,4) 中部国際空港(44,12) 106 18 379 三河八橋(0,7) 新安城(12,7) 宇頭(3,3) 牛田(15,3) 大山寺(53,5) 新日鉄前(54,8) 榎戸(30,4) 常滑(4,4) 名鉄一宮(48,9) 山崎(16,4) 木曽川堤(31,7) 妙興寺(22,6) 島氏永(2,6) 苅安賀(22,5) 観音寺(1,5) 新清洲(24,5) 須ケ口(2,4) 中京競馬場前(40,14) 105 17 374 知多半田(0,5) 巽ヶ丘(16,6) 金山(22,4) 丸ノ内(15,5) 中京競馬場前(39,14) 榎戸(66,4) 常滑(4,4) 名鉄一宮(48,9) 山崎(16,4) 木曽川堤(31,7) 妙興寺(22,6) 島氏永(2,6) 苅安賀(22,5) 観音寺(1,5) 新清洲(24,5) 須ケ口(2,4) 中部国際空港(44,12) 105 17 374 半田口(0,5) 知多半田(3,5) 巽ヶ丘(16,6) 金山(22,4) 丸ノ内(15,5) 中京競馬場前(39,14) 榎戸(66,4) 常滑(4,4) 名鉄一宮(48,9) 山崎(16,4) 木曽川堤(31,7) 妙興寺(22,6) 島氏永(2,6) 観音寺(20,5) 新清洲(24,5) 須ケ口(2,4) 中部国際空港(44,12) 105 17 376 知多半田(0,5) 高横須賀(23,6) 金山(17,4) 丸ノ内(15,5) 中京競馬場前(39,14) 榎戸(66,4) 常滑(4,4) 名鉄一宮(48,9) 山崎(16,4) 木曽川堤(31,7) 妙興寺(22,6) 島氏永(2,6) 苅安賀(22,5) 観音寺(1,5) 新清洲(24,5) 須ケ口(2,4) 中部国際空港(44,12) 105 17 376 半田口(0,5) 知多半田(3,5) 高横須賀(23,6) 金山(17,4) 丸ノ内(15,5) 中京競馬場前(39,14) 榎戸(66,4) 常滑(4,4) 名鉄一宮(48,9) 山崎(16,4) 木曽川堤(31,7) 妙興寺(22,6) 島氏永(2,6) 観音寺(20,5) 新清洲(24,5) 須ケ口(2,4) 中部国際空港(44,12) 105 17 377 尾張横須賀(0,7) 金山(14,4) 丸ノ内(15,5) 中京競馬場前(39,14) 榎戸(66,4) 常滑(4,4) 名鉄一宮(48,9) 山崎(16,4) 木曽川堤(31,7) 妙興寺(22,6) 島氏永(2,6) 苅安賀(22,5) 観音寺(1,5) 甚目寺(36,4) 新清洲(15,5) 須ケ口(2,4) 中部国際空港(44,12) 105 18 378 三河八橋(0,7) 新安城(12,7) 牛田(3,3) 大山寺(53,5) 神宮前(27,6) 榎戸(44,4) 常滑(4,4) 名鉄一宮(48,9) 山崎(16,4) 木曽川堤(31,7) 妙興寺(22,6) 島氏永(2,6) 苅安賀(22,5) 観音寺(1,5) 甚目寺(36,4) 新清洲(15,5) 須ケ口(2,4) 中京競馬場前(40,14) 104 18 366 三河八橋(0,7) 新安城(12,7) 宇頭(3,3) 牛田(15,3) 大山寺(53,5) 神宮前(27,6) 榎戸(44,4) 常滑(4,4) 名鉄一宮(48,9) 山崎(16,4) 木曽川堤(31,7) 妙興寺(22,6) 島氏永(2,6) 苅安賀(22,5) 観音寺(1,5) 新清洲(24,5) 須ケ口(2,4) 中京競馬場前(40,14)
データダウンロード
「犬山遊園」「八幡新田」で終わるルートの一部(20KB)
http://dl.dropbox.com/u/231552/meitetsu/meitetsu_routes_top100_n.tsv
使用データフルセット(2.7MB、展開後59.2MB)
http://dl.dropbox.com/u/231552/meitetsu/route_1225.tgz
反省点
反省点としては、出力されるルートの数が多すぎて結局検証に手間がかかるという点が挙げられます。ルートが多すぎると、大雑把な条件でgrepしていくことになりますが、今度はそれで省いてしまったルートに、実は優勝できそうなルートが紛れていたのでは？ということが起こります。やはり出発時刻に応じて、下車駅での待ち時間も考慮した移動時間を計算する必要があるかもしれません。
