أخبار عاجلة

أطول متتالية جزئية متزايدة مثال

مثال

في متتالية ع¤ان دير كورپت الثنائية

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, …

إحدى المتتاليات الجزئية الأطول المتزايدة هي

0, 2, 6, 9, 13, 15.

طول هذه المتتالية الجزئية هو 6 أي أن المتتالية الأصلية لا تحوي متتالية جزئية من 7 عناصر يمكنها تشكيل متتالية جزئية متزايدة.كما أن المتتالية الجزئية المتزايدة الأطول ليست وحيدة فمثلاً لدينا

0, 4, 6, 9, 11, 15 أو 0, 4, 6, 9, 13, 15

هما متتاليتان جزئيتان متزايدتان من نفس طول المتتالية الجزئية المتزايدة الأطول .

علاقتها بمسائل خوارزمية أخرى

مسألة إيجاد المتتالية الجزئية المتزايدة الأطول لها تعلق وطيد بمسألة إيجاد أطول متتالية جزئية مشتركة , والتي تحتاج زمناً من الدرجة الثالثة لحلها باستخدام برمجة ديناميكية البرمجة الديناميكية إن اطول متتالية جزئية متزايدة في متتالية ما S هي أطول متتالية جزئية مشتركة بين المتتاليتين S و T, حيث T هي نتيجة ترتيب المتتالية S.

من أجل الحالة الخاصة التي يكون فيها الدخل عبارة عن تبديل للأعداد الصحيحة 1, 2, ..., n, يمكن لهذا الحل أن يكون فعالاً , ليعطينا حلاً بحدود( O(n log log n. Citation author Hunt, J. Szymanski, T. A fast algorithm for computing longest common subsequences journal Communications of the ACM year 1977 pages 350–353 doi 10.1145/359581.359603 issue 5 volume 20 postscript .

خوارزمية فعالة للحل

الخوارزمية التالية تحلّ مسألة إيجاد أطول متتالية جزئية متزايدة باستخدام المصفوفات و بحث ثنائي البحث الثنائي .
فهي تقوم بمعالجة عناصر المتتالية تباعاً, وتقوم بحفظ أطول متتالية جزئية تم العثور عليها حتى الآن. إذا رمزنا إلى عناصر المتتالية بـ [X[1], X[0, الخ. فبعد معالجة العنصر [X[i, تكون الخوارزمية قد حفظت قيماً في مصفوفتين

[M[j — تحفظ قيمة الفهرس k لأصغر عنصر [X[k حيث توجد متتالية جزئية متزايدة طولها j وتنتهي بالعنصر [X[kفي المجال k ≤ i (لاحظ أن لدينا هنا j ≤ k ≤ i , لأن j يمثل طول المتتالية الجزئية المتزايدة , وk يمثل رقم فهرس انتهاء المتتالية الجزئية.فمن الواضح أنه لا يمكننا الحصول على متتالية جزئية متزايدة طولها 13 عندما نكون لانزال عند العناصر رقم 11 , . k ≤ i بالتعريف).
[P[k — تحفظ رقم الفهرس للعنصر الذي يسبق [X[k في أطول متتالية جزئية متزايدة تنتهي عند [X[k.

إضافة لما سبق فإن الخوارزمية تحفظ عدداً L يمثل طول أطول متتالية جزئية متزايدة تم العثور عليها حتى الآن.

في الخوارزمية أدناه سنزيح المصفوفة M بالعنصر [M[0 الذي لن يستخدم للتسهيل (فالمصفوفة تستخدم الترقيم بدءاً من الصفر ).

لاحظ أن المتتالية X[M[1 , X[M[2 , ..., X[M[L تكون غير متناقصة عند أي نقطة من الخوارزمية ,لذلك إذا كان هناك متتالية جزئية طولها i تنتهي عند X[M[i

فهناك أيضاً متتالية جزئية طولها i-1 تنتهي عند قيمة أصغر وهي القيمة [X[P[M[i. لذلك نقوم بعمل بحث ثنائي في المتتالية في زمن لوغاريتمي .

سنكتب الخوارزمية بالعربية لتقريبها إلى الفهم أكثر بحيث توضح المسميات وظيفة كل متحول ومصفوفة وذلك كما يلي

  • سنرمز بالكلمة أمجد لــأطول متتالية جزئية متزايدة .
  • [M[j تكافئها رقم_أصغر_نهاية_لأمجد_بطول_ما[ج]
  • [P[k تكافئها رقم_السابق_في_أمجد_لعنصر_ما[ك]
  • [X[k تكافئها الدخل[ك]
  • عدد العناصر N يقابله الحجم
  • طول أمجد تم العثور عليها L يقابله الطول

نص الخوارزمية بطريقة شبه الكود كما يلي

رقم_السابق_في_أمجد_لعنصر_ما مصفوفة طولها الحجم

رقم_أصغر_نهاية_لأمجد_بطول_ما مصفوفة طولها الحجم+1

الطول 0

من أجل المتحول س ضمن المجال من 0 إلى الحجم-1

\ بحث ثنائي للعثور على أكبر قيمة تحقق العلاقتين ج ≤ الطول

\ و الدخل[ رقم_أصغر_نهاية_لأمجد_بطول_ما[ج] ]

في علم الحاسوب ,تعالج مسألةُ إيجاد أطول متتالية جزئية متزايدة البحث عن متتالية جزئية من متتالية معطاة بحيث تكون عناصر هذه المتتالية الجزئية مرتبة ,تصاعديّاً أو تنازليّاً , وبحيث تكون أطول ما يمكن .وهذه المتتالية الجزئية ليست بالضرورة ناتجة عن عناصر متجاورة كما أنها يمكن ألا تكون وحيدة ضمن المتتالية الأصلية .

تمت دراسة مسألة إيجاد أطول متتالية جزئية متزايدة في سياق دراسة عدة فروع متعلقة بال رياضيات , متضمنة ال خوارزميات , تجمع مصفوفة غاوسية , نظرية تمثيل الزمر , وال فيزياء . citation
last1 Aldous first1 David author1-link David Aldous
last2 Diaconis first2 Persi author2-link Persi Diaconis
doi 10.1090/S0273-0979-99-00796-X
journal Bulletin of the American Math atical Society

pages 413–432
issue 04
Longest increasing subsequences from patience sorting to the Baik–Deift–Johansson theor

volume 36
year 1999 . يمكن حل مسألة إيجاد أطول متتالية جزئية متزايدة في زمن( O(n log n, حيث n هو طول متتالية الدخل .

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني.