أطول تسلسل فرعي تصاعدي

تبحث مسألة أطول تسلسل فرعي تصاعدي Longest Incressing Subsequence ( وتعرف اختصارًا بـ LIS) عن طول أطول تسلسل فرعي في تسلسل معين بشرط أن تُرتب جميع العناصر في التسلسل الفرعي ترتيبًا تصاعديًا. فعلى سبيل المثال يكون طول أطول تسلسل فرعي تصاعدي للمصفوفة ‎{10, 22, 9, 33, 21, 50, 41, 60, 80}‎ هو 6 والتسلسل الفرعي التصاعدي هو ‎{10, 22, 33, 50, 60, 80}‎.

البنية الفرعية المثالية

لنفترض أنّ المصفوفة arr[0..n-1]‎ تمثّل مصفوفة المدخلات وأنّ الدالة L(i)‎ تمثّل طول أطول تسلسل فرعي تصاعدي ينتهي بالموقع i بشرط أن يكون العنصر arr[i]‎ آخر عنصر في التسلسل الفرعي.

يمكن كتابة الدالة L(i)‎ بالطريقة التعاودية التالية: L(i) = 1 + max( L(j) )‎ إذ ‎0 < j < i و ‎arr[j] < arr[i];‎ أو L(i) = 1 إن لم تكن j موجودة.

ولإيجاد أطول تسلسل فرعي تصاعدي للمصفوفة المعطاة يجب إعادة القيمة max(L(i))‎ إذ ‎0 < i < n‎.

يلاحظ هنا أنّ مسألة أطول تسلسل فرعي تصاعدي تتصف بصفة البنية الفرعية المثالية وذلك لأنّ بالإمكان حلّ المسألة الرئيسية باستخدام حلول المسائل المتفرّعة عنها.

تعرض الأمثلة التالية طريقة إيجاد أطول تسلسل فرعي تصاعدي بطريقة تعاودية.

يجب أن تعيد الدالة أمرين وذلك للاستفادة من الاستدعاءات التعاودية، وهذان الأمران هما:

1. طول أطول تسلسل فرعي تصاعدي ينتهي بالعنصر arr[n-1]‎. تستخدم الأمثلة التالية المتغير max_ending_here لهذا الغرض.
2. القيمة القصوى الكلية، وذلك لأنّ أطول تسلسل فرعي صاعدي قد ينتهي بعنصر يسبق العنصر arr[n-1]‎. تستخدم الأمثلة المتغير max_ref لهذا الغرض.

• C++‎:

#include<stdio.h> 
#include<stdlib.h> 

// تخزّن قيمة أطول تسلسل فرعي تصاعدي 
// *max_ref لكامل المصفوفة ذات الحجم المعطى في المتغير 
// والذي سيمثل النتيجة النهائية

int _lis( int arr[], int n, int *max_ref) 
{ 
	/* الحالة الأساس */
	if (n == 1) 
		return 1; 

	// 'max_ending_here'
	// arr[n-1] هو طول أطول تسلسل فرعي تصاعدي ينتهي بالعنصر
	int res, max_ending_here = 1; 

	/* استخدام التعاود في الحصول  على التسلسل الفرعي الأطول التصاعدي
	الذي ينتهي بالعناصر
	arr[0], arr[1] ... arr[n-2]. 
	arr[i-1] إن كان العنصر
	arr[n-1] مشابهًا للعنصر
	arr[n-1] وكانت النهاية العظمى مع العنصر
	بحاجة إلى تحديث، فسنحدّثها
	*/
	for (int i = 1; i < n; i++) 
	{ 
		res = _lis(arr, i, max_ref); 
		if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here) 
			max_ending_here = res + 1; 
	} 

	// max_ending_here مقارنة المتغير
	// القيمة القصوى الكلية وتحديث الأخيرة إن لزم الأمر
	if (*max_ref < max_ending_here) 
	*max_ref = max_ending_here; 

	// arr[n-1] إعادة طول أطول تسلسل فرعي تصاعدي ينتهي بالعنصر
	return max_ending_here; 
} 

// دالة تغلف الدالة السابقة
int lis(int arr[], int n) 
{ 
	// يحمل هذا المتغير النتيجة
	int max = 1; 

	// max تخزّن الدالة السابقة النتيجة في المتغير
	_lis( arr, n, &max ); 

	return max; 
} 

/* اختبار الدالة السابقة */
int main() 
{ 
	int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	printf("Length of lis is %dn", 
		lis( arr, n )); 
	return 0; 
}

• بايثون:

"""تخزّن قيمة أطول تسلسل فرعي تصاعدي 
*max_ref لكامل المصفوفة ذات الحجم المعطى في """

# متغير عام لتخزين القيمة القصوى
global maximum 

def _lis(arr , n ): 

	# السماح بالوصول إلى المتغير العام
	global maximum 

	# الحالة الأساس
	if n == 1 : 
		return 1

	# maxEndingHere
	# arr[n-1] هو طول أطول تسلسل فرعي تصاعدي ينتهي بالعنصر 
	maxEndingHere = 1

	"""استخدام التعاود في الحصول  على التسلسل الفرعي الأطول التصاعدي
	الذي ينتهي بالعناصر
	arr[0], arr[1] ... arr[n-2]. 
	arr[i-1] إن كان العنصر
	arr[n-1] مشابهًا للعنصر
	arr[n-1] وكانت النهاية العظمى مع العنصر
	بحاجة إلى تحديث، فسنحدّثها"""
	for i in xrange(1, n): 
		res = _lis(arr , i) 
		if arr[i-1] < arr[n-1] and res+1 > maxEndingHere: 
			maxEndingHere = res +1
	# maxEndingHere مقارنة المتغير
	// القيمة القصوى الكلية وتحديث الأخيرة إن لزم الأمر
	maximum = max(maximum , maxEndingHere) 

	return maxEndingHere 

def lis(arr): 

	# الوصول إلى المتغير العام
	global maximum 

	# arr طول المصفوفة 
	n = len(arr) 

	# يحمل هذا المتغير النتيجة
	maximum = 1

	# max تخزّن الدالة السابقة النتيجة في المتغير 
	_lis(arr , n) 

	return maximum 

# اختبار الدالة السابقة
arr = [10 , 22 , 9 , 33 , 21 , 50 , 41 , 60] 
n = len(arr) 
print "Length of lis is ", lis(arr)

• جافا:

class LIS 
{ 
static int max_ref; // يخزّن هذا المتغير أطول تسلسل فرعي تصاعدي

/* تخزّن قيمة أطول تسلسل فرعي تصاعدي 
*max_ref لكامل المصفوفة ذات الحجم المعطى في المتغير 
والذي سيمثل النتيجة النهائية */
static int _lis(int arr[], int n) 
{ 
	// الحالة الأساس
	if (n == 1) 
		return 1; 

	// 'max_ending_here'
	// arr[n-1] هو طول أطول تسلسل فرعي تصاعدي
	int res, max_ending_here = 1; 

		/* استخدام التعاود في الحصول  على التسلسل الفرعي الأطول التصاعدي
	الذي ينتهي بالعناصر
	arr[0], arr[1] ... arr[n-2]. 
	arr[i-1] إن كان العنصر
	arr[n-1] مشابهًا للعنصر
	arr[n-1] وكانت النهاية العظمى مع العنصر
	بحاجة إلى تحديث، فسنحدّثها */
		for (int i = 1; i < n; i++) 
		{ 
			res = _lis(arr, i); 
			if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here) 
				max_ending_here = res + 1; 
		} 

		// max_ending_here مقارنة المتغير
		// القيمة القصوى الكلية وتحديث الأخيرة إن لزم الأمر
		if (max_ref < max_ending_here) 
		max_ref = max_ending_here; 

		// arr[n-1] إعادة طول أطول تسلسل فرعي تصاعدي ينتهي بالعنصر
		return max_ending_here; 
} 

	// دالة تغلف الدالة السابقة 
	static int lis(int arr[], int n) 
	{ 
		// يحمل هذا المتغير النتيجة 
		max_ref = 1; 

		// max تخزّن الدالة السابقة النتيجة في المتغير
		_lis( arr, n); 

		return max_ref; 
	} 

	// اختبار التابع السابق
	public static void main(String args[]) 
	{ 
		int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; 
		int n = arr.length; 
		System.out.println("Length of lis is "
						+ lis(arr, n) + "\n"); 
	} 
}

مسائل فرعية متداخلة

تعطي طريقة التنفيذ السابقة شجرة التعاود التالية لمصفوفة ذات أربعة عناصر. تعطي الدالة lis(n)‎ في هذه الشجرة طول أطول سلسلة فرعية تصاعدية للمصفوفة arr[]‎.

             lis(4)
        /        |     
      lis(3)    lis(2)   lis(1)
     /           /
   lis(2) lis(1) lis(1)
   /
lis(1)

يلاحظ ممّا سبق وجود العديد من المسائل الفرعية التي يجري حلّها مرارًا وتكرارًا، وهذا يعني أنّ هذه المسألة تمتلك خاصية البنى الفرعية المتداخلة وأنّ بالإمكان تجنّب إعادة حساب نفس المسألة الفرعية باستخدام التحفيظ Memoization أو الجدولة Tabulation.

يعرض المثال التالي كيفية تنفيذ طريقة الجدول في حل مسألة إيجاد أطول تسلسل فرعي تصاعدي:

• C++‎:

#include<bits/stdc++.h> 
using namespace std; 
	
// تعيد الدالة طول أطول تسلسل فرعي تصاعدي في المصفوفة المعطاة ذات الحجم المعطى
int lis( int arr[], int n ) 
{ 
	int lis[n]; 

	lis[0] = 1; 

	/* حساب قيم خوارزمية أطول تسلسل فرعي تصاعدي المحسّنة
	باستخدام طريقة "من الأسفل إلى الأعلى" */
	for (int i = 1; i < n; i++ ) 
	{ 
		lis[i] = 1; 
		for (int j = 0; j < i; j++ ) 
			if ( arr[i] > arr[j] && lis[i] < lis[j] + 1) 
				lis[i] = lis[j] + 1; 
	} 

	// lis[] إعادة أكبر قيمة في المصفوفة
	return *max_element(lis, lis+n); 
} 
	
/* اختبار الدالة السابقة */
int main() 
{ 
	int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	printf("Length of lis is %d\n", lis( arr, n ) ); 
	return 0; 
}

• بايثون:

# تعيد الدالة طول أطول تسلسل فرعي تصاعدي في المصفوفة المعطاة ذات الحجم المعطى
def lis(arr): 
	n = len(arr) 

	# التصريح عن القائمة المسؤولة عن تخزين قيم أطول تسلسل فرعي تصاعدي
	lis = [1]*n 

	# حساب قيم خوارزمية أطول تسلسل فرعي تصاعدي المحسّنة
	# باستخدام طريقة "من الأسفل إلى الأعلى"
	for i in range (1 , n): 
		for j in range(0 , i): 
			if arr[i] > arr[j] and lis[i]< lis[j] + 1 : 
				lis[i] = lis[j]+1

	# تهيئة القيمة القصوى لتكون صفرًا
	# وذلك للحصول على القيمة القصوى لكل القيم
	# في أطول تسلسل فرعي تصاعدي
	maximum = 0

	# اختيار أكبر قيمة من قيم أطول تسلسل فرعي تصاعدي
	for i in range(n): 
		maximum = max(maximum , lis[i]) 

	return maximum 

# اختبار الدالة السابقة
arr = [10, 22, 9, 33, 21, 50, 41, 60] 
print "Length of lis is", lis(arr)

• جافا:

class LIS 
{ 
	/* تعيد الدالة طول أطول تسلسل فرعي تصاعدي في المصفوفة المعطاة ذات الحجم المعطى */
	static int lis(int arr[],int n) 
	{ 
		int lis[] = new int[n]; 
		int i,j,max = 0; 

		/* تهيئة قيم المصفوفة التي ستُخزَّن فيها قيم أطول تسلسل فرعي تصاعدي */
		for ( i = 0; i < n; i++ ) 
			lis[i] = 1; 

		/* حساب قيم خوارزمية أطول تسلسل فرعي تصاعدي المحسّنة
		باستخدام طريقة "من الأسفل إلى الأعلى" */
		for ( i = 1; i < n; i++ ) 
			for ( j = 0; j < i; j++ ) 
						if ( arr[i] > arr[j] && lis[i] < lis[j] + 1) 
					lis[i] = lis[j] + 1; 

		
		/* اختيار أكبر قيمة من قيم أطول تسلسل فرعي تصاعدي */
		for ( i = 0; i < n; i++ ) 
			if ( max < lis[i] ) 
				max = lis[i]; 

			return max; 
	} 

	public static void main(String args[]) 
	{ 
		int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; 
			int n = arr.length; 
			System.out.println("Length of lis is " + lis( arr, n ) + "\n" ); 
	} 
}

التعقيد الزمني

يبلغ التعقيد الزمني لهذه الخوارزمية المقدار O(n^2)‎.

مصادر

• صفحة Longest Increasing Subsequence | DP-3 في توثيق الخوارزميات في موقع GeeksforGeeks.