2014-06-07
最長しりとりは、 勉強会でやっている。こんな感じ。
from pulp import * with open('cpp11_keywords.csv') as fp: l = [s.rstrip() for s in fp.readlines()] nl = len(l) rl = range(nl) arcs = [] # アークとする aout = [[] for i in rl] # 出るアーク ain = [[] for i in rl] # 入るアーク for i in rl: si = l[i][-1:] for j in rl: if i == j: continue sj = l[j][:1] if si == sj: k = len(arcs) aout[i].append(k) ain[j].append(k) arcs.append((i, j, k)) na = len(arcs) m = LpProblem('shiritori', LpMaximize) va = [LpVariable('a%d' % i, upBound=nl, cat=LpBinary) for i in range(na)] # アークを選ぶかどうか vs = [LpVariable('s%d' % i, lowBound=0, upBound=1) for i in rl] # 先頭かどうか vp = [LpVariable('p%d' % i, lowBound=0, upBound=nl) for i in rl] # 先頭からの距離 m += lpSum(va) m += lpSum(vs) == 1 for i in rl: so = lpSum(va[j] for j in aout[i]) si = lpSum(va[j] for j in ain[i]) + vs[i] m += so <= si m += si <= 1 for i, j, k in arcs: m += vp[i] + 1 <= vp[j] + nl * (1 - va[k]) %time m.solve() print int(value(m.objective) + 1) p = sum(i * int(value(vs[i])) for i in rl) while p >= 0: print l[p], t = -1 for h in aout[p]: i, j, k = arcs[h] if value(va[k]) > 0.5: t = j break p = t
コードも短いし、計算も速い(1秒かからず)。