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

最長しりとりを解く

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

定式化

典型問題の中の2部グラフの最大マッチング問題の変種になります。
しりとりに使われる単語を$kw$とします。
$kw$を左右にそれぞれ並べ、左を先行、右を後行とします。そして、つながる場合に線を引くことを考えます。下記の図では、"alignas"の後に"sizeof"を繋げることを表しています。

この線を引くか引かないかを$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++予約語から最長のしりとりを作ろう！」
数独を組合せ最適で解く
献立を組合せ最適化で考える
洗濯物を干しながら最適化してみた