एकाधिक अनुक्रमों के लिए सबसे लंबा आम परिणाम

Question

मैंने एम = 2 अनुक्रमों के लिए सबसे लंबे समय तक खोजने के लिए शोध का एक गुच्छा किया है, लेकिन मैं यह समझने की कोशिश कर रहा हूं कि एम> = 2 अनुक्रमों के लिए इसे कैसे किया जाए। मुझे एन और एम: एम अनुक्रम, एन अद्वितीय तत्वों के साथ दिया जा रहा है। एन {1 - एन} का सेट है। मैंने गतिशील प्रोग्रामिंग दृष्टिकोण के बारे में सोचा है, लेकिन मैं अभी भी उलझन में हूं कि वास्तव में इसे कैसे शामिल किया जाए।

उदाहरण इनपुट
5 3
5 3 4 1 2
2 5 4 3 1
5 2 3 1 4

यहां अधिकतम अनुक्रम देखा जा सकता है होना करने के लिए

ऍक्स्प ected उत्पादन
लंबाई = 3

Answer 1

एक साधारण विचार।

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), अगर आप पहले से पदों की मैट्रिक्स की गणना है।

Answer 2

आप "Design of a new Deterministic Algorithm for finding Common DNA Subsequence" कागज पर गौर कर सकते हैं। आप डीएजी (पीजी 8, आकृति 5) बनाने के लिए इस एल्गोरिदम का उपयोग कर सकते हैं। डीएजी से, सबसे आम आम विशिष्ट अनुवर्ती पढ़ें। फिर एम के मूल्य का उपयोग करके उस पर एक गतिशील प्रोग्रामिंग दृष्टिकोण आज़माएं ताकि यह तय किया जा सके कि प्रति अनुक्रम बनाने के लिए आपको कितने डीएजी की आवश्यकता है। मूल रूप से इन अनुक्रमों को कुंजी के रूप में उपयोग करें और संबंधित अनुक्रम संख्याओं को संग्रहीत करें जहां यह पाया जाता है और फिर सबसे बड़ा अनुवर्ती (जो 1 से अधिक हो सकता है) खोजने का प्रयास करें।

Answer 3

जब से तुम अद्वितीय तत्व है, @Nikita रयबाक के जवाब के साथ जाने के लिए है, लेकिन जब से तुम गतिशील प्रोग्रामिंग उल्लेख किया है, इस तरीके से डी पी का उपयोग करेंगे आप दो से अधिक दृश्यों जब बताया गया है:

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] पर बैकट्रैक और वर्ण मुद्रित करें। यदि नहीं, उपरोक्त मानों के अधिकतम के अनुसार बैकट्रैक।