최단 공통 슈퍼시퀀스 문제

컴퓨터 과학에서, X와 Y의 두 시퀀스 중 가장 짧은 공통 초서열은 X와 Y를 후속으로 하는 가장 짧은 시퀀스이다.이것은 가장 일반적인 서브시퀀스 문제와 밀접하게 관련된 문제입니다.X = < x₁ , ...x_m > 및 Y = < y₁ , ... , y_n >의 2개의 배열이 주어졌을 때, U = < u , u_k >는₁ U에서 항목을 제거하여 X와 Y를 생성할 수 있는 경우 X와 Y의 공통 슈퍼 배열이다.

Shortest Common Super Sequence(SCS; 최단 공통 초서열)는 최소 길이의 공통 초서열입니다.최단 공통 슈퍼시퀀스 문제에서는 두 개의 시퀀스 X와 Y가 주어지며, 과제는 이들 시퀀스의 가능한 최단 공통 슈퍼시퀀스를 찾는 것이다.일반적으로 SCS는 고유하지 않습니다.

2개의 입력 시퀀스에 대해 SCS는 가장 긴 공통 서브시퀀스(LCS)에서 쉽게 형성할 수 있습니다.예를 들어 X${\displaystyle }$[ ${\displaystyle 1}$. ${\displaystyle m}$]$=$ ${\displaystyle a}$ ${\displaystyle b}$ c ${\displaystyle b}$ ${\displaystyle d}$ a$$ b b b b \ $displaystyle [ 1$ . m ]= $bbdab$y yY ${\displaystyle \mathrm{}}$${\displaystyle 1}$ .${\displaystyle n}$] $=$ ${\displaystyle b}$ d ${\displaystyle c}$ ${\displaystyle a}$ ${\displaystyle b}$a { $displaystyle [1$. n ]= $bdcaba$}는${\displaystyle }$Z [ ${\displaystyle 1}$.$L$$$$L]=bcba$ 원래의 순서를 유지하면서 비 LCS 기호를 Z에 삽입함으로써 최단 공통 슈퍼시퀀스 U${\displaystyle \mathrm{1..]}}$를 얻는다.$display$$1$$S]=abdcabdab$ 특히${\displaystyle ,}$ ${\displaystyle L}$ + ${\displaystyle S}$= ${\displaystyle m}$+ n \ $display style$L+S$= m$+ n 은 $임의$의 두 입력 시퀀스에 대해 유지됩니다.

3개 이상의 입력 시퀀스의 최단 공통 시퀀스와 최장 공통 시퀀스는 유사한 관계가 없습니다.(특히 LCS와 SCS는 이중 문제가 아닙니다.)그러나 동적 프로그래밍을 사용하여 두 문제를 O$(n k)$ 시간 내에 $해결$할 수 있습니다. $여기$서 k$(\style$ k$)$는 시퀀스 수이고 n$(\display style$ n$)$은 $최대$ 길이입니다.임의의 수의 입력 시퀀스의 일반적인 경우 문제는 ^[1]NP-hard입니다.

최단 공통 초끈

유한한 문자열 집합의 슈퍼스트링인 최소 길이의 문자열을 찾는 것과 밀접하게 관련된 문제S= {s₁,s₂,...s_n }도 ^[2]NP-hard입니다.여러 해 동안 여러 개의 상수 요인 근사치가 제안되었으며, 현재 가장 잘 알려진 알고리즘의 근사 계수는 2.4783입니다.^[3]단, 아마도 가장 간단한 해결책은 세트커버 인스턴스에 대한 최적의 솔루션의 무게가 최단 슈퍼스트링 길이의 2배 미만이 되도록 문제를 가중치 세트커버 인스턴스로 재구성하는 것이다.S그런 다음 가중치 세트 커버의 O(log)-n근사를 사용하여 O(log)를 얻을 수 있습니다.n))) 최단 슈퍼스트링에 대한 근사치(상수 요인 근사치가 아님에 유의하십시오.

임의의 문자열에 대해x이 알파벳에서 정의P(x)의 서브스트링인 모든 문자열의 집합이 됩니다.x. 인스턴스I세트 커버의 공식은 다음과 같습니다.

• 허락하다M텅 비다
• 각 문자열 쌍에 대해s_i 그리고s마지막인_j 경우k의 상징.s_i 처음과 같다k의 상징.s에 문자열을 추가합니다_j.M최대 겹침과의 연결로 구성되다s_i 와 함께s를 클릭합니다_j.
• set cover instance의$universe{\displaystyle \mathcal{}}$U(\$displaystyle\mathcal$ {U$$$})$를 정의한다.S
• {\cHBFFFFF}이 되는 우주의 서브셋을 정의합니다.P(x)x∈S∪M}
• 각 서브셋의 비용 정의P(x)가 되는 것x, 의 길이x.

인스턴스I그런 다음 가중치 세트커버를 위한 알고리즘을 사용하여 해결할 수 있으며 알고리즘은 문자열의 임의 연결을 출력할 수 있습니다.x가중치 세트커버 알고리즘이 출력하는 값P(x를 참조해 주세요.^[4]

예

세트를 고려하다S= { abc, cde, fab}, 이것은 가중치 세트 커버 인스턴스의 우주가 됩니다.이 경우,M= { abcde, fabc }.그럼 우주의 부분 집합은

${\displaystyle {begin {aligned}\{P(x) x\in S\cup M\}&={P(x) x\in \{abc,cde,fabc\}\&={P(abc),P(fab(ABc),}\}\&=\{a,b,c,ab,bc,cde\},\ldots,\{f,a,cd,de,cde\},\ldots,\{f,a,c,ab,bc,bc,bc,bc,bc,bc,bc\}\}\}\\\\\\\\\\end{a,\\\end{aligned{alled {aligned}$

가격은 각각 3, 3, 3, 5, 4 입니다.

레퍼런스

• Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. p. 228 A4.2: SR8. ISBN 0-7167-1045-5. Zbl 0411.68039.
• Szpankowski, Wojciech (2001). Average case analysis of algorithms on sequences. Wiley-Interscience Series in Discrete Mathematics and Optimization. With a foreword by Philippe Flajolet. Chichester: Wiley. ISBN 0-471-24063-X. Zbl 0968.68205.
• Vazirani, Vijay V. (2001), Approximation Algorithms, Springer-Verlag, ISBN 3-540-65367-8

외부 링크

• 알고리즘 및 데이터 구조 사전: 최단 공통 슈퍼시퀀스