Python
数学
最適化
パズル
組合せ最適化

最長しりとりを組合せ最適で解く


最長しりとりを解く

組合せ最適化を使うと最長しりとりも簡単に解けます。


定式化

典型問題の中の2部グラフの最大マッチング問題の変種になります。

しりとりに使われる単語を$kw$とします。

$kw$を左右にそれぞれ並べ、左を先行、右を後行とします。そして、つながる場合に線を引くことを考えます。下記の図では、"alignas"の後に"sizeof"を繋げることを表しています。

image

この線を引くか引かないかを$x_{ij} \in {0, 1}$で表すことにします。

$\mbox{objective}$
$\sum_i{\sum_j{x_{ij}}}$
なるべく繋げる (0)

$\mbox{variables}$
$x_{ij} \in \{0, 1\} ~ \forall i, j$
$kw_i$の次が$kw_j$かどうか (1)

$y_i \ge 0 ~ \forall i$
$kw_i$が先頭かどうか (2)

$z_i \ge 0 ~ \forall i$
$kw_i$の順番 (3)

$\mbox{subject to}$
$\sum_j{x_{ij}} = 1 ~ \forall i$
$kw_i$から出る数は1以下 (4)

$\sum_j{x_{ji}} = 1 ~ \forall i$
$kw_i$へ入る数は1以下 (5)

$\sum_j{x_{ij}} \le \sum_j{x_{ji}} + y_i ~ \forall i$
$y$に関する制約 (6)

$z_i \le z_j + 1-(n+1)\times(1-x_{ij}) ~ \forall i, j$
$z$に関する制約 (7)

$\sum_i{y_i} = 1$
先頭は1つだけ (8)


Pythonで解く

C++のキーワード84個を使ってみましょう。キーワードは、文字列の配列(kw)に入っているとします。


python

kw = "alignas,alignof,and,and_eq,asm,auto,bitand,bitor,bool,break,case," \

"catch,char,char16_t,char32_t,class,compl,const,constexpr,const_cast," \
"continue,decltype,default,delete,do,double,dynamic_cast,else,enum," \
"explicit,export,extern,false,float,for,friend,goto,if,inline,int,long," \
"mutable,namespace,new,noexcept,not,not_eq,nullptr,operator,or,or_eq," \
"private,protected,public,register,reinterpret_cast,return,short," \
"signed,sizeof,static,static_assert,static_cast,struct,switch,template," \
"this,thread_local,throw,true,try,typedef,typeid,typename,union," \
"unsigned,using,virtual,void,volatile,wchar_t,while,xor,xor_eq".split(',')

pulpを使って定式化して解いてみましょう。


python

from pulp import * # pip install pulp

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)
%time 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
>>>
35
[1]alignas -> [2]signed -> [3]default -> [4]typedef ->
[5]friend -> [6]do -> [7]operator -> [8]reinterpret_cast ->
[9]thread_local -> [10]long -> [11]goto -> [12]or ->
[13]register -> [14]return -> [15]new -> [16]wchar_t ->
[17]true -> [18]export -> [19]throw -> [20]while ->
[21]else -> [22]enum -> [23]mutable -> [24]explicit ->
[25]this -> [26]static -> [27]class -> [28]sizeof ->
[29]float -> [30]template -> [31]extern -> [32]noexcept ->
[33]typeid -> [34]dynamic_cast -> [35]try

規模が大きい場合は、最長しりとり問題の解法を参考にしてください。

2017/1/16 追記

ループを含む解を避けるために、変数zを追加しました。ループがあると式(7)が成り立たなくなります。

参考:

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

CodeIQ 「組合せ最適化:C++予約語から最長のしりとりを作ろう!」

数独を組合せ最適で解く

献立を組合せ最適化で考える

洗濯物を干しながら最適化してみた