Algorithms/Greedy Algorithms

الخوارزميات الجشعة هي إحدى نماذج الخوارزميات Algorithm paradigm التي تصل إلى الحل خطوة فخطوة وذلك بالحرص على أن تقدّم الخطوة التالية أعظم فائدة ممكنة في طريق الوصول إلى الحل؛ ولهذا فإنّ المشاكل التي يؤدي فيها اختيار حلول محلية فضلى local optimal إلى الوصول إلى حلول عامة فضلى global optimal، تكون هي الأكثر ملائمة للخوارزميات الجشعة، مثل مشكلة حقيبة الظهر المجزئة Fractional Knapsack Problem، إذ يكون الحل المحلّي الأفضل هو اختيار العنصر الذي يمتلك أعلى نسبة (قيمة إلى وزن). يؤدي الاعتماد على هذه الطريقة إلى الوصول إلى حل مثالي عام وذلك لأنّ اختيار أجزاء من العناصر مسموح به في هذه الحالة.

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

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

الخوارزميات التالية هي خوارزميات جشعة:

1- خوارزمية كروسكال للشجرة الممتدة الصغرى Kruskal's Minimum Spanning Tree (MST)‎: يتم إنشاء الشجرة الممتدة الصغرى في هذه الخوارزمية عن طريق اختيار الأضلاع واحدًا تلو الآخر. الاختيار الجشع هنا هو التقاط الضلع الذي يمتلك أصغر وزن بحيث لا يتسبب ذلك في إنشاء دائرة في الشجرة الممتدة قيد الإنشاء.

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

3- خوارزمية ديكسترا لإيجاد المسار الأقصر Dijkstra's Shortest Path: تشبه خوارزمية ديكسترا خوارزمية برم إلى حدٍّ كبير، إذ يُبنى المسار الأقصر ضلعًا تلو الآخر، هناك مجموعتان في هذه الخوارزمية: الأولى هي مجموعة الرؤوس الموجودة فعلًا في الشجرة الممتدة الصغرى والثانية هي مجموعة الرؤوسة غير الموجودة في الشجرة. الاختيار الجشع هنا هو التقاط الضلع الذي يربط بين المجموعتين والذي يكون على المسار الذي يمتلك أصغر وزن من المصدر إلى المجموعة التي تحتوي على الرؤوس غير المضمّنة في الشجر بعد.

4- ترميز هوفمان Huffman Coding: ترميز هوفمان هو من إحدى تقنيات الضغط دون خسارة البيانات. يُسند هذا الترميز رموز بتات bit codes ذات أطوال مختلفة إلى محارف مختلفة. الاختيار الجشع هنا هو إسناد شيفرة الرموز الأقصر طولًا للمحارف الأكثر تكرارًا.

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

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

تنص مسألة اختيار النشاط 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[]‎).

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

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

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

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

• 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)‎.