多個序列的最長公共子序列

我已經做了大量的研究以找到M = 2個序列中最長的一個，但我想弄清楚如何對M> = 2個序列做它。我被賦予N和M：M序列，並帶有N個獨特元素。 N是{1 - N}的集合。我曾考慮過動態編程方法，但我仍然對如何實際納入它感到困惑。多個序列的最長公共子序列

實施例輸入
5 3
5 3 4 1 2
2 5 4 3 1
5 2 3 1 4

這裏的最大序列可被看作是

精通輸出
長度= 3

來源

2011-04-22 mkobit

你可以發佈你到目前爲止嘗試過的方法嗎？從那裏，我們可以指出你在正確的方向。 – 2011-04-22 04:11:57

M是子序列必須存在的序列數量？ – BiGYaN 2011-04-22 04:17:06

@Jerry第一行指定N和M.這對C比賽/作業問題規範來說是正常的:) – 2011-04-22 05:17:40

一個簡單的想法。

對於1和N之間的每個數字i，計算最後一個數字爲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)，如果你事先計算位置矩陣。

來源

2011-04-22 04:38:16

我認爲這大部分是正確的，但是你寫的僞裝很混亂。它看起來像'我'迭代序列列表，但不應該從'1'迭代到'N'？我猜你認爲'sequences [0]'是第一個序列，因此包含所有元素'1 .. N'，但我認爲像寫給'j'所寫的那樣更清晰。 – IVlad 2011-04-22 10:09:32

@IVlad是的，它應該迭代迭代從1到N的所有數字，但也按照正確的順序。但是你是對的，這個僞碼很混亂。我已經澄清了一點。不確定是否可以更好地呈現「訂單」要求。 – 2011-04-22 10:15:19

非常感謝您，我花了一點時間來了解這裏發生了什麼，但現在是有道理的。 – mkobit 2011-04-30 14:37:42

您可以查看「Design of a new Deterministic Algorithm for finding Common DNA Subsequence」論文。您可以使用此算法構建DAG（第8頁，圖5）。從DAG中讀取最大的常見不同子序列。然後嘗試一種動態編程方法，使用M的值來確定每個序列需要構建多少個DAG。基本上使用這些子序列作爲密鑰並存儲相應的序列號，然後嘗試找到最大的子序列（可以大於1）。

來源

2011-04-22 04:25:54 BiGYaN

既然你有獨特的元素，@Nikita Rybak的的回答是一個一起去，但既然你提到的動態規劃，這裏是你如何使用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]並打印該字符。如果不是，則根據上述值的最大值進行回溯。

來源

2011-04-22 11:21:06 IVlad

多個序列的最長公共子序列

回答

相關問題