أقصر سلسلة فائقة مشتركة

في علم الحاسوب ، يُعرف أقصر تسلسل مشترك فائق بين تسلسلين X و Y بأنه أقصر تسلسل يحتوي على X و Y كمتتاليتين جزئيتين . هذه المسألة وثيقة الصلة بمسألة أطول تسلسل جزئي مشترك . إذا كان لدينا تسلسلان X = < x ₁ ,...,x _m > و Y = < y 1 _, ...,y _n >، فإن التسلسل U = < u ₁ ,...,u _k > يُعد تسلسلًا مشتركًا فائقًا بين X و Y إذا أمكن حذف عناصر منه للحصول على X و Y.

أقصر متتالية مشتركة فائقة (SCS) هي متتالية مشتركة فائقة ذات طول أدنى. في مسألة SCS، تُعطى متتاليتان X و Y ، والمطلوب هو إيجاد أقصر متتالية مشتركة فائقة ممكنة لهاتين المتتاليتين. عمومًا، لا تكون المتتالية المشتركة الفائقة فريدة.

بالنسبة لسلسلتين من المدخلات، يمكن تكوين سلسلة فرعية مشتركة قصيرة (SCS) بسهولة من أطول سلسلة فرعية مشتركة (LCS). على سبيل المثال، أطول سلسلة فرعية مشتركة لـ X${\displaystyle [1..m]=abcbdab}$و Y${\displaystyle [1..n]=bdcaba}$هل Z${\displaystyle [1..L]=bcba}$بإدخال الرموز غير المشتركة في المجموعة Z مع الحفاظ على ترتيبها الأصلي، نحصل على أقصر متتالية مشتركة U${\displaystyle [1..S]=abdcabdab}$وعلى وجه الخصوص، المعادلة${\displaystyle L+S=m+n}$ينطبق هذا على أي سلسلتين من المدخلات.

لا توجد علاقة مماثلة بين أقصر المتتاليات الفائقة المشتركة وأطول المتتاليات الفرعية المشتركة لثلاثة متتاليات إدخال أو أكثر. (على وجه الخصوص، لا تُعتبر LCS وSCS مشكلتين ثنائيتين ). ومع ذلك، يمكن حل كلتا المشكلتين في${\displaystyle O(n^{k})}$الوقت باستخدام البرمجة الديناميكية ، حيث${\displaystyle k}$يمثل عدد التسلسلات، و${\displaystyle n}$يمثل طولها الأقصى. أما في الحالة العامة لعدد عشوائي من متواليات الإدخال، فإن المسألة تُصنف ضمن المسائل الصعبة من نوع NP . ^{[ 1 ]}

تُعدّ مشكلة إيجاد سلسلة نصية ذات طول أدنى تُمثّل سلسلة فائقة لمجموعة محدودة من السلاسل النصية S = { s ₁ , s ₂ ,..., s _n }، ذات الصلة الوثيقة، من المسائل الصعبة من فئة NP. ^{[ 2 ]} علاوة على ذلك، فهي مسألة كاملة من فئة APX . ^{[ 3 ]} وقد اقتُرحت العديد من التقريبات ذات العامل الثابت على مرّ السنين، ويبلغ عامل التقريب لأفضل خوارزمية معروفة حاليًا 2.475. ^{[ 4 ]} مع ذلك، ربما يكون الحل الأبسط هو إعادة صياغة المشكلة كحالة من حالات تغطية المجموعات الموزونة، بحيث يكون وزن الحل الأمثل لتغطية المجموعات أقل من ضعف طول أقصر سلسلة فائقة S. عندئذٍ، يُمكن استخدام تقريب O(log( n )) لتغطية المجموعات الموزونة للحصول على تقريب O(log( n )) لأقصر سلسلة فائقة (مع ملاحظة أن هذا ليس تقريبًا ذا عامل ثابت).

لأي سلسلة نصية x في هذه الأبجدية، يُعرَّف P ( x ) على أنه مجموعة جميع السلاسل النصية التي تُعدّ سلاسل نصية جزئية من x . ويُصاغ المثال I لتغطية المجموعة على النحو التالي:

• ليكن M فارغًا.
• لكل زوج من السلاسل s _i و s _j ، إذا كانت الرموز k الأخيرة من s _i هي نفسها الرموز k الأولى من s _j ، فأضف سلسلة إلى M تتكون من التسلسل مع أقصى تداخل لـ s _i مع s _j .
• عرّف الكون${\displaystyle {\mathcal {U}}}$من مجموعة غطاء المثال لتكون S
• عرّف مجموعة المجموعات الجزئية من الكون على أنها { P ( x ) | x ∈ S ∪ M }
• حدد تكلفة كل مجموعة جزئية P (x) لتكون | x |، طول x .

يمكن بعد ذلك حل الحالة I باستخدام خوارزمية لتغطية المجموعات الموزونة، ويمكن للخوارزمية أن تُخرج سلسلة عشوائية من السلاسل x التي تُخرج خوارزمية تغطية المجموعات الموزونة لها P ( x ). ^{[ 5 ]}

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

• غاري، مايكل ر.؛ جونسون ، ديفيد س. (1979). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . دبليو إتش فريمان. ص 228 A4.2: SR8 . ISBN 0-7167-1045-5. Zbl 0411.68039 . 
• شبانكوفسكي، فويتش (2001). تحليل الحالة المتوسطة للخوارزميات على المتتاليات . سلسلة وايلي-إنترساينس في الرياضيات المتقطعة والتحسين. مع مقدمة بقلم فيليب فلاجو. تشيتشستر: وايلي. ISBN 0-471-24063-X. Zbl 0968.68205 . 
• فازيراني ، فيجاي ف. (2001)، خوارزميات التقريب ، سبرينغر-فيرلاغ، ISBN 3-540-65367-8

• قاموس الخوارزميات وهياكل البيانات: أقصر سلسلة فائقة مشتركة
• أقصر تسلسل مشترك فائق
• 1092. أقصر تسلسل مشترك فائق
• أقصر تسلسل مشترك فائق
• أقصر سلسلة فائقة مشتركة
• أقصر تسلسل مشترك فائق (SCS)