أطول سلسلة متزايدة (Longest Increasing Subsequence)

<![CDATA[

مقدمة

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

تعريف المشكلة

بشكل رسمي، إذا كانت لدينا سلسلة من الأرقام (أو أي نوع بيانات قابل للمقارنة):

S = (a₁, a₂, …, a_n)

فإن السلسلة الفرعية المتزايدة هي:

S’ = (a_i1, a_i2, …, a_ik)

حيث:

i₁ < i₂ < … < i_k

و:

a_i1 < a_i2 < … < a_ik

هدفنا هو إيجاد أطول سلسلة فرعية متزايدة ممكنة.

أمثلة توضيحية

لنفترض أن لدينا السلسلة التالية:

S = (3, 10, 2, 1, 20)

أطول سلسلة فرعية متزايدة هنا هي:

(3, 10, 20)

أو

(2, 20)

ولكن هذه السلسلة ليست الأطول, فالأطول هي:

(3, 10, 20) و طولها 3

مثال آخر:

S = (3, 4, -1, 0, 6, 2, 3)

أطول سلسلة فرعية متزايدة هنا هي:

(-1, 0, 2, 3)

أو

(3, 4, 6)

وكلاهما لهما نفس الطول وهو 4.

خوارزميات الحل

هناك عدة طرق لحل مشكلة إيجاد أطول سلسلة متزايدة، تختلف في تعقيدها وكفاءتها. بعض الخوارزميات الشائعة تتضمن:

• البرمجة الديناميكية (Dynamic Programming)
• خوارزمية تعتمد على البحث الثنائي (Binary Search)
• خوارزمية الحل الساذج (Naive Recursive Solution)

البرمجة الديناميكية

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

الفكرة:

ننشئ مصفوفة dp، حيث dp[i] يمثل طول أطول سلسلة فرعية متزايدة تنتهي بالعنصر a_i.

الخطوات:

1. نهيئ dp[i] = 1 لكل i (لأن كل عنصر يمكن أن يكون سلسلة فرعية متزايدة بطول 1).
2. نتحرك في السلسلة الأصلية من البداية إلى النهاية.
3. لكل عنصر a_i، نتحقق من جميع العناصر التي تسبقه a_j (حيث j < i).
4. إذا كان a_i > a_j، فهذا يعني أنه يمكننا إضافة a_i إلى السلسلة الفرعية المتزايدة التي تنتهي بـ a_j.
5. نقوم بتحديث dp[i] = max(dp[i], dp[j] + 1).
6. أخيرًا، أطول سلسلة فرعية متزايدة هي max(dp[i]) لجميع i.

مثال:

لنفترض أن لدينا السلسلة S = (10, 22, 9, 33, 21, 50, 41, 60)

ستكون مصفوفة dp كالتالي:

• dp[0] = 1 (لأن العنصر 10 يمكن أن يكون سلسلة فرعية متزايدة بطول 1)
• dp[1] = 2 (لأن العنصر 22 يمكن أن يضاف إلى العنصر 10 ليصبح السلسلة (10, 22))
• dp[2] = 1 (لأن العنصر 9 لا يمكن أن يضاف إلى العنصر 10 أو 22، فهو أصغر منهما)
• dp[3] = 3 (لأن العنصر 33 يمكن أن يضاف إلى العنصر 10 أو 22 أو 9، ولكن الأفضل هو إضافته إلى (10, 22) ليصبح (10, 22, 33))
• dp[4] = 2 (لأن العنصر 21 يمكن أن يضاف إلى العنصر 10 أو 9، ولكن الأفضل هو إضافته إلى 10 ليصبح (10, 21))
• dp[5] = 4 (لأن العنصر 50 يمكن أن يضاف إلى العناصر 10, 22, 9, 33, 21، ولكن الأفضل هو إضافته إلى (10, 22, 33) ليصبح (10, 22, 33, 50))
• dp[6] = 4 (لأن العنصر 41 يمكن أن يضاف إلى العناصر 10, 22, 9, 33, 21، ولكن الأفضل هو إضافته إلى (10, 22, 33) ليصبح (10, 22, 33, 41))
• dp[7] = 5 (لأن العنصر 60 يمكن أن يضاف إلى العناصر 10, 22, 9, 33, 21, 50, 41، ولكن الأفضل هو إضافته إلى (10, 22, 33, 50) ليصبح (10, 22, 33, 50, 60))

إذًا، أطول سلسلة فرعية متزايدة هي 5.

التعقيد الزمني: O(n²)

التعقيد المكاني: O(n)

خوارزمية تعتمد على البحث الثنائي

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

الفكرة:

نحتفظ بمصفوفة tail، حيث tail[i] يمثل أصغر عنصر يمكن أن يكون نهاية لسلسلة فرعية متزايدة بطول i+1.

الخطوات:

1. نهيئ مصفوفة tail فارغة.
2. نتحرك في السلسلة الأصلية من البداية إلى النهاية.
3. لكل عنصر a_i، نستخدم البحث الثنائي للعثور على أصغر عنصر في tail أكبر من أو يساوي a_i.
4. إذا لم يتم العثور على عنصر أكبر من أو يساوي a_i، فهذا يعني أن a_i يمكن أن يمدد أطول سلسلة فرعية متزايدة حالية، لذلك نضيف a_i إلى نهاية tail.
5. إذا تم العثور على عنصر أكبر من أو يساوي a_i في الفهرس j، فهذا يعني أنه يمكننا استبدال tail[j] بـ a_i، لأن a_i أصغر من tail[j] ويمكن أن يؤدي إلى سلسلة فرعية متزايدة أفضل في المستقبل.
6. أخيرًا، طول أطول سلسلة فرعية متزايدة هو طول مصفوفة tail.

مثال:

لنفترض أن لدينا السلسلة S = (10, 22, 9, 33, 21, 50, 41, 60)

ستكون مصفوفة tail كالتالي:

• 10 (بعد معالجة العنصر 10)
• 10, 22 (بعد معالجة العنصر 22)
• 9, 22 (بعد معالجة العنصر 9، استبدلنا 10 بـ 9)
• 9, 22, 33 (بعد معالجة العنصر 33)
• 9, 21, 33 (بعد معالجة العنصر 21، استبدلنا 22 بـ 21)
• 9, 21, 33, 50 (بعد معالجة العنصر 50)
• 9, 21, 33, 41 (بعد معالجة العنصر 41، استبدلنا 50 بـ 41)
• 9, 21, 33, 41, 60 (بعد معالجة العنصر 60)

إذًا، أطول سلسلة فرعية متزايدة هي 5.

التعقيد الزمني: O(n log n)

التعقيد المكاني: O(n)

خوارزمية الحل الساذج

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

الفكرة:

نقوم بتوليد جميع السلاسل الفرعية الممكنة، ثم نتحقق من أن كل سلسلة فرعية متزايدة، ثم نختار أطول سلسلة فرعية متزايدة.

التعقيد الزمني: O(2ⁿ)

التعقيد المكاني: O(n)

تطبيقات

تستخدم مشكلة إيجاد أطول سلسلة متزايدة في العديد من التطبيقات المختلفة، بما في ذلك:

• تحليل البيانات المالية: يمكن استخدامها لتحديد الاتجاهات في أسعار الأسهم.
• علم الأحياء الحسابي: يمكن استخدامها لمقارنة تسلسل الحمض النووي.
• ضغط البيانات: يمكن استخدامها لتقليل حجم البيانات.
• الذكاء الاصطناعي: يمكن استخدامها في تعلم الآلة.
مقارنة الملفات: في أدوات مقارنة الملفات، تُستخدم لتحديد أطول سلسلة من الأسطر المتطابقة بين ملفين، مما يساعد في تحديد التغييرات التي تم إجراؤها.

اعتبارات الأداء

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

تحسينات إضافية:

• استخدام هياكل بيانات متقدمة: يمكن استخدام هياكل بيانات مثل أشجار الفينويك (Fenwick Trees) أو أشجار القطاعات (Segment Trees) لتحسين أداء البحث الثنائي.
• التحسينات الخاصة بالتطبيق: يمكن إجراء تحسينات خاصة بالتطبيق بناءً على خصائص البيانات.

خاتمة

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

المراجع

• Longest Increasing Subsequence – Wikipedia
• Longest Increasing Subsequence (LIS) – GeeksforGeeks
• Longest Increasing Subsequence – JavaTpoint
• Longest Increasing Subsequence – Tutorialspoint

]]>