algorithm
सबसे लंबा सामान्य परिणाम

सबसे लंबे समय तक सामान्य परिणाम स्पष्टीकरण

डायनामिक प्रोग्रामिंग के सबसे महत्वपूर्ण कार्यान्वयनों में से एक सबसे लंबे समय तक सामान्य परिणाम का पता लगाना है। आइए पहले कुछ बुनियादी शब्दावली को परिभाषित करें।

subsequence:

एक क्रम एक ऐसा अनुक्रम है जो शेष तत्वों के क्रम को बदले बिना कुछ तत्वों को हटाकर दूसरे अनुक्रम से प्राप्त किया जा सकता है। मान लीजिए कि हमारे पास एक स्ट्रिंग एबीसी है । यदि हम इस स्ट्रिंग से शून्य या एक या एक से अधिक वर्ण मिटाते हैं, तो हमें इस स्ट्रिंग की अनुवर्तीता मिलती है। तो स्ट्रिंग एबीसी के परिणाम { "ए" , "बी" , "सी" , "एबी" , "एसी" , "बीसी" , "एबीसी" , "" } होंगे। यहां तक कि अगर हम सभी पात्रों को हटा देते हैं, तो खाली स्ट्रिंग भी एक बाद होगी। एक वर्ण में प्रत्येक वर्ण के लिए, बाद में पता लगाने के लिए, हमारे पास दो विकल्प हैं - या तो हम चरित्र लेते हैं, या हम नहीं करते हैं। इसलिए यदि स्ट्रिंग की लंबाई n है , तो उस स्ट्रिंग के 2 ⁿ अनुवर्ती हैं।

सबसे लंबा सामान्य परिणाम:

जैसा कि नाम से पता चलता है, सभी सामान्य अनुवर्ती दो स्ट्रिंग्स में से, सबसे लंबा सामान्य लेन्स (LCS) अधिकतम लंबाई वाला होता है। उदाहरण के लिए: "HELLOM" और "HMLD" के बीच की सामान्य अनुवर्ती "H" , "HL" , "HM" आदि हैं। यहाँ "HLL" सबसे लंबी सामान्य अनुवर्ती है जिसकी लंबाई 3 है।

जानवर बल विधि:

हम backtracking का उपयोग करके दो तारों के सभी बाद उत्पन्न कर सकते हैं । फिर हम उनकी तुलना आम नतीजों के बारे में जानने के लिए कर सकते हैं। बाद में हमें अधिकतम लंबाई वाले व्यक्ति का पता लगाना होगा। हम पहले ही देख चुके हैं कि, एक स्ट्रिंग की लंबाई n के 2 ^एन बाद हैं। यदि हमारी n 20-25 पार हो जाए तो समस्या को हल करने में कई साल लग जाएंगे।

गतिशील प्रोग्रामिंग विधि:

आइए एक उदाहरण के साथ हमारी पद्धति पर जाएं। मान लें कि, हमारे पास दो तार हैं abcdaf और acbcf । आइए इन्हें s1 और s2 के साथ निरूपित करें। तो इन दो तारों की सबसे लंबी सामान्य जटिलता "एबीसीएफ" होगी , जिसकी लंबाई 4 है। फिर से मैं आपको याद दिलाता हूं, बाद में स्ट्रिंग में निरंतरता की आवश्यकता नहीं होनी चाहिए। "Abcf" का निर्माण करने के लिए, हम एस 1 और "सी" s2 में में "दा" नजरअंदाज कर दिया। डायनामिक प्रोग्रामिंग का उपयोग करके हमें यह कैसे पता चलेगा?

हम एक तालिका (2 डी सरणी) के साथ शुरू करेंगे, जिसमें पंक्ति में s1 के सभी वर्ण और स्तंभ में s2 के सभी वर्ण होंगे। यहाँ तालिका 0-अनुक्रमित है और हम पात्रों को 1 से आगे की तरफ रखते हैं। हम प्रत्येक पंक्ति के लिए तालिका को बाएं से दाएं की ओर ले जाएंगे। हमारी तालिका इस तरह दिखाई देगी:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

यदि हम उस पंक्ति और स्तंभ के पात्रों को लेते हैं और उसके पहले उपसर्ग को जोड़ते हैं, तो प्रत्येक पंक्ति और स्तंभ दो तारों के बीच सबसे लंबे समय तक सामान्य लंबाई की लंबाई का प्रतिनिधित्व करते हैं। उदाहरण के लिए: तालिका [2] [3] "एसी" और "एबीसी" के बीच सबसे लंबे समय तक सामान्य परिणाम की लंबाई का प्रतिनिधित्व करता है।

0-वें कॉलम s1 के खाली परिणाम का प्रतिनिधित्व करता है। इसी प्रकार 0-वें पंक्ति s2 के खाली परिणाम का प्रतिनिधित्व करती है। यदि हम एक स्ट्रिंग की खाली जगह लेते हैं और इसे किसी अन्य स्ट्रिंग के साथ मिलाने की कोशिश करते हैं, तो कोई फर्क नहीं पड़ता कि दूसरे सबस्ट्रिंग की लंबाई कितनी है, सामान्य बाद में 0 लंबाई होगी। तो हम 0-पंक्तियों और 0-वें स्तंभों को 0 के साथ भर सकते हैं। हमें मिला:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

चलो शुरू करें। जब हम भरने टेबल [1] [1], हम अपने आप को कह रहे हैं कि अगर हम एक स्ट्रिंग एक था और एक और स्ट्रिंग एक और कुछ नहीं, क्या यहां सबसे लंबे समय तक आम subsequence हो जाएगा? यहाँ LCS की लंबाई 1. होगी। अब आइए सारणी [1] [2] को देखें । हम स्ट्रिंग एबी और स्ट्रिंग ए है । LCS की लंबाई 1. हो जाएगा आप देख सकते हैं, शेष मान पहली पंक्ति के लिए भी 1 हो जाएगा के रूप में यह ABCD, abcda, abcdaf के साथ ही स्ट्रिंग एक मानता है। तो हमारी तालिका इस तरह दिखाई देगी:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

पंक्ति 2 के लिए, जिसमें अब c शामिल होगा। टेबल के लिए [2] [1] हम दूसरी तरफ एक तरफ एसी और एक की है। तो LCS की लंबाई 1. है। हमें यह 1 कहां से मिला? शीर्ष है, जो दो सबस्ट्रिंग के बीच LCS एक अर्थ है से। तो हम जो कह रहे हैं, अगर s1 [2] और s2 [1] समान नहीं हैं, तो LCS की लंबाई शीर्ष पर , या बाईं ओर LCS की लंबाई की अधिकतम सीमा होगी। शीर्ष पर LCS की लंबाई लेना यह दर्शाता है कि, हम वर्तमान वर्ण को s2 से नहीं लेते हैं। इसी तरह, बाईं ओर LCS की लंबाई को देखते हुए, हम LCS बनाने के लिए s1 से वर्तमान वर्ण को नहीं लेते हैं। हमें मिला:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |  1  |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

तो हमारा पहला सूत्र होगा:

if s2[i] is not equal to s1[j]
    Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif

टेबल [2] [2] के लिए आगे बढ़ते हुए, हमारे पास स्ट्रिंग एबी और एसी है । चूँकि c और b एक समान नहीं हैं, इसलिए हम सबसे ऊपर या यहाँ छोड़ दिया जाता है। इस मामले में, यह फिर से है। इसके बाद, तालिका [2] [3] के लिए हमारे पास स्ट्रिंग एबीसी और एसी है । इस बार पंक्ति और स्तंभ दोनों के वर्तमान मूल्य समान हैं। अब LCS की लंबाई LCS की अधिकतम लंबाई के बराबर होगी। अब तक हम LCS की अधिकतम लंबाई कैसे प्राप्त कर सकते हैं? हम विकर्ण मूल्य की जांच करते हैं, जो एब और ए के बीच सबसे अच्छे मैच का प्रतिनिधित्व करता है । इस स्थिति से, वर्तमान मानों के लिए, हमने s1 और s2 में एक और चरित्र जोड़ा, जो एक ही हुआ। तो LCS की लंबाई निश्चित रूप से बढ़ेगी। हम 1 + 1 = 2 को तालिका [2] [3] में डालेंगे । हमें मिला,

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |  1  |  1  |  2  |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

तो हमारा दूसरा सूत्र होगा:

if s2[i] equals to s1[j]
    Table[i][j] = Table[i-1][j-1] + 1
endif

हमने दोनों मामलों को परिभाषित किया है। इन दो सूत्रों का उपयोग करके, हम पूरी तालिका को आबाद कर सकते हैं। तालिका भरने के बाद, यह इस तरह दिखेगा:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |  1  |  1  |  2  |  2  |  2  |  2  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |  1  |  2  |  2  |  2  |  2  |  2  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |  1  |  2  |  3  |  3  |  3  |  3  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |  1  |  2  |  3  |  3  |  3  |  4  |
     +-----+-----+-----+-----+-----+-----+-----+-----+

S1 और s2 के बीच LCS की लंबाई तालिका [5] [6] = 4 होगी । यहां, 5 और 6 क्रमशः s2 और s1 की लंबाई हैं। हमारा छद्म कोड होगा:

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

इस एल्गोरिथ्म का समय जटिलता है: ओ (एमएन) जहां एम और एन प्रत्येक तार की लंबाई को दर्शाता है।

हम सबसे लंबे समय तक सामान्य परिणाम कैसे पता लगा सकते हैं? हम नीचे-दाएं कोने से शुरू करेंगे। हम जांच करेंगे कि मूल्य कहां से आ रहा है। यदि मूल्य विकर्ण से आ रहा है, तो यह है कि तालिका [i-1] [j-1] तालिका [i] [j] - 1 के बराबर है, हम या तो s2 [i] या s1 [j] (दोनों को धक्का देते हैं ) समान हैं) और तिरछे चलते हैं। यदि मान ऊपर से आ रहा है, तो इसका मतलब है, यदि तालिका [i-1] [j] तालिका [i] [j] के बराबर है, तो हम शीर्ष पर जाते हैं। यदि मान बाईं ओर से आ रहा है, तो इसका मतलब है, यदि तालिका [i] [j-1] तालिका [i] [j] के बराबर है, तो हम बाईं ओर चलते हैं। जब हम सबसे बाएँ या सबसे ऊपरी स्तंभ पर पहुँचते हैं, तो हमारी खोज समाप्त हो जाती है। फिर हम स्टैक से मानों को पॉप करते हैं और उन्हें प्रिंट करते हैं। छद्म कोड:

Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
     if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
        S.push(s1[j])   //or S.push(s2[i])
        i := i - 1
        j := j - 1
    else if Table[i-1][j] == Table[i][j]
        i := i-1
    else
        j := j-1
    endif
endwhile
while S is not empty
    print(S.pop)
endwhile

ध्यान देने वाली बात: अगर टेबल [i-1] [j] और टेबल [i] [j-१] दोनों टेबल के बराबर है [i] [j] और टेबल [i-१] [j-१] नहीं है तालिका [i] [j] - 1 के बराबर, उस क्षण के लिए दो LCS हो सकते हैं। यह छद्म कोड इस स्थिति पर विचार नहीं करता है। आपको कई LCS खोजने के लिए इसे पुनरावर्ती रूप से हल करना होगा।

इस एल्गोरिथ्म का समय जटिलता है: O (अधिकतम (m, n)) ।