डीएए - सबसे लंबा सामान्य परिणाम
सबसे लंबे समय तक चलने वाली सामान्य समस्या सबसे लंबे अनुक्रम का पता लगा रही है जो कि दिए गए तार में मौजूद है।
परिणाम को
आइए एक अनुक्रम पर विचार करें S = <s 1 , s 2 , s 3 , s 4 ,…, s n >।
एक सीक्वेंस Z = <z 1 , z 2 , z 3 , z 4 ,…, z m > S पर S को S का आफ्टरनून कहा जाता है, अगर और केवल अगर इसे कुछ तत्वों के S डिलीट से प्राप्त किया जा सकता है।
सामान्य परिणाम
मान लीजिए, X तथा Yतत्वों के एक सीमित सेट पर दो अनुक्रम हैं। हम कह सकते हैं किZ का एक सामान्य परिणाम है X तथा Y, अगर Z दोनों का एक परिणाम है X तथा Y।
सबसे लंबा सामान्य परिणाम
यदि अनुक्रम का एक सेट दिया जाता है, तो सबसे लंबे समय तक चलने वाली समस्या बाद में उन सभी अनुक्रमों की एक सामान्य अनुवर्तीता है जो अधिकतम लंबाई का है।
सबसे लंबी सामान्य अनुवर्ती समस्या एक क्लासिक कंप्यूटर विज्ञान की समस्या है, जो डेटा उपयोगिता कार्यक्रमों जैसे कि डिफरेंट-यूटिलिटी का आधार है, और इसमें जैव सूचना विज्ञान के अनुप्रयोग हैं। यह संशोधन नियंत्रण प्रणालियों द्वारा भी व्यापक रूप से उपयोग किया जाता है, जैसे कि SVN और Git, फ़ाइलों के संशोधन-नियंत्रित संग्रह में किए गए कई परिवर्तनों को समेटने के लिए।
Nave विधि
लश्कर X लंबाई का एक क्रम हो m तथा Y लंबाई का एक क्रम n। के हर बाद के लिए जाँच करेंX चाहे वह इसके बाद का हो Y, और सबसे लंबे समय तक पाए जाने वाले सामान्य परिणाम लौटाएं।
वहां 2m के बाद के X। परीक्षण अनुक्रम है या नहीं यह एक के बाद हैY लेता है O(n)समय। इस प्रकार, भोले एल्गोरिदम ले जाएगाO(n2m) समय।
गतिशील प्रोग्रामिंग
चलो एक्स = <एक्स 1 , एक्स 2 , एक्स 3 , ..., एक्स मीटर > और वाई = <y 1 , वाई 2 , वाई 3 , ..., वाई एन > क्रम हो। एक तत्व की लंबाई की गणना करने के लिए निम्नलिखित एल्गोरिथ्म का उपयोग किया जाता है।
इस प्रक्रिया में, तालिका C[m, n] पंक्ति प्रमुख क्रम और एक अन्य तालिका में गणना की जाती है B[m,n] इष्टतम समाधान के निर्माण के लिए गणना की जाती है।
Algorithm: LCS-Length-Table-Formulation (X, Y)
m := length(X)
n := length(Y)
for i = 1 to m do
C[i, 0] := 0
for j = 1 to n do
C[0, j] := 0
for i = 1 to m do
for j = 1 to n do
if xi = yj
C[i, j] := C[i - 1, j - 1] + 1
B[i, j] := ‘D’
else
if C[i -1, j] ≥ C[i, j -1]
C[i, j] := C[i - 1, j] + 1
B[i, j] := ‘U’
else
C[i, j] := C[i, j - 1]
B[i, j] := ‘L’
return C and B
Algorithm: Print-LCS (B, X, i, j)
if i = 0 and j = 0
return
if B[i, j] = ‘D’
Print-LCS(B, X, i-1, j-1)
Print(xi)
else if B[i, j] = ‘U’
Print-LCS(B, X, i-1, j)
else
Print-LCS(B, X, i, j-1)
यह एल्गोरिथ्म सबसे लंबे समय तक चलने वाले सामान्य प्रिंट को प्रिंट करेगा X तथा Y।
विश्लेषण
तालिका, बाहरी को आबाद करने के लिए for पाश iterates m समय और भीतर for पाश iterates nबार। इसलिए, एल्गोरिथ्म की जटिलता ओ (एम, एन) है , जहांm तथा n दो तारों की लंबाई है।
उदाहरण
इस उदाहरण में, हमारे पास दो तार हैं X = BACDB तथा Y = BDCB सबसे लंबे समय तक सामान्य परिणाम खोजने के लिए।
एल्गोरिथ्म एलसीएस-लंबाई-तालिका-निर्माण (जैसा कि ऊपर कहा गया है) के बाद, हमने टेबल सी (बाएं हाथ की तरफ दिखाया गया है) और टेबल बी (दाहिने हाथ की तरफ दिखाया गया है) की गणना की है।
टेबल बी में, 'डी', 'एल' और 'यू' के बजाय, हम क्रमशः विकर्ण तीर, बाएं तीर और ऊपर तीर का उपयोग कर रहे हैं। तालिका बी बनाने के बाद, LCS फ़ंक्शन LCS-Print द्वारा निर्धारित किया जाता है। परिणाम बीसीबी है।