هل هذه الطريقة لأطول سلسلة فرعية مشتركة صحيحة؟

Question

لقد وجدت خوارزمية ل أطول سلسلة فرعية مشتركة.وعادة ما يتم ذلك باستخدام dynamic programming, باستخدام مصفوفة ثنائية الأبعاد من الحجم mxn أين m و n هي أطوال السلسلتين قيد النظر.

سأقوم ببناء المصفوفة التالية للسلسلتين.

M[i][j] = 1 if s1[i]==s2[j] else 0.

على سبيل المثال، إذا كانت السلاسل هي: abcxy و pqaabx

تبدو المصفوفة كما يلي:

    a b c x y
 p  0 0 0 0 0
 q  0 0 0 0 0
 a  1 0 0 0 0
 a  1 0 0 0 0
 b  0 1 0 0 0
 x  0 0 0 1 0

الآن، أبحث عن أقصى تسلسل مستمر لـ 1s في كل قطري يكون في الاتجاه من أعلى اليسار إلى أسفل اليمين.

الحد الأقصى للقيمة بين هذه سيكون الجواب.

يمكنني تنفيذ العملية المذكورة أعلاه دون استخدام المصفوفة بشكل صريح.التعقيد الزمني لا يزال O(M*N).لذلك، ليست هناك حاجة للذاكرة.

هل يمكن لأي شخص أن يشير لي إلى أين أخطئ؟

Answer 1

طريقتك صحيحة.للإثبات، افترض أن أطول سلسلة فرعية مشتركة لـ S1 وS2 كانت من S1[i..j] وS2[p..q].هذا يعني s1 [i+k] = s2 [p+k

كل هذه تقع على القطر بدءًا من (i,p).

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

تم التعديل

على تعليقك على حل ويكيبيديا باستخدام ذاكرة إضافية.انها هناك فقط من أجل الوضوح.من حيث المبدأ، تحتاج فقط إلى صفين من المصفوفة في حل ويكيبيديا وتحتفظ بالعدد الأقصى الحالي في متغير واحد.وهذا صحيح لأنه بالنسبة لأي إدخال (i,j) في المصفوفة

M(i,j) = 1 + M(i-1, j-1) (إذا كان s1[i] == s2[j])

كما ترون فإن عناصر الصف الحالي تعتمد فقط على عناصر الصف العلوي مباشرة.

Answer 2

الخوارزمية الخاصة بك صحيحة، ولكن نهج DP القياسي يلغي المرحلة الثانية، ويجعل الحل أكثر بساطة.

بدلاً من تحديد القيم المنطقية ثم مسح الأقطار للبحث عن أطول تسلسلات، يمكنك حساب الأطوال القطرية أثناء إنشاء المصفوفة - مطلوب تمريرة واحدة فقط.

من حيث تعقيد الزمان والمكان، كلا الحلين هما O(NxM).يمكن أن يوفر الحل الخاص بك بعض الذاكرة إذا كنت تستخدم تمثيل مصفوفة بت، في حين أن الحل الآخر ربما يكون أسرع قليلاً.