여러 시퀀스에 대해 가장 긴 공통 서브 시퀀스

Question

M = 2 시퀀스에 대해 가장 길게 찾는 연구를 수행했지만 M> = 2 시퀀스에서이를 수행하는 방법을 파악하려고합니다. N 개의 고유 요소가있는 N 및 M : M 시퀀스가 ​​제공됩니다. N은 {1 - N}의 집합입니다. 동적 프로그래밍 접근 방식에 대해 생각해 봤지만 실제로 통합하는 방법에 대해서는 여전히 혼란 스럽습니다.

여기서 최대 시퀀스 알 수
5 3
5 3 4 1 2
2 5 4 3 1
5 2 3 1 4

예

입력 될
5 3 1

특급 산출 된 출력
길이 = 3

Answer 1

간단한 생각.

각 숫자가 i이고 범위가 1이고 N 인 경우 마지막 숫자가 i 인 가장 긴 하위 시퀀스를 계산하십시오. (a[i]이라고 부름)

이렇게하려면 처음부터 끝까지 첫 번째 시퀀스에서 숫자 i을 반복합니다. a[i] > 1 인 경우 숫자 j이 각 순서대로 i 앞에옵니다.
j의 가능한 모든 값을 확인하고 (이전 조건이 성립하는 경우) a[i] = max(a[i], a[j] + 1)을 확인하면됩니다.

마지막 비트는 j이 첫 번째 시퀀스에서 i 앞에 오기 때문에 a[j]이 이미 계산되었음을 의미합니다.

for each i in first_sequence 
    // for the OP's example, 'i' would take values [5, 3, 4, 1, 2], in this order 
    a[i] = 1; 
    for each j in 1..N 
     if j is before i in each sequence 
      a[i] = max(a[i], a[j] + 1) 
     end 
    end 
end 

사전에 위치 행렬을 계산하면 O(N^2*M)입니다.

Answer 2

"Design of a new Deterministic Algorithm for finding Common DNA Subsequence"용지를 볼 수 있습니다. 이 알고리즘을 사용하여 DAG를 구성 할 수 있습니다 (8 페이지, 그림 5). DAG에서 가장 큰 공통적 인 하위 시퀀스를 읽습니다. 그런 다음 M 값을 사용하여 시퀀스 당 생성해야하는 DAG 수를 결정하는 동적 프로그래밍 방식을 시도하십시오. 기본적으로 이러한 하위 시퀀스를 키로 사용하고 해당 시퀀스 번호가있는 위치에 저장 한 다음 최대 하위 시퀀스 (1보다 클 수 있음)를 찾으려고합니다.

Answer 3

는 독특한 요소를 가지고 있기 때문에, @Nikita 리박의 대답은 함께 갈 수있는 하나이지만, 동적 프로그래밍을 언급 한 이후, 여기에 두 개 이상의 시퀀스가있을 때 당신은 DP를 사용하십시오 방법은 다음과 같습니다

dp[i, j, k] = length of longest common subsequence considering the prefixes 
       a[1..i], b[1..j], c[1..k]. 


dp[i, j, k] = 1 + dp[i - 1, j - 1, k - 1] if a[i] = b[j] = c[k] 
      = max(dp[i - 1, j, k], dp[i, j - 1, k], dp[i, j, k - 1]) otherwise 

을 실제 하위 시퀀스를 다시 얻으려면 dp[a.Length, b.Length, c.Length]에서 시작하는 재귀 함수를 사용하고 기본적으로 위의 수식을 역순으로 바꾸십시오. 세 요소가 같으면 dp[a.Length - 1, b.Length - 1, c.Length - 1]으로 역 추적하여 문자를 인쇄하십시오. 그렇지 않은 경우 위의 값 중 최대 값에 따라 역 추적하십시오.