Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

最長しりとりを解く

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

定式化

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした