組合せ最適化で最短超文字列問題を解く

これなに

最短超文字列問題を組合せ最適化で解いてみましょう。

最短超文字列問題とは(上記記事より)

入力：文字列の集合 $S = \{s_1, s_2, ..., s_n\}$
出力：$S$ 中のすべての文字列を部分文字列として含む最短の文字列の長さ

$S = \{AGA, CTAG, GATC\}$ ならば、最短超文字列は $CTAGATC$。
$S = \{CATGC, ATGCAT, CTAAGT, GCTA, TTCA\}$ ならば、最短超文字列は $GCTAAGTTCATGCAT$。

考え方

文字列の集合から部分文字列となるものを除いて、空文字列("")を追加しておきます。
文字列間の距離を伸びる長さとすれば、最短超文字列問題は、巡回セールスマン問題そのものです。
早速、やってみましょう。

Pythonプログラム

以下のプログラムは厳密解を求めるので、サイズが増えると、解けなくなるのでご注意ください。

python3

def overlap(s,t):
    """sとtの重なりの長さ"""
    m = len(s)
    n = max(0, m-len(t))
    for i in range(n,m):
        if s[i:] == t[:m-i]:
            return m-i
    return 0

def shortest_superstring(words):
    """最短超文字列問題"""
    from ortoolpy import tsp
    words = ['']+words
    n = len(words)
    dist = {(i,j):len(t)-overlap(s,t) for i,s in enumerate(words)
            for j,t in enumerate(words) if i != j}
    _,lst = tsp(words,dist)
    return ''.join(words[j][len(words[j])-dist[i,j]:] for i,j in zip(lst,lst[1:]))

確認その1

python3

shortest_superstring('AGA CTAG GATC'.split())
>>>
'CTAGATC'

確認その2

python3

shortest_superstring('CATGC ATGCAT CTAAGT GCTA TTCA'.split())
>>>
'GCTAAGTTCATGCAT'

どちらも合っています。

以上