الخوارزمية الجشعة مع مثال: ما هي الطريقة والنهج

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

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

حل المشكلة باستخدام النهج الجشع يتكون من مرحلتين:

1. مسح قائمة العناصر
2. التحسين

تعمل المرحلتان بالتوازي حيث يتم تقسيم مصفوفة الإدخال تدريجياً.

لاتباع النهج الجشع، فإن المعرفة العملية بالاستدعاء الذاتي وتبديل السياق تساعدك trace الكود. يمكن وصف النموذج الجشع بزوج من العبارات الضرورية والكافية.

هناك شرطان يحددان النموذج الجشع.

• يجب أن يوجه كل خيار تدريجي المشكلة نحو الحل الأمثل المقبول لها.
• يجب أن تتوقف بنية المشكلة عند عدد محدود من الخطوات الجشعة.

بعد وضع النظرية موضع التنفيذ، دعونا نلقي نظرة على التاريخ الكامن وراء نهج البحث الجشع.

تاريخ الجشع Algorithms

فيما يلي أهم المحطات في تاريخ الخوارزميات الجشعة:

• تم وضع الخوارزميات الجشعة لأول مرة لخوارزميات اجتياز الرسوم البيانية في الخمسينيات من القرن الماضي.
• قام إدسكار ديكسترا بتطوير خوارزمية أقصر مسار لتقصير الطرق عبر العاصمة الهولندية أمستردام.
• في نفس العقد، طور بريم وكروسكال استراتيجيات تحسين تقلل من تكاليف المسار على طول الطرق الموزونة لبناء أشجار ممتدة دنيا.
• في سبعينيات القرن الماضي، وصف الباحثون الأمريكيون كورمن، وليسرسون، وريفست، وستين، البنية الفرعية المتكررة للحلول الجشعة في كتابهم الكلاسيكي Introduction to Algorithms الكتب المدرسية.
• تم تصنيف نموذج البحث الجشع كاستراتيجية تحسين مميزة في سجلات المعهد الوطني للمعايير والتكنولوجيا في عام 2005.
• وحتى يومنا هذا، تستخدم بروتوكولات الويب مثل بروتوكول Open Shortest Path First (OSPF) والعديد من بروتوكولات تبديل الحزم استراتيجية الجشع لتقليل وقت العبور على الشبكة.

الاستراتيجيات والقرارات الجشعة

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

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

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

خصائص الخوارزمية الجشعة

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

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

لماذا نستخدم النهج الجشع؟

فيما يلي أسباب استخدام النهج الجشع:

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

كيفية حل مشكلة اختيار النشاط

في مثال جدولة الأنشطة، لكل نشاط وقت بدء ووقت انتهاء، ويتم ترقيمه برقم للرجوع إليه. يوجد نوعان من الأنشطة:

1. النشاط المعتبر: النشاط المرجعي الذي تُقاس من خلاله القدرة على استيعاب المزيد من الأنشطة المتبقية.
2. الأنشطة المتبقية: الأنشطة في واحد أو أكثر من الفهارس قبل النشاط المعني.

تكلفة أداء نشاط ما هي مدته، والتي يتم حسابها على النحو التالي: (النهاية - البداية).

إن المدى الجشع هو ببساطة عدد الأنشطة المتبقية التي يمكن القيام بها في غضون وقت النشاط المعتبر.

Archiبنية النهج الجشع

الخطوة 1) قم بمسح قائمة تكاليف النشاط بدءًا من الفهرس 0 باعتباره الفهرس المعتبر.

الخطوة 2) عندما يمكن أن تنتهي المزيد من الأنشطة بحلول وقت انتهاء النشاط المحدد، ابحث عن تلك الأنشطة المتبقية.

الخطوة 3) إذا لم يكن بالإمكان جدولة المزيد من الأنشطة، يصبح النشاط المتبقي حاليًا هو النشاط التالي الذي سيتم النظر فيه. كرر الخطوتين 1 و2 مع النشاط الجديد الذي سيتم النظر فيه. إذا لم يتبق أي أنشطة، فانتقل إلى الخطوة 4.

الخطوة 4) أعد اتحاد المؤشرات التي تم أخذها في الاعتبار - هذه هي مؤشرات النشاط التي تزيد الإنتاجية إلى أقصى حد.

Archiبنية النهج الجشع

Code تفسير

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

#define MAX_ACTIVITIES 12

شرح الكود:

1. ملفات/فئات الرأس المضمنة
2. الحد الأقصى لعدد الأنشطة التي يمكن للمستخدم ضبطها.

using namespace std;

class TIME
{
    public:
    int hours;

    public: TIME()
    {
   	 hours = 0;
    }
};

شرح الكود:

1. يُعلن عن مساحة الاسم القياسية لعمليات البث.
2. تعريف فئة TIME
3. الطابع الزمني ساعة.
4. مُنشئ افتراضي للوقت
5. الساعات متغيرة.

class Activity
{
    public:
    int index;
    TIME start;
    TIME finish;

    public: Activity()
    {
   	 start = finish = TIME();
    }
};

شرح الكود:

1. تعريف فئة للنشاط.
2. الطوابع الزمنية التي تحدد معًا مدة زمنية.
3. يتم تهيئة جميع الطوابع الزمنية إلى 0 في المُنشئ الافتراضي.

class Scheduler
{
    public:
    int considered_index,init_index;
    Activity *current_activities = new    Activity[MAX_ACTIVITIES];
    Activity *scheduled;

شرح الكود:

1. الجزء الأول من تعريف فئة الجدولة.
2. يُعتبر considered_index نقطة البداية لمسح المصفوفة.
3. يتم استخدام init_index لتعيين طوابع زمنية عشوائية أثناء الإعداد.
4. يتم تخصيص مجموعة من كائنات النشاط ديناميكيًا باستخدام عامل التشغيل الجديد.
5. يحتوي المؤشر المُجدول على نتيجة البحث الجشع الحالية.

Scheduler()
{
   	 considered_index = 0;
   	 scheduled = NULL;
...
...

شرح الكود:

1. مُنشئ المُجدول - الجزء الثاني من تعريف الفئة.
2. يشير considered_index إلى بداية عملية المسح الحالية.
3. يكون نطاق الجشع غير محدد في البداية.

for(init_index = 0; init_index < MAX_ACTIVITIES; init_index++)
 {
   		 current_activities[init_index].start.hours =
   			 rand() % 12;

   		 current_activities[init_index].finish.hours =
   			 current_activities[init_index].start.hours +
   				 (rand() % 2);

   		 printf("\nSTART:%d END %d\n",
   		 current_activities[init_index].start.hours
   		 ,current_activities[init_index].finish.hours);
 }
&#8230;
&#8230;

شرح الكود:

1. تقوم حلقة التكرار "for" بتهيئة ساعات بدء وانتهاء كل نشاط مُجدول.
2. يقوم بتهيئة وقت البدء.
3. يُهيئ وقت الانتهاء ليكون في ساعة البداية أو بعدها.
4. تقوم عبارة تصحيح الأخطاء بطباعة المدد الزمنية المخصصة.

	public:
   		 Activity * activity_select(int);
};

شرح الكود:

1. الجزء 4 - الجزء الأخير من تعريف فئة Scheduler.
2. تأخذ الدالة activity_select() فهرس البداية كأساس وتقسم المهمة الجشعة إلى مشاكل فرعية.

Activity * Scheduler :: activity_select(int considered_index)
{
    this->considered_index = considered_index;
    int greedy_extent = this->considered_index + 1;
…
…

1. يربط عامل تحديد النطاق (::) تعريف الدالة بفئة Scheduler.
2. يتم تمرير considered_index بالقيمة، ويتم تهيئة greedy_extent إلى الفهرس الذي يليه مباشرة.

Activity * Scheduler :: activity_select(int considered_index)
{
    	while( (greedy_extent < MAX_ACTIVITIES ) &&
   	 ((this->current_activities[greedy_extent]).start.hours <
   		 (this->current_activities[considered_index]).finish.hours ))
    	{
   	 printf("\nSchedule start:%d \nfinish%d\n activity:%d\n",
   	 (this->current_activities[greedy_extent]).start.hours,
   	 (this->current_activities[greedy_extent]).finish.hours,
   	 greedy_extent + 1);
   	 greedy_extent++;
    	}
&#8230;
...

شرح الكود:

1. المنطق الأساسي - يتم تحديد النطاق الجشع عند MAX_ACTIVITIES.
2. يتم التحقق من ساعة بدء النشاط الحالي مقابل ساعة انتهاء النشاط المعني.
3. طالما أن الشرط قائم، يتم طباعة عبارة تصحيح اختيارية.
4. ثم ينتقل النطاق الجشع إلى الفهرس التالي في مصفوفة النشاط.

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

   	 return activity_select(greedy_extent);
    }
    else
    {
   	 return NULL;
    }
}

شرح الكود:

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

int main()
{
    Scheduler *activity_sched = new Scheduler();
    activity_sched->scheduled = activity_sched->activity_select(
   				activity_sched->considered_index);
    return 0;
}

شرح الكود:

1. تقوم الدالة الرئيسية باستدعاء المجدول.
2. يتم إنشاء كائن جدولة جديد.
3. تقوم الدالة activity_select() بإرجاع مؤشر Activity إلى المستدعي بمجرد انتهاء المهمة الجشعة.

الإخراج:

START:7 END 7

START:9 END 10

START:5 END 6

START:10 END 10

START:9 END 10

Schedule start:5
finish6
 activity:3

Schedule start:9
finish10
 activity:5

حدود تقنية الجشع

إن النهج الجشع غير مناسب للمشاكل التي تتطلب حلاً أمثل لكل مشكلة فرعية، مثل الفرز.

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

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

يوضح الرسم البياني أدناه هذا العيب في الطريقة الجشعة.

في عملية المسح الجشع الموضحة هنا على شكل شجرة (القيمة الأعلى تعني جشعًا أعلى)، فإن الخوارزمية عند القيمة 40 ستختار 29 بعد ذلك، ثم تنتهي عند 12، ليصبح المجموع 41.

وعلى النقيض من ذلك، فإن استراتيجية فرق تسد ستتبع 25 مع 40 ليصبح المجموع 65، وهو أعلى بمقدار 24 نقطة من الخيار الجشع محليًا.

أمثلة على الجشع Algorithms

تعتمد معظم خوارزميات الشبكات على نهج جشع. ومن الأمثلة الشائعة على الخوارزميات الجشعة ما يلي:

• خوارزمية بريم للشجرة الممتدة الدنيا
• مشكلة البائع المتجول (تقريبًا)
• تلوين الخرائط البيانية
• خوارزمية كروسكال للشجرة الممتدة الدنيا
• خوارزمية ديكسترا لأقصر مسار
• غطاء رأس الرسم البياني
• مشكلة الحقيبة
• تسلسل المهام مع مراعاة المواعيد النهائية

الأسئلة الشائعة