Loading article…
コンピュータサイエンスでは、2 つのシーケンスXとYの最短共通スーパーシーケンスは、 XとYを部分シーケンスとして持つ最短のシーケンスです。これは、最長共通部分シーケンス問題と密接に関連した問題です。2 つのシーケンスX = < x 1 ,...,x m > とY = < y 1 ,...,y n > が与えられたとき、シーケンスU = < u 1 ,...,u k > は、 Uから要素を削除してXとYを生成できる場合、 XとYの共通スーパーシーケンスです。
最短共通スーパーシーケンス（SCS）とは、最小長の共通スーパーシーケンスのことです。SCS問題では、2つのシーケンスXとYが与えられ、これらのシーケンスの最短共通スーパーシーケンスを見つけることが課題となります。一般に、SCSは一意ではありません。
2 つの入力シーケンスに対して、最長共通部分列(LCS)から SCS を簡単に形成できます。たとえば、Xの最長共通部分列はそしてYZです非LCSシンボルを元の順序を維持したままZに挿入することで、最短共通スーパーシーケンスUが得られます。特に、方程式これは任意の2つの入力シーケンスに対して成り立つ。
3つ以上の入力シーケンスの最短共通スーパーシーケンスと最長共通サブシーケンスの間には、同様の関係はありません。（特に、LCSとSCSは双対問題ではありません。）しかし、どちらの問題も解決できます。動的計画法を用いた時間、はシーケンスの数であり、はそれらの最大長です。任意の数の入力シーケンスの一般的な場合、この問題はNP困難です。[ 1 ]
文字列の有限集合S = { s 1 , s 2 ,..., s n }のスーパーストリングである最小長の文字列を見つけるという密接に関連する問題も NP 困難です。[ 2 ]さらに、 APX完全です。[ 3 ] 長年にわたっていくつかの定数係数近似が提案されており、現在知られている最良のアルゴリズムの近似係数は 2.475 です。[ 4 ]しかし、おそらく最も簡単な解決策は、セット カバー インスタンスの最適解の重みが最短スーパーストリングSの長さの 2 倍未満になるように問題を重み付きセット カバーのインスタンスとして再定式化することです。そうすれば、重み付きセット カバーのO(log( n )) 近似を使用して、最短スーパーストリングのO(log( n )) 近似を得ることができます (これは定数係数近似ではないことに注意してください)。
このアルファベットに含まれる任意の文字列xに対して、 P ( x ) をxの部分文字列であるすべての文字列の集合と定義する。集合被覆のインスタンスIは次のように定式化される。
このインスタンスは、重み付き集合被覆アルゴリズムを使用して解くことができ、このアルゴリズムは、重み付き集合被覆アルゴリズムが P(x) を出力する文字列 x の任意の連結を出力することができる。[ 5 ]
重み付き集合被覆インスタンスの全体集合となる集合S = { abc, cde, fab } を考えます。この場合、M = { abcde, fabc } となります。すると、全体集合の部分集合の集合は次のようになります。
それぞれのコストは3、3、3、5、4です。
![{\displaystyle [1..m]=abcbdab}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a81f42392c43a0b0298789a903338bf76dc97223)
![{\displaystyle [1..n]=bdcaba}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c34a14553055e81f2d6a800b4b8a81818503a8b)
![{\displaystyle [1..L]=bcba}](https://wikimedia.org/api/rest_v1/media/math/render/svg/650337a86ee10a285698a036e6bc6c051142551a)
![{\displaystyle [1..S]=abdcabdab}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d2cc9828f4d32339be1fc26d946996bd3da65e3)
