Pythonで最長駅名しりとりを探索してみた

完全に趣味ですね。
実は5年くらい前に作っていたんですが、眠らせておくのももったいないので（誰得感はありますが）、何となく紹介してみます。

問題設定

日本の鉄道駅名¹を読みがなでしりとりします。

なぜ駅名かというと、メンテナンスされている単語リストがあるからということが理由の一つです。
その他、単語数が手頃だとか、身近な存在（多くの人がいくつかは知っているはず）だとか、いろいろありますが、結局は個人の趣味という点に帰着するかもしれません。

ルール

今回は以下のルールでやってみます。

• 原則として同じ駅名を2回以上使ってはいけない。
• しりとりは好きな駅から始めることができる。
• 「ん」で終わるか、続けられる駅名がなくなればそこで終了。
• しりとりの始めから終わりまでに、なるべくたくさんの駅を使う。

なお、補足ルールとして以下を決めておきます。

1. 別の場所²に同じ名前の駅がある場合には、その数だけ使ってよい。
   • （例）「うじ」（宇治）駅はJR奈良線と京阪宇治線にそれぞれ離れて存在するので、2回まで使用可能。
2. 濁点・半濁点は任意に取り外し可能。
3. 末尾の長音（－）は無いものとして考え、直前の文字から続ける。
4. 末尾の拗音「ゃ」「ゅ」「ょ」は、大文字化して「や」「ゆ」「よ」で考える。
5. 「じ」と「ぢ」、「ず」と「づ」は、別のものとして考える³。

例えばこんな感じで

東京（とうきょう）→宇治（うじ：JR奈良線）→十条（じゅうじょう：3つのうちどれか1つ）→宇治（うじ：京阪宇治線：ルール1）
→新大阪（しんおおさか：ルール2）→加布里（かふり）→流通センター（りゅうつうせんたー）
→丹波橋（たんばばし：ルール3）→市役所（しやくしょ）→吉田（よした：大阪府：ルール4）
→大安（だいあん：ルール2）

実装の方針

最長しりとり問題の解法の解説⁴があったので、これをベースに実装してみました。
数式とかは文献に書いてあるので、ここでは厳密な議論はせず、なるべく直感的に分かりやすい表現で書きます。定義の曖昧な単語などが出るかもしれませんが、ご了承ください。

理屈とか細かいことはいいからとにかく遊びたいという方は、「解いてみよう」の節までジャンプしてください。

グラフの作成

簡単に言えば、

• 五十音に対応する頂点を作る。
• 各駅名の最初の文字から最後の文字に向かって枝を追加する。（枝の方向を矢印で表します。一方通行の道路みたいなものと思ってください）
• しりとりの始まりを表すsという特別な頂点を作り、sからはs以外のすべての頂点に出る枝を1本ずつ付ける。
• しりとりの終わりを表すtという特別な頂点を作り、t以外のすべての頂点からtに1本ずつ枝を付ける。

これにより、以下のようなグラフを作ります。赤い矢印は先ほどのしりとりの例を表します。

同一視する文字は正規化して1つにまとめてしまっています。例えば「だいあん」の枝は「た」→「ん」、「しやくしょ」の枝は「し」→「よ」に付けています。また、「うじ」は2駅あるため、「う」→「し」に2本の枝が追加されます。
（※実際には、しりとりに使わない駅もたくさんあるので、各頂点には大量の枝が出入りしています。図に描くととんでもないことになるので、あえて描きません）

この変換によって、最長駅名しりとり問題は、上のグラフから同じ枝を2度通らず、sで始まりtで終わる、なるべく長い経路を見つけ出す問題となります。
（別の言い方をすれば、sという場所からtという場所まで行くのに、同じ道路を通らず、一方通行を守りながら、なるべく長い距離をドライブしたい、という感じでしょうか）

さらに言えば、そのような最長経路について、どの頂点からどの頂点に何本の枝を使うかだけを求めれば十分です。例えば、今回の例なら、
「s→と」×1、「と→う」×1、「う→し」×2、「し→う」×1、「し→か」×1、「か→り」×1、「り→た」×1、「た→し」×1、「し→よ」×1、「よ→た」×1、「た→ん」×1、「ん→t」×1
を求めるだけでOKです。
注意点として、ここから元のしりとりに戻そうとすると1通りには決まりません。上のグラフで赤い矢印を全部使うしりとりを考えると、

• とうきょう→うじ→じゅうじょう→うじ→しんおおさか→…→たんばばし→しやくしょ→…→だいあん
• とうきょう→うじ→しやくしょ→…→たんばばし→じゅうじょう→うじ→しんおおさか→…→だいあん
• とうきょう→うじ→しんおおさか→…→たんばばし→じゅうじょう→うじ→しやくしょ→…→だいあん

のように、異なるしりとりを作ることができます。しかし、使う駅数に違いはないので、最長しりとりを探すという意味では問題になりません。これらのうちどれか1つを作れば、最長しりとりを具体的に示したことになります。

定式化

上のようなグラフと考え方により、最適化問題（数理計画問題）として、ソルバーライブラリ（問題を解くアルゴリズムを実装したライブラリ）で解けるようになります。以下の目的関数と制約条件をソルバーに入力します。

• （目的関数）使う枝の数を最大化する。
  • しりとりで使う駅の数に対応します（実際には枝の数から2を引いた数が駅数になりますが、以降では細かく書きません）。
• （制約条件）sから出る枝をちょうど1本だけ使うこと。
  • しりとりの始まりを表します。「好きな駅から始める」ために、sからの初手で好きな枝（道路）を1本選びます。
• （制約条件）tに入る枝をちょうど1本だけ使うこと。
  • しりとりの終わりを表します。どこでしりとりが詰まっても、必ずtへの枝（道路）はあるので、それを使ってtに進んでゴールします。
• （制約条件）s, t以外の各頂点について、出ていく枝と入ってくる枝は同じ数だけ使うこと。
  • 何かの単語が来たときに、次の単語を続けることを意味します。
  • しりとりの始まりの場合に限り、sから入ってくる頂点を使います。
  • しりとりの終わりの場合に限り、tに出ていく頂点を使います。
• （制約条件）グラフに存在する枝の数を超えて使うことはできない。
  • 一度使った単語を使えないことに対応します。
• （制約条件）使う枝の数は0以上の整数。

問題発生

文献⁴でも触れられていますが、実は上の制約条件で解いてしまうと、変な答えが出てきてしまうかもしれません。具体的には、以下のような答えが出てくる可能性があります。

赤枠内にあるsからtへの経路だけでなく、青枠や緑枠といった、sもtも通らない飛び地のループ経路ができてしまうのが問題です。これでは、得られた枝を全部使ったしりとりを作ることができません。
おかしいじゃないか！と思われるかもしれませんが、実は先に示した制約条件は全部ちゃんと満たしています。

そこで、もしこのような経路ができてしまったら、

• 「赤枠内のどれかの頂点」から「赤枠外のどれかの頂点」に出る枝をどれか1つ以上使う

という制約条件を加えて、もう一度解いてみます（文献で「分枝限定法」と書いてある所です）。
なお、赤枠内だけでしりとりは（最長かどうかは分かりませんが）成立していますので、先にこれを仮の結果として保存しておきます。

1. もし解が存在しなければ（全部の制約条件を満たすことができなくなったら）、今保存している仮の結果が、最終的な結果です。
2. もし解が存在して、青枠や緑枠のような飛び地がない経路が作れていれば、仮の結果と比べて、より長いしりとりが最終的な結果です。
3. もし、また飛び地のある解ができてしまったら、このときの新しいsからtへの経路を新しい赤枠で囲みます（今までの赤枠は忘れます）。もし、この赤枠内だけのしりとりが仮の結果より長いしりとりになっていれば、仮の結果を赤枠のしりとりで更新します。赤枠に対する制約条件をさらに1つ追加して解いてみます。（以後、繰り返し）

この繰り返しは1か2を満たしたときに終了しますが、3の場合であっても、（飛び地を含めた）赤い矢印の総数が、保存していた仮の結果の長さ以下になれば、そこで終了できます（なぜなら、しりとりの長さは赤い矢印の総数より大きくはならないからです）。
この繰り返しが終了することは、本当はちゃんと証明しないといけない気がしますが、よくわかりません。(^_^;)

解いてみよう

さて長々とアルゴリズムの話ばかりしていましたが、いよいよ解いてみます。

PuLP

今回はPuLP⁵というソルバーライブラリを使ってPythonで解きます。
以下の情報を参考にしました。線形計画問題（目的関数と制約条件が1次式）なら結構いろいろできるようです。

https://qiita.com/samuelladoco/items/703bf78ea66e8369c455
https://qiita.com/mzmttks/items/82ea3a51e4dbea8fbc17

事前準備として、開発環境で

terminal

$ pip install pulp

を実行しておきます。

なお、CygwinだとPuLPがうまく動かないっぽいです。

駅名リスト

駅は生き物です。新しくできることもあれば、廃止されることもあります。
定期的にメンテナンスされている駅名リストを発見したので、今回はそれを使います。
対象となる駅候補¹や同駅・別駅の基準²を元データに丸投げする効果もあります。(^_^;)

日本駅名語辞典（第9版）を使います。
ダウンロードしたファイルをExcelで開いて、オートフィルタを以下のように設定します。

• B列「駅名(漢字)」: 「"(貨)"で終わらない」（貨物専用駅を除外）
• I列「廃止」：「BRT」と「(空白セル)」をチェック（廃止駅を除外、BRTで存続している駅を含む）

フィルタをかけた状態で、B3:H9265をコピーしてテキストエディタに貼り付け（タブ区切りのテキストになります）、UTF-8で保存します。
このファイル名を ekimei_20170924.txt とします。

プログラム

220行ほどなので、全コード載せます。
実はソルバーを呼ぶところより、駅名リストを読み込んだり、解いた結果をしりとりに変換するところの方が大変だったりします。
実装が頭悪かったりするのは勘弁してください。あとコメントにここで説明していない用語とか書いているのも勘弁してください。

shiritori.py

#!/usr/bin/env python2.7
# -*- coding: utf-8 -*-

# modules
import sys
import itertools
import collections
import codecs
import pulp

# *** ↓ここから設定項目 ***

# 都道府県縛り
# 例えば以下のように指定します。[]だと縛りなし。
#prefs = [u"兵庫県", u"大阪府", u"京都府", u"奈良県", u"奈良県", u"和歌山県"]
#prefs = [u"宮崎県"]
prefs = []

# *** ↑ここまで ***

# 正規化テーブル
# 小文字->大文字
# 濁音・半濁音の有無は問題にしない
regtable = dict(zip(u"ゃゅょ", u"やゆよ") + \
                zip(u"がぎぐげござじずぜぞだぢづでどばびぶべぼぱぴぷぺぽ",
                    u"かきくけこさしすせそたちつてとはひふへほはひふへほ"))

# ソース（始まり）とシンク（終わり）
SOURCE = u"s"
SINK = u"t"

## 指定した点を通る閉路を1つ見つける関数
## 見つけた閉路は edges から除かれる (見つからなければそのまま)
def one_cycle(edges, start):
    path = [start]
    # 深さ優先探索（スタック）
    # start からの枝を列挙
    stack = [e[1] for e, cnt in edges.iteritems() if e[0] == start and cnt > 0]
    while len(stack) > 0:
        # 枝を1つ選ぶ
        e_new = (path[-1], stack[-1])
        edges[e_new] -= 1
        path.append(stack[-1])
        # 元の点に戻れたら終了
        if stack.pop() == start:
            return path
        # 今の地点から始まる枝を列挙
        dest_avail = [e[1] for e, cnt in edges.iteritems() if e[0] == e_new[1] and cnt > 0]
        if len(dest_avail) == 0:
            # 行き止まり: 1ステップ巻き戻す
            edges[e_new] += 1
            path.pop()
        else:
            # 行き先を列挙する
            stack += dest_avail
    # 閉路見つからず
    return None

## Euler 閉路を取り出す
def euler_cycle(edges, start):
    edges_tmp = edges.copy()
    # まず1個閉路を探す: 深さ優先探索 (edges_tmp から取り出した閉路が除かれる)
    cycle = one_cycle(edges_tmp, start)
    assert cycle is not None
    cycle_add = cycle
    while len(edges_tmp) > 0:
        # 閉路上の点のうち、出ていく枝の残っているものを選ぶ
        next_start = [v for v in set(cycle) if any(e[0] == v and cnt > 0 for e, cnt in edges_tmp.iteritems())]
        if len(next_start) == 0:
            # 別の連結成分があるので、諦める
            break
        else:
            # 別の閉路を探せ
            cycle_add = one_cycle(edges_tmp, next_start[0])
            assert cycle_add is not None
            # 選んだ開始点で元の閉路とつなげる
            idx = cycle.index(next_start[0])
            cycle = cycle[:idx] + cycle_add + cycle[idx+1:]
    return cycle

# solver の初期化と制約条件の設定
def make_solver(edges, vertexes, constraints):
    solver = pulp.LpProblem("Shiritori", pulp.LpMaximize)

    # 各枝に流すフローが変数に相当
    # 整数変数
    variables = dict((e, pulp.LpVariable(e, lowBound=0, cat="Integer")) for e in edges.keys())

    # 目的関数: フロー総和最大
    solver += sum(variables.values())

    # 制約条件
    # ソースから出るフロー、シンクに入るフローは1
    solver += sum([variables[e] for e in edges if e[0] == SOURCE]) == 1
    solver += sum([variables[e] for e in edges if e[1] == SINK]) == 1

    # 頂点ごとに出るフローと入るフローの総和が一致 (s, t以外)
    for v in vertexes:
        solver += sum([variables[e] for e in edges if e[0] == v]) \
               == sum([variables[e] for e in edges if e[1] == v]) 

    # フロー量制限
    for e, maxflow in edges.iteritems():
        solver += 0 <= variables[e] <= maxflow

    # 分枝限定法に関する制約条件の追加
    # 「cycle に含まれる点から、それ以外の点への遷移が1つ以上ある」
    for cons in constraints:
        solver += sum(variables[e] for e in cons) >= 1

    return solver, variables

def main():
    ## 駅名読み込む
    # とりあえず鉄道駅だけ
    stations = []
    with codecs.open("ekimei_20170924.txt", "r", "UTF-8") as f:
        for l in f:
            cols = l.rstrip("\n").split("\t")
            name, yomi, loc = cols[0], cols[1], cols[4]
            rail = cols[5] + cols[6]
            # フィルタリング設定
            if len(prefs) > 0 and not any(loc.startswith(x) for x in prefs):
                continue

            # 読みを正規化
            yomi_norm = u"".join([regtable.get(c, c) for c in yomi])
            if yomi_norm[-1] == u"ー": yomi_norm = yomi_norm[:-1]

            stations.append((name, yomi, yomi_norm, loc, rail))

    print >>sys.stderr, "総駅数:", len(stations)

    ## しりとり用グラフ作成
    # 枝リスト（と本数）: 有向グラフ
    # 枝（最初の文字と終わりの文字）ごとの駅リストも作成
    edges = collections.defaultdict(int)
    edges_sta = collections.defaultdict(set)
    for name, yomi, yomi_norm, loc, rail in stations:
        t = (yomi_norm[0], yomi_norm[-1])
        edges[t] += 1
        edges_sta[t].add((name, yomi, loc, rail))

    # ソースとシンクを加える
    vertexes = set(itertools.chain(*edges.iterkeys()))
    for v in vertexes:
        edges[(SOURCE, v)] = 1
        edges[(v, SINK)] = 1

    # *****
    # 最大流問題として整数計画法で解く

    length_tmp = 0
    solution_tmp = None
    constraints = []
    while True:
        solver, variables = make_solver(edges, vertexes, constraints)
        solver.solve()
        if solver.status != pulp.constants.LpStatusOptimal:
            # そのような解は無い: 現時点の解が最終的な解
            break

        # sから出る枝とtに入る枝を除いたものが、
        # （飛び地がないと仮定した場合の）しりとりの長さ（単語数）
        length_upper = int(pulp.value(solver.objective)+0.01) - 2

        # *****
        # 結果を加工

        # 使う枝を列挙
        # 簡単のため t -> s のパスを加えて閉路にしておく
        edges_sub = dict(itertools.ifilter(lambda (_, sol): sol > 0,
                                           ((e, variables[e].value()) for e in edges.iterkeys())))
        edges_sub[(SINK, SOURCE)] = 1

        # Euler 閉路を探す（どこから始めてもよいのでsに固定）
        cycle = euler_cycle(edges_sub, SOURCE)
        # cycle: s -> X1 -> ... -> Xn -> t -> s で、X1からXnまでの -> の数は len(cycle)-4
        length_lower = len(cycle) - 4
        print >>sys.stderr, length_lower, "/", length_upper,
        if length_lower == length_upper:
            # 連結グラフ
            print >>sys.stderr, "連結グラフ"
            if length_tmp < length_lower:
                # 解の更新
                length_tmp = length_lower
                solution_tmp = cycle
            # 今の解で確定
            break
        else:
            # 連結グラフでない
            # 解の更新ができないなら終わり
            print >>sys.stderr, "非連結グラフ"
            if length_upper <= length_tmp:
                break
            if length_tmp < length_lower:
                # 少なくとも今の解より良い解は見つかった
                length_tmp = length_lower
                solution_tmp = cycle
            print >>sys.stderr, "新たな解の探索を試みます"

            # 次回以降「cycle に含まれる点から、それ以外の点への遷移が1つ以上ある」
            # という条件を追加
            vertexes_cycle = [v for v in vertexes if v in cycle]
            vertexes_outofcycle = [v for v in vertexes if v not in cycle]
            # そのような遷移を列挙
            list_added_edges = [e for e in itertools.product(vertexes_cycle, vertexes_outofcycle) if e in edges]
            if len(list_added_edges) == 0:
                # 初めからそのような遷移がなければ終了
                break
            constraints.append(list_added_edges)

    # *****
    ## 駅名リストに変換

    print "起終点含む駅数", length_tmp
    for e1, e2 in itertools.izip(solution_tmp[1:-3], solution_tmp[2:-2]):
        # 与えられた最初と最後の文字に当てはまる駅を1つ選んで出力
        used = edges_sta[(e1, e2)].pop()
        print u"\t".join([e1, e2, used[1], used[0], used[2], used[3]]).encode("UTF-8")

if __name__ == "__main__":
    main()

結果

（注意：駅名リストが更新されると、結果は変わる可能性があります）

駅名リストに入っている9198駅のうち、最長で4128駅を使ったしりとりを作ることができました。

あ      ゆ      あかゆ          赤湯    山形県  JR東日本奥羽本線
ゆ      に      ゆに            由仁    北海道  JR北海道室蘭本線
に      に      にしいわくに    西岩国  山口県  JR西日本岩徳線
に      に      にしさまに      西様似  北海道  JR北海道日高本線
に      に      にしかに        西可児  岐阜県  名鉄広見線
に      く      にしきょうごく  西京極  京都府  阪急京都本線
（あまりに長すぎるので略）
つ      ま      つねやま      常山      岡山県  JR西日本宇野線
ま      て      まついやまて  松井山手  京都府  JR西日本片町線
て      ま      てんま        天満      大阪府  JR西日本大阪環状線
ま      ち      まつち        真土      愛媛県  JR四国予土線
ち      ら      ちくら        千倉      千葉県  JR東日本内房線
ら      ん      らくらくえん  楽々園    広島県  広島電鉄宮島線

この最初と最後だけを見ても、「あ」で始まる駅から始まり（きっと「あ」で終わる名前は多くないでしょうし）、最後は「ん」で終わっていて、なんだかそれっぽい？ですね。

都道府県縛りもできます。
例えば近畿2府4県（滋賀・京都・大阪・兵庫・奈良・和歌山）の駅、1337駅を使ってしりとりを作ると、最長で562駅のしりとりを続けることができました。

ゆ      さ      ゆあさ              湯浅      和歌山県  JR西日本紀勢本線
さ      き      さわらぎ            沢良宜    大阪府    大阪高速鉄道大阪モノレール線
き      た      きいながた          紀伊長田  和歌山県  JR西日本和歌山線
た      お      たけだお            武田尾    兵庫県    JR西日本福知山線
お      さ      おさ                長        兵庫県    北条鉄道
さ      み      さんようたるみ      山陽垂水  兵庫県    山陽電鉄本線
（やっぱり長すぎるので略）
し      せ      じぇいあーるながせ  ＪＲ長瀬  大阪府    JR西日本おおさか東線
せ      し      せっつし            摂津市    大阪府    阪急京都本線
し      へ      しんこうべ          新神戸    兵庫県    神戸市営地下鉄西神・山手線
へ      う      べんてんちょう      弁天町    大阪府    JR西日本大阪環状線
う      り      うぐいすのもり      鴬の森    兵庫県    能勢電鉄妙見線
り      ん      りょくちこうえん    緑地公園  大阪府    北大阪急行

今度は「ゆ」で始まりました。確かに「ゆ」で終わる駅も何となく少ない気がします。ちなみに、同じ562駅のしりとりを「あ」から作る方法もあるようです。

自由課題みたいな何か？

「問題発生」の項で、飛び地ができてしまう！という話をしましたが、使える単語数（駅数）が十分多ければ飛び地はできないと考えられます。
感覚的には、しりとりが長くなればなるほど、最初と最後の文字として使わずに済む仮名の種類が減っていくので、飛び地ができる余地がなくなっていくと理解できます。
（上のプログラムでは、飛び地ができずに済んだときに「連結グラフ」と出して結果を確定させ、飛び地ができてしまったときに「非連結グラフ」と出して新しい解の探索に移ります。）

というわけで、都道府県縛りを入れて、使える単語数を減らすと飛び地ができるかもしれません。飛び地ができたときに何が起こるか様子を見てみます。

• 上のプログラムで prefs = [u"宮崎県"] とすると、（私の環境では）最初に飛び地のある結果が見つかり、再三の再探索の末、結局最初に見つかった長さ16のしりとりが最終結果になりました。
• 同じく prefs = [u"滋賀県"] とすると、（私の環境では）最初に飛び地のある結果が見つかり、長さ20のしりとりが仮に保存されました。その後、再探索により長さ26のしりとりに更新され、確定しました。

最後に

今回はPython + PuLPライブラリを使って遊んでみました。
Python自体の影は薄かった気がしないでもないですが、それでもいろいろ条件を変えて遊べるのがプログラムですね。
題材にはたまたま駅名を使いましたが、データを読み込むところを変えればいろんなものでしりとりできます。まあ、今回のように整備されたリストがないと、遊ぶ以前に単語リストを集める段階で心が折れそうですけども。

1. ここでは日本国内を走る鉄道・軌道、路面電車、ケーブルカー、ロープウェイ等の、旅客営業を行っている駅（停留場を含みます）とします。臨時駅でもOKですが、貨物専用駅は含めないこととします。また既に廃止された駅は使えません。 ↩ ↩²

2. 「別の場所」の定義も実は難しいですが、適当に決めれば良いだけなので、あまり深く立ち入りません。 ↩ ↩²

3. これを同一視すると、ルール2との合わせ技で「じ」「し」「ぢ」「ち」を全部同一視することになりますが、さすがに無理があります。 ↩

4. 品野勇治, 乾伸雄: 最長しりとり問題とその解法（OR研究の最前線）, オペレーションズ・リサーチ : 経営の科学, Vol. 50(3), pp. 175-180, 2005-03-01 ↩ ↩²

5. この記事を書いた時点でのバージョンは1.6.8。 ↩