はじめに
東急線に乗っていた時にURBAN HACKSという広告を目にしました。
広告には、東急電鉄全96駅の駅名でしりとりを行った際に最長となる組み合わせを算出せよという問題が書かれていました。
サマーウォーズのケンジ君のように、こういう問題は解いてみたくなります。
よろしくお願いしまぁーす！
結論
東急電鉄96駅の最長駅名しりとり結果は 25 と分かりました。
（合ってるか知りたい…）
結果
[1]すずかけだい -> [2]いちがお -> [3]おやまだい -> [4]いしかわだい -> [5]いけがみ ->
[6]みょうれんじ -> [7]じゆうがおか -> [8]かじがや -> [9]やました -> [10]たな ->
[11]ながつた -> [12]たまがわ -> [13]わかばやし -> [14]しぶや -> [15]やぐちのわたし ->
[16]しもしんめい -> [17]いけじりおおはし -> [18]しょういんじんじゃまえ -> [19]えばらまち -> [20]ちどりちょう ->
[21]うのき -> [22]きたせんぞく -> [23]くほんぶつ -> [24]つなしま -> [25]まつばら
内容
事前にpipでnumpyと、線形計画法のソルバーライブラリであるPulPをインストールしてください。
terminal
$ pip install numpy
$ pip install pulp
以下コードを実行することで結果が得られます。コードは参考記事を全面的に写させていただきました。
python
from pulp import * # pip install pulp
import numpy as np
kw = "あおばだい,あざみの,いけがみ,いけじりおおはし,いしかわだい,いちがお,うのき,えだ,えばらなかのぶ,えばらまち," \
"おおいまち,おおおかやま,おおくらやま,おおさきひろこうじ,おくさわ,おやまだい,おんだ,おんたけさん," \
"がくげいだいがく,かじがや,かまた,かみのげ,かみまち,きくな,きたせんぞく,くがはら,くほんぶつ,ごたんだ," \
"こどものくに,こまざわだいがく,さぎぬま,さくらしんまち,さんげんちゃや,しぶや,しもしんめい,しもたかいど," \
"しもまるこ,じゆうがおか,しょういんじんじゃまえ,しんまるこ,すずかけだい,せたがや,せんぞく,せんぞくいけ," \
"だいかんやま,たかつ,たな,たまがわ,たまぷらーざ,たんまち,ちどりちょう,ちゅうおうりんかん,つきみの,つくしの," \
"つなしま,でんえんちょうふ,とごしぎんざ,とごしこうえん,とどろき,とりつだいがく,ながつた,なかのぶ,ながはら," \
"なかめぐろ,にしこやま,にしたいしどう,ぬまべ,はくらく,はすぬま,はたのだい,ひがしはくらく,ひよし,ふじがおか," \
"ふたこしんち,ふたこたまがわ,ふどうまえ,まつばら,みぞのくち,みどりがおか,みなみまちだぐらんべりーぱーく," \
"みやざきだい,みやのさか,みやまえだいら,みょうれんじ,むさしこすぎ,むさしこやま,むさしにった,めぐろ," \
"もとすみよし,やぐちのわたし,やました,ゆうてんじ,ゆきがやおおつか,ようが,よこはま,わかばやし".split(',')
print(len)
n, r = len(kw), range(len(kw))
m = LpProblem(sense=LpMaximize) # 数理モデル
x = [[0 if kw[i][-1] != kw[j][0] else LpVariable('x%d_%d'%(i,j), cat=LpBinary)
for j in r] for i in r] # kw_i から kw_j に繋げるかどうか (1)
y = [LpVariable('y%d'%i, lowBound=0) for i in r] # kw_iが先頭かどうか (2)
z = [LpVariable('z%d'%i, lowBound=0) for i in r] # kw_iの順番 (3)
m += lpSum(x[i][j] for i in r for j in r) # なるべく繋げる (0)
for i in r:
cou = lpSum(x[i][j] for j in r) # kw_i から出る数
cin = lpSum(x[j][i] for j in r) # kw_i へ入る数
m += cou <= 1 # kw_i から出る数は1以下 (4)
m += cin <= 1 # kw_i へ入る数は1以下 (5)
m += cou <= cin + y[i] # yに関する制約 (6)
for j in r:
m += z[i] <= z[j]-1+(n+1)*(1-x[i][j]) # zに関する制約 (7)
m += lpSum(y) == 1 # 先頭は1つだけ (8)
m.solve() # 求解
print(int(value(m.objective)) + 1) # 最長しりとり数
rr = range(1,n+1)
vx = np.vectorize(value)(x).astype(int)
i, s = 0, int(np.vectorize(value)(y)@rr)
while s:
if i:
print(' -> ', end='')
i += 1
print('[%d]%s'%(i,kw[s-1]), end=' ')
s = vx[s-1]@rr
感想
- 線形計画法も最大マッチング問題の何たるかも分かってないのにそれっぽいことができるPythonしゅごい…。
- アルゴリズムがわかっていないので検算ができません。目下勉強中。
参考