أطول لاحقة مشتركة: Python, C++ مثال

ما هو أطول لاحقة مشتركة؟

تعني مسألة إيجاد أطول سلسلة فرعية مشتركة (LCS) أنه سيتم إعطاؤك سلسلتين نصيتين أو نمطين أو تسلسلين من العناصر. من بين هذين التسلسلين أو السلسلتين، عليك إيجاد أطول سلسلة فرعية من العناصر بنفس الترتيب الموجودة في كلتا السلسلتين أو النمطين.

مثال

على سبيل المثال، لدينا سلسلتان نصيتان. لنفترض أن:

Pattern_1 = "RGBGARGA"
Pattern_2 = "BGRARG"

• انطلاقاً من النمط 1، يمكن إنتاج تسلسلات مثل "RGB" و"RGGA" و"RGAR". لإنشاء تسلسل، يجب الحفاظ على الموضع النسبي لكل حرف في السلسلة.
• انطلاقاً من النمط الثاني، يمكننا إنتاج متواليات مثل "BGR" و"BRAG" و"RARG". ويمكن إنتاج المتواليات طالما حافظت على الموضع النسبي للسلسلة الأصلية.

مصطلح الوضع النسبي يعني النظام.

على سبيل المثال، يُعد التسلسل "BRG" تسلسلاً صحيحاً لأن الحرف "B" ظهر أولاً، ثم "R"، ثم "G" في النمط الأصلي pattern_2. أما إذا كان التسلسل "RBRG"، فهو غير صحيح، لأن الحرف "B" ظهر أولاً في النمط الأصلي (pattern_2).

لدينا خياران للعثور على أطول تسلسل مشترك من التسلسلين أو المصفوفتين المحددتين.

• طريقة ساذجة
• حل البرمجة الديناميكية: يُعرف أيضًا أطول تسلسل مشترك باسم LCS.

الحل البسيط يتطلب وقتاً أطول ولا يُعدّ الحل الأمثل. باستخدام حل البرمجة الديناميكية، نتغلب على مشكلة التعقيد.

طريقة ساذجة

تُعدّ الطريقة البسيطة أسلوبًا سهلًا لحلّ المشكلة، بغض النظر عن تعقيد الوقت وعوامل التحسين الأخرى. وهي تعتمد في أغلب الأحيان على "التجربة والخطأ"، وحلقات تكرارية متعددة، واستدعاءات متكررة. ويُقصد بمصطلح "التجربة والخطأ" استعراض جميع الأنماط الممكنة لمشكلة معينة.

مثال

من المثال أعلاه للنمط 1 والنمط 2، لنفترض أن النمط 1 يبلغ طوله m والنمط 2 يبلغ طوله n. للتحقق من كل حالة محتملة، نحتاج إلى تقييم كل تسلسل لاحق محتمل للنمط 1 مع النمط 2.

إليك سلسلة بسيطة من أربعة أحرف "ABCD". على سبيل المثال، نحتاج إلى إنشاء تسلسل من "ABCD". يمكننا إما أخذ حرف أو عدم أخذه. هذا يعني أنه لكل حرف لدينا خياران:

• سيتم إضافة الحرف إلى اللاحقة.
• لن يتم إضافة الحرف إلى اللاحقة.

هنا تظهر الصور جميع التسلسلات التي يمكننا صنعها من السلسلة "ABCD".

تسلسل بحرف واحد:

تسلسلات مكونة من حرفين:

تسلسلات مكونة من حرفين:

من الرسم البياني أعلاه، نجد 14 متتالية. إذا لم نأخذ أي حروف، أي سلسلة فارغة، يصبح إجمالي المتتاليات 15. علاوة على ذلك، فإن السلسلة "ABCD" نفسها تُعدّ متتالية. لذا، يصبح إجمالي المتتاليات 16.

لذا، من الممكن توليد 2^4 أو 16 متتالية فرعية من "ABCD". ثم، سلسلة بطول m سيكون لها تسلسل فرعي إجمالي قدره 2^m.

لكل تسلسل فرعي، نحتاج إلى التحقق منه للنمط الثاني بأكمله. سيستغرق ذلك وقتًا مقداره O(n). يشير O(n) إلى دالة التعقيد التي تحسب الوقت المستغرق للتنفيذ.

لذا، يصبح التعقيد الزمني الإجمالي O(n*2^m). بالنسبة للمثال الذي رأيناه أعلاه، فإن قيمة m = 8 و n = 5.

فيما يلي خطوات الطريقة الساذجة:

الخطوة 1) خذ تسلسلاً من النمط 1.
الخطوة 2) قم بمطابقة التسلسل من الخطوة 1 مع النمط 2.
الخطوة 3) إذا كان مطابقًا، فقم بحفظ التسلسل اللاحق.
الخطوة 4) إذا بقيت المزيد من التسلسلات في النمط 1، فانتقل إلى الخطوة 1 مرة أخرى.
الخطوة 5) طباعة أطول تسلسل.

البنية التحتية المثلى

يشير مصطلح البنية الفرعية المثلى إلى إمكانية إيجاد الحل الأمثل من خلال حل المسائل الفرعية. على سبيل المثال، في المثال أعلاه، لدينا النمط 1 والنمط 2.

الخطوة 1) اختر أول حرفين من كل نمط.

الخطوة 2) خذ الأحرف الثالثة إلى الخامسة من كل نمط.

الخطوة 3) تواصل بالمثل مع الشخصيات المتبقية.

البنية العودية لمشكلة LCS

نحدد أطول سلسلة مشتركة في السلسلة الفرعية (سلسلة مُولّدة من السلسلة الأصلية). ثم نسجل طول أطول سلسلة مشتركة في السلاسل الفرعية.

الآن، هنا خاصية أخرى مثيرة للاهتمام وهي تداخلping المشاكل الفرعيةيقال إن المشكلة تتضمن تداخلاًping المشاكل الفرعية إذا كان من الممكن تقسيم بيان المشكلة إلى مشاكل فرعية صغيرة واستخدامها عدة مرات في البرنامج.

يوضح الرسم البياني أدناه أن الخوارزمية العودية تستدعي الوظيفة بنفس المعلمة عدة مرات.

على سبيل المثال، انظر إلى شجرة الاستدعاء الذاتي. في المربع ذي اللون الداكن، يمكنك ملاحظة التداخلping المشاكل الفرعية. يتم استدعاء ("RG"، "RA")، ("RG"، "R")، وغيرها عدة مرات.

ولتحسين ذلك، لدينا نهج البرمجة الديناميكية (موانئ دبي).

طريقة التكرار لأطول سلسلة فرعية مشتركة

الرسم البياني الموضح أعلاه يمثل الطريقة التكرارية. لكل دالة تكرارية حالة توقف لإنهاء التكرار أو لبدء العودة من مكدسها.

في هذا التطبيق، سنستخدم حالة أساسية. لذا، فإن خوارزمية هو مثل التالي:

• إذا كانت جميع العناصر قبل العنصر الأخير متطابقة، فقم بزيادة الطول بمقدار واحد ثم أعد.
• مرر نمطين إلى الدالة، ثم خذ القيمة القصوى للقيمة المرجعة.
• إذا كان طول أحد الأنماط صفرًا، فلن يكون لدينا أي نتيجة لاحقة للمقارنة. العودة 0 في هذه الحالة. هذه هي الحالة الأساسية للتكرار.

كنية Code:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
    if len_1 or len_2 is zero:
        return 0
    if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]:
        return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
    else:
        return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2),
                   lcs(pattern_1, pattern_2, len_1, len_2 - 1))

التنفيذ في C++

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int lcs(string pattern_1, string pattern_2, int len_1, int len_2) {
  if (len_1 == 0 || len_2 == 0)
    return 0;
  if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) {
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1);
  } else {
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1));
  }
}
int main() {
  string pattern_1, pattern_2;
  pattern_1 = "RGBGARGA";
  pattern_2 = "BGRARG";
  cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl;
}

الإخراج:

Length of LCS is: 5

التنفيذ في Python

def lcs(pattern_1, pattern_2, len_1, len_2):
    if len_1 == 0 or len_2 == 0:
        return 0
    if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]:
        return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
    else:
        return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2),
                   lcs(pattern_1, pattern_2, len_1, len_2 - 1))

pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

الإخراج:

Length of LCS is:  5

طريقة البرمجة الديناميكية لأطول سلسلة فرعية مشتركة (LCS)

البرمجة الديناميكية تعني تحسين الطريقة التكرارية البسيطة. على سبيل المثال، إذا نظرنا إلى الرسم البياني للطريقة التكرارية أو البسيطة، فسنجد عدة استدعاءات متطابقة للدوال. أما طريقة البرمجة الديناميكية فتسجل جميع العمليات الحسابية في مصفوفة وتعيد استخدامها عند الحاجة.

سنستخدم مصفوفة ثنائية الأبعاد بأبعاد m×n، حيث m و n هما طولا النمط 1 والنمط 2 على التوالي. مجموعة 2Dيمكننا استخدام هياكل بيانات القوائم في Python أو هياكل بيانات المتجهات/المصفوفات في C++.

كنية Code بالنسبة لـ LCS باستخدام البرمجة الديناميكية:

LCS(pattern_1, pattern_2):
    m = length of pattern_1 + 1
    n = length of pattern_2 + 1
    dp[n][m]
    for i in range 0 to n + 1:
        for j in range 0 to m + 1:
            if i or j equals to 0:
                dp[i][j] = 0
            else if pattern_1[i] == pattern_2[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

فيما يلي جدول LCS الذي يستخدم كبنية بيانات مصفوفة ثنائية الأبعاد لنهج البرمجة الديناميكية.

دعونا نناقش المنطق الذي استخدمناه هنا. الخطوات هي:

الخطوة 1) إذا كانت قيمة i أو j تساوي صفرًا، فإننا نأخذ سلسلة نصية فارغة من السلسلتين المعطيتين ونحاول إيجاد التسلسلات الفرعية المشتركة. ولكن، بما أن السلسلة الفرعية التي نأخذها فارغة، فإن طول التسلسل الفرعي يساوي صفرًا.

الخطوة 2) إذا تطابق حرفان، فسنقوم بتعيين القيمة للفهرس (i,j) عن طريق زيادة LCS المحسوب مسبقًا، والذي يوجد في الفهرس (i-1,j-1) (من الصف السابق).

الخطوة 3) إذا لم تتطابق القيم، فسنختار أكبر عنصر مشترك قصير (LCS) بين الفهرسين المتجاورين. وبهذه الطريقة، نحتاج إلى ملء جميع القيم في المصفوفة ثنائية الأبعاد.

الخطوة 4) وأخيرًا، سنعيد قيمة الخلية الأخيرة من المصفوفة ثنائية الأبعاد.

باختصار، تحتوي جميع القيم في المصفوفة ثنائية الأبعاد على طول التسلسلات الفرعية المشتركة. ومن بين هذه القيم، تحتوي الخلية الأخيرة على طول أطول تسلسل فرعي مشترك.

التنفيذ في C++

#include<iostream>
using namespace std;
int lcs(string pattern_1, string pattern_2) {
  int m = pattern_1.size();
  int n = pattern_2.size();
  // dp will store solutions as the iteration goes on
  int dp[n + 1][m + 1];
  for (int i = 0; i < n + 1; i++) {
    for (int j = 0; j < m + 1; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 0;
      } else if (pattern_2[i - 1] == pattern_1[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[n][m];
}
int main() {
  string pattern_1 = "RGBGARGA";
  string pattern_2 = "BGRARG";
  cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;
}

الإخراج:

Length of LCS: 5

التنفيذ في Python

def lcs(pattern_1, pattern_2):
    m = len(pattern_1)
    n = len(pattern_2)
    # dp will store solutions as the iteration goes on
    dp = [[None] * (n + 1) for item in range(m + 1)]
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif pattern_1[i - 1] == pattern_2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS: ", lcs(pattern_1, pattern_2))

الإخراج:

Length of LCS: 5

لذلك، كلا السلسلتين لهما أطول تسلسل مشترك بطول 5.

باختصار، نقوم ببساطة بحساب كل مهمة مرة واحدة في طريقة البرمجة الديناميكية. أما في الطريقة التكرارية، فقد يكون هناك تداخل.ping المشاكل الفرعية.

في خوارزمية البرمجة الديناميكية هذه، نستخدم مصفوفة ثنائية الأبعاد. سيكون هناك سلسلتين محددتين (بافتراض أن كلاهما بطول n). إذن المساحة المطلوبة في المصفوفة هي nx n. إذا كانت السلاسل كبيرة بما يكفي، فسنحتاج إلى إصدار محسّن للذاكرة من حل DP.

المنطق المبسط الذي تم أخذه في الكود هو:

• قم بتعريف صفيف ثنائي الأبعاد DP[m][n].
• املأ الصف الأول والعمود الأول من مصفوفة DP بـ 0.
• خذ i وj للتكرار.
• إذا كان النمط 1[i] يساوي النمط 2[j]، فقم بتحديث DP[i][j] = DP[i-1][j-1] + 1.
• إذا لم يكن النمط 1[i] يساوي النمط 2[j]، فإن DP[i][j] سيكون القيمة القصوى بين DP[i-1][j] و DP[i][j-1].
• استمر حتى يصل i وj إلى m وn.
• العنصر الأخير، DP[m-1][n-1]، سيحتوي على الطول.

هنا، تتم الإشارة إليه على أنه DP[m-1][n-1] لأن فهرس المصفوفة يبدأ من 0.

الأسئلة الشائعة