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

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

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

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

مع استمرار التنظير، دعونا نصف التاريخ المرتبط بمنهج البحث الجشع.

تاريخ الجشع Algorithms

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

• تم تصور الخوارزميات الجشعة للعديد من خوارزميات المشي البياني في الخمسينيات من القرن العشرين.
• قام Esdger Djikstra بوضع تصور للخوارزمية لإنشاء الحد الأدنى من الأشجار الممتدة. كان يهدف إلى تقصير مدى الطرق داخل العاصمة الهولندية أمستردام.
• وفي نفس العقد، حقق بريم وكروسكال استراتيجيات التحسين التي تعتمد على تقليل تكاليف المسار على طول المسارات الموزونة.
• في سبعينيات القرن العشرين، اقترح الباحثون الأمريكيون كورمن، وريفست، وستاين، هيكلة فرعية متكررة للحلول الجشعة في كتابهم الكلاسيكي "مقدمة إلى الخوارزميات".
• تم تسجيل نموذج البحث الجشع كنوع مختلف من إستراتيجية التحسين في سجلات NIST في عام 2005.
• حتى الآن، تستخدم البروتوكولات التي تقوم بتشغيل الويب، مثل بروتوكول فتح أقصر مسار أولاً (OSPF) والعديد من بروتوكولات تبديل حزم الشبكة الأخرى، الإستراتيجية الجشعة لتقليل الوقت المستغرق على الشبكة.

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

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

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

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

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

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

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

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

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

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

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

في مثال جدولة النشاط، يوجد وقت "بدء" و"انتهاء" لكل نشاط. يتم فهرسة كل نشاط برقم كمرجع. هناك فئتان للنشاط.

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

المدة الإجمالية تعطي تكلفة أداء النشاط. أي أن (الانتهاء – البدء) يعطينا المدة كتكلفة للنشاط.

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

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

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

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

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

الخطوة 4) إرجاع اتحاد المؤشرات المدروسة. هذه هي مؤشرات النشاط التي سيتم استخدامها لتعظيم الإنتاجية.

شرح الكود

#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. الفهرس المعتبر هو نقطة البداية لمسح مجموعة.
3. يتم استخدام فهرس التهيئة لتعيين طوابع زمنية عشوائية.
4. يتم تخصيص مجموعة من كائنات النشاط بشكل ديناميكي باستخدام عامل التشغيل الجديد.
5. يحدد المؤشر المجدول الموقع الأساسي الحالي للجشع.

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

شرح الكود:

1. منشئ المجدول – الجزء 2 من تعريف فئة المجدول.
2. يحدد الفهرس المدروس البداية الحالية للفحص الحالي.
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);
 }
…
…

شرح الكود:

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

	public:
   		 Activity * activity_select(int);
};

شرح الكود:

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

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

1. باستخدام عامل حل النطاق (::)، يتم توفير تعريف الوظيفة.
2. والمؤشر المعتبر هو المؤشر المسمى بالقيمة. إن 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++;
    	}
…
...

شرح الكود:

1. المنطق الأساسي- يقتصر مدى الجشع على عدد الأنشطة.
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. تعود وظيفة تحديد النشاط، التي تُرجع مؤشرًا من نوع النشاط، إلى المتصل بعد انتهاء المهمة الجشعة.

الإخراج:

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

تستخدم أغلب خوارزميات الشبكات النهج الجشع. وفيما يلي قائمة ببعض أمثلة الخوارزميات الجشعة:

• خوارزمية الشجرة الممتدة الصغرى لبريم
• مشكلة البائع المتجول
• الرسم البياني - تلوين الخريطة
• خوارزمية كروسكال للشجرة الممتدة
• خوارزمية ديكسترا للشجرة الممتدة
• الرسم البياني – غطاء قمة الرأس
• مشكلة الحقيبة
• مشكلة جدولة الوظائف

الملخص

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