مسألة اختيار النشاط

تنص مسألة اختيار النشاط Activity Selection Problem على ما يلي:

إن كان هناك n من النشاطات مع أوقات بدء وانتهاء كلّ نشاط. اختر أقصى عدد ممكن من النشاطات التي يمكن لشخص واحد أن يؤديها بافتراض أنّ ذلك الشخص قادرٌ على تأدية نشاط واحدة في كل مرة.

المثال الأول: لنفترض أن لدينا ثلاثة أنشطة مرتّبة حسب وقت الانتهاء:

start[] = {10, 12, 20};
finish[] = {20, 25, 30};

يمكن للشخص أن يؤدي تمرينين على الأكثر، وبهذا تكون أكبر مجموعة من التمارين التي يمكن تنفيذها من قبل شخص واحد هي ‎{0, 2}‎ (تشير الأرقام إلى موقع التمرين في المصفوفتين start[]‎ و finish[]‎). المثال الثاني: لنفترض أن لدينا ستة تمارين مرتّبة حسب وقت الانتهاء:

start[] = {1, 3, 0, 5, 8, 5};
finish[] = {2, 4, 6, 7, 9, 9};

يمكن للشخص الواحد أن يؤدي أربعة تمارين على الأكثر، وبهذا يصبح أكبر مجموعة من التمارين التي يمكن تنفيذها من قبل شخص واحد هي ‎{0, 1, 3, 4}‎. (تشير الأرقام إلى موقع التمرين في المصفوفتين start[]‎ و finish[]‎).

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

ويمكن تلخيص الخوارزمية بالخطوات التالية:

ترتيب النشاطات حسب وقت الانتهاء.
اختيار النشاط الأول من المصفوفة ذات العناصر المرتبة وطباعته.
إن كان وقت البدء لهذا النشاط أكبر من وقت انتهاء النشاط السابق الذي تم اختياره أو يساويه فسنختار هذا النشاط ونطبعه. (تنفذ هذه الخطوة على العناصر المتبقية في المصفوفة).

تنفيذ الخوارزمية

تعرض الشيفرات التالية طريقة تنفيذ هذه الخوارزمية في عدد من لغات البرمجة، وتفترض جميع هذه الشيفرات أنّ النشاطات مرتّبة في المصفوفات وفق وقت الانتهاء.

C++‎:

#include<stdio.h> 

// تطبع الدالة أكبر مجموعة من النشاطات التي يمكن لشخص واحد أن ينفذها، بشرط تنفيذ نشاط واحد في كل مرة.
// n --> العدد الكلي للنشاطات
// s[] --> مصفوفة تتضمن أوقات البدء الخاصة بكل التمارين
// f[] --> مصفوفة تتضمن أوقات الانتهاء الخاصة بكل التمارين
void printMaxActivities(int s[], int f[], int n) 
{ 
	int i, j; 

	printf ("Following activities are selected n"); 

	// يتم اختيار النشاط الأوّل دائمًا
	i = 0; 
	printf("%d ", i); 

	// المرور على بقية النشاطات
	for (j = 1; j < n; j++) 
	{ 
	// إن كان النشاط يمتلك وقت بدء أكبر من وقت انتهاء
    // النشاط السابق الذي تم اختياره أو يساويه
    // فسنختار هذا النشاط
	if (s[j] >= f[i]) 
	{ 
		printf ("%d ", j); 
		i = j; 
	} 
	} 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int s[] = {1, 3, 0, 5, 8, 5}; 
	int f[] = {2, 4, 6, 7, 9, 9}; 
	int n = sizeof(s)/sizeof(s[0]); 
	printMaxActivities(s, f, n); 
	return 0; 
}

بايثون:

""" تطبع الدالة أكبر مجموعة من النشاطات التي يمكن لشخص واحد أن ينفذها، بشرط تنفيذ نشاط واحد في كل مرة."""
# n --> العدد الكلي للنشاطات
# s[] --> مصفوفة تتضمن أوقات البدء الخاصة بكل التمارين
# f[] --> مصفوفة تتضمن أوقات الانتهاء الخاصة بكل التمارين

def printMaxActivities(s , f ): 
	n = len(f) 
	print "The following activities are selected"

	# يتم اختيار النشاط الأوّل دائمًا
	i = 0
	print i, 

	# المرور على بقية النشاطات
	for j in xrange(n): 

		
        # إن كان النشاط يمتلك وقت بدء أكبر من وقت انتهاء
	    # النشاط السابق الذي تم اختياره أو يساويه
	    # فسنختار هذا النشاط
		if s[j] >= f[i]: 
			print j, 
			i = j 

# اختبار الدوال السابقة
s = [1 , 3 , 0 , 5 , 8 , 5] 
f = [2 , 4 , 6 , 7 , 9 , 9] 
printMaxActivities(s , f)

جافا:

import java.util.*; 
import java.lang.*; 
import java.io.*; 

class ActivitySelection 
{ 
	// يطبع التابع أكبر مجموعة من النشاطات التي يمكن لشخص واحد أن ينفذها، بشرط تنفيذ نشاط واحد في كل مرة.
	// n --> العدد الكلي للنشاطات
	// s[] --> مصفوفة تتضمن أوقات البدء الخاصة بكل التمارين
	// f[] --> مصفوفة تتضمن أوقات الانتهاء الخاصة بكل التمارين
	public static void printMaxActivities(int s[], int f[], int n) 
	{ 
	int i, j; 
	
	System.out.print("Following activities are selected : n"); 
	
	// يتم اختيار النشاط الأول دائمًا 
	i = 0; 
	System.out.print(i+" "); 
	
	// المرور على بقية العناصر
	for (j = 1; j < n; j++) 
	{ 
		// إن كان النشاط يمتلك وقت بدء أكبر من وقت انتهاء
	    // النشاط السابق الذي تم اختياره أو يساويه
	    // فسنختار هذا النشاط

		if (s[j] >= f[i]) 
		{ 
			System.out.print(j+" "); 
			i = j; 
		} 
	} 
	} 
	
	// اختبار التوابع السابقة
	public static void main(String[] args) 
	{ 
	int s[] = {1, 3, 0, 5, 8, 5}; 
	int f[] = {2, 4, 6, 7, 9, 9}; 
	int n = s.length; 
		
	printMaxActivities(s, f, n); 
	} 
	
}

تعطي الشيفرات السابقة المخرجات التالية:

Following activities are selected
0 1 3 4

لنفترض أنّ لدينا مجموعة الأنشطة التالية S={1, 2, 3, …n}‎ وأنّ هذه الأنشطة مرتّبة حسب وقت انتهائها. الاختيار الجشع هنا هو التقاط النشاط الأول دائمًا، لأنّه الحل المثالي دائمًا مهما كانت محتويات المجموعة. ويمكن أن نبرهن على ذلك بإثبات أنّه في حال وجود الحل B إضافة إلى النشاط الأول، فسيكون هناك حلّ آخر هو الحل A وبالحجم نفسه مع النشاط 1 ليكون هو النشاط الأول. ولو افترضنا أنّ الحل B هو k فإن المجموعة A ستكون موجودة دائمًا ويمكن التعبير عنها بالعلاقة ‎A = {B - {k}} U {1}‎ (لاحظ أنّ النشاطات في المجموعة B مستقلة عن بعضها البعض وأنّ النشاط k يمتلك أقل وقت انتهاء من بين جميع النشاطات، ولما لم تكن قيمة k هي 1 فإنّ finish(k) >= finish(1)‎.

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

قد يبلغ التعقيد الزمني O(n log n)‎ إن لم يكن بالإمكان ترتيب النشاطات، أما إن كانت النشاطات مرتّبة دائمًا فإن التعقيد الزمني يبلغ O(n)‎.

مصادر

صفحة Activity Selection Problem في توثيق الخوارزميات في موقع GeeksforGeeks.