خوارزمية جشعة

الخوارزمية الجشعة هي خوارزمية تتخذ، في كل خطوة، الخيار الأمثل محليًا، ولا تعيد النظر في الخيارات السابقة. تُستخدم الخوارزميات الجشعة غالبًا لحل مسائل التحسين التوافقي . إذا كانت مسألة التحسين تعتمد فقط على الحل الجزئي لمسألة فرعية واحدة، فيمكننا حل هذه المسألة بالنظر "بشكل جشع" إلى المسألة الفرعية الأمثل محليًا فقط. وبهذا المعنى، تُعد الخوارزمية الجشعة حالة خاصة من خوارزمية البرمجة الديناميكية . ويشير أورييل فيج ^{[ 1 ]} إلى ما يلي:

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

في كثير من الحالات، لا تُنتج الخوارزمية الجشعة حلاً دقيقاً، ولكنها قد تُنتج حلولاً تقارب الحل الدقيق في فترة زمنية معقولة. ^{[ 2 ]}

مثال على مشكلة تقبل حلاً دقيقاً باستخدام خوارزمية جشعة هو مشكلة اختيار النشاط . بالنظر إلى مجموعة من المهام التي يمكن إنجازها خلال فترات زمنية محددة، تكمن المشكلة في تحديد الحد الأقصى لعدد المهام التي يمكن إنجازها. تُستخدم خوارزمية جشعة في حل هذه المشكلة.${\displaystyle O(n\log(n))}$يقوم هذا الأسلوب بحل هذه المشكلة عن طريق فرز المهام حسب وقت الانتهاء ثم يختار بشكل متكرر المهمة الأولى التي تبدأ بعد انتهاء المهمة الأخيرة.

تستخدم العديد من الخوارزميات الكلاسيكية في علوم الحاسوب، مثل خوارزمية ترميز هوفمان ، وخوارزمية بريم ، وخوارزمية كروسكال ، وخوارزمية ديكسترا ، خصائص الجشع في تصميمها. كما يستخدم علماء الرياضيات استراتيجيات الجشع بكثرة في البراهين. ومن الأمثلة الكلاسيكية على ذلك ما يُشير إليه رافائيل يوستر بالبرهان الجشع ^{[ 3 ]} الذي يُثبت أن كل دورة في الرسم البياني تحتوي على مسار هاميلتوني .

نظرًا لعدم وجود تعريف رسمي للخوارزمية الجشعة، ^{[ 4 ]} فإنّ توصيفًا كاملًا للحالات التي تقبل فيها المسألة خوارزمية جشعة كحل غير معروف. مع ذلك، تمّ تحديد حالات خاصة. فقد بيّن جاك إدموندز إمكانية استخدام خوارزمية جشعة لحلّ فئة من مسائل التحسين التوافقي الخطي ذات البنية الماترويدية. ^{[ 5 ]}

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

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

إحدى التقنيات المستخدمة لإثبات أمثلية الخوارزميات الجشعة هي حجة التبادل. ^{[ 6 ]} تُبين حجة التبادل أن أي حل يختلف عن الحل الجشع لا يتجاوز في جودته الحل الجشع. ويتبع نمط هذا البرهان عادةً الخطوات التالية:

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

أمثلة على كيفية فشل الخوارزمية الجشعة في تحقيق الحل الأمثل

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

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

• في مسألة حقيبة الظهر الجزئية ، تُعطى قائمة من العناصر بأوزانها وقيمها. والهدف هو اختيار كميات جزئية من كل عنصر بحيث تكون القيمة الإجمالية في أعلى مستوياتها، ويكون الوزن أقل من حدٍّ مُحدد. على عكس مسألة حقيبة الظهر التقليدية ، المعروفة بصعوبتها من فئة NP-hard ، فإن مسألة حقيبة الظهر الجزئية تقبل خوارزمية جشعة ذات زمن متعدد الحدود.
• تسمح حالات مسألة عملة فروبينيوس بحلول جشعة. ومع ذلك، في بعض الحالات لا تؤدي الخوارزمية الجشعة إلى حل أمثل. ^{[ 7 ]}
• يُعد البحث المطابق مثالاً على خوارزمية جشعة تُطبق على تقريب الإشارة.
• تجد الخوارزمية الجشعة الحل الأمثل لمشكلة مالفاتي المتمثلة في إيجاد ثلاث دوائر منفصلة داخل مثلث معين تعمل على زيادة المساحة الإجمالية للدوائر؛ ويُفترض أن الخوارزمية الجشعة نفسها هي الأمثل لأي عدد من الدوائر.
• في تعلم شجرة القرار ، تُستخدم الخوارزميات الجشعة بشكل شائع، ومع ذلك فهي ليست مضمونة لإيجاد الحل الأمثل.
  • ومن بين هذه الخوارزميات الشائعة خوارزمية ID3 لبناء شجرة القرار.
• تُنشئ خوارزمية جشعة تمثيل زيكندورف (أو ترميز فيبوناتشي) لعدد طبيعي. ويُعطي طرح أكبر عدد فيبوناتشي أصغر من أو يساوي العدد الطبيعي بشكل متكرر تمثيل زيكندورف الخاص به. وتُستخلص الخوارزمية الجشعة من برهان وجود تمثيل زيكندورف. ويضمن تفرد تمثيل زيكندورف أنه لا يمكن لأي مجموع فيبوناتشي غير متتالي أن يُعطي ناتجًا مختلفًا.
• وصف فيبوناتشي خوارزمية جشعة لحساب الكسور المصرية .
• تظهر الخوارزميات الجشعة في توجيه الشبكات . باستخدام التوجيه الجشع، تُعاد توجيه الرسالة إلى العقدة المجاورة الأقرب إلى الوجهة. قد يُحدد موقع العقدة (وبالتالي قربها) بموقعها الفعلي، كما هو الحال في التوجيه الجغرافي المستخدم في الشبكات المخصصة . وقد يكون الموقع أيضًا مفهومًا اصطناعيًا بالكامل، كما هو الحال في توجيه العالم الصغير وجداول التجزئة الموزعة .

تُعدّ نظرية الرسوم البيانية مصدراً غنياً للخوارزميات الجشعة. ويستخدم علماء الحاسوب هذه الخوارزميات بكثرة لحساب ثوابت الرسوم البيانية.

• تعتبر خوارزمية ديكسترا وخوارزمية البحث A* ذات الصلة خوارزميات جشعة مثالية يمكن التحقق منها للبحث في الرسوم البيانية وإيجاد أقصر مسار .
  • تعتبر خوارزمية البحث A* مثالية بشكل مشروط، مما يتطلب " طريقة استدلالية مقبولة " لا تبالغ في تقدير تكاليف المسار.
• تُعدّ خوارزمية كروسكال وخوارزمية بريم خوارزميات جشعة تُستخدم لبناء أشجار ممتدة دنيا لرسم بياني متصل مُعطى . وهي تجد دائمًا حلاً أمثل، قد لا يكون فريدًا في العموم.
• تقوم خوارزمية جشعة بإنشاء شجرة هوفمان في ترميز هوفمان .
• تعتبر خوارزميات Sequitur و Lempel -Ziv-Welch خوارزميات جشعة لاستقراء القواعد النحوية .
• تجد الخوارزمية الجشعة أكبر مجموعة مستقلة في الشجرة.

تُستخدم الخوارزميات الجشعة أيضًا لإيجاد حدود عليا للأعداد اللونية ^{[ 8 ]} . ومن الأمثلة البسيطة على ذلك الحد${\displaystyle \chi (G)\leq \Delta (G)+1}$تم الحصول عليها بواسطة خوارزمية جشعة. ^{[ 9 ]} نبدأ بأخذ رأس لم يتم تلوينه. بما أنه يحتوي على أكثر من${\displaystyle \Delta (G)}$الجيران، على الأكثر${\displaystyle \Delta (G)}$تُستخدم الألوان في الرؤوس المتجاورة، مما يترك لونًا حرًا للرأس قيد الدراسة.

يمكن تقريب حل مسألة البائع المتجول، وهي مسألة كاملة من فئة NP، بالبدء من مجموعة حواف فارغة ثم إضافة الحافة الأرخص التالية، والتي تمثل رسمًا بيانيًا فرعيًا لجولة كاملة. وقد ثبت أن هذه الخوارزمية الجشعة تُنتج على الأكثر${\displaystyle \Theta (\log n)}$^{[ 10 ]} أطول من الجولة المثلى.

مثال آخر هو أنه يمكن تقريب حل مسألة حقيبة الظهر 0-1 باستخدام الخوارزمية الجشعة لمسألة حقيبة الظهر الكسرية . وقد ثبت أن هذه الخوارزمية الجشعة تُعطي حلاً لا يقل عن نصف قيمة الحل الأمثل. ^{[ 11 ]}

يتم تقريب حلول تعظيم الدوال شبه المعيارية باستخدام خوارزمية جشعة تُنتج حلاً لا يقل عن نصف قيمة الحل الأمثل. ^{[ 12 ]}

تتضمن المشاكل التي تستخدم فيها الخوارزميات الجشعة لتوفير خوارزميات التقريب مشكلة تغطية المجموعة ، وموازنة الحمل ، وشجرة شتاينر ، والمجموعة المستقلة ^{[ 13 ] .}

• "الخوارزمية الجشعة" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]
• هدية، نوح. "مثال على جشع بايثون في العملات المعدنية" .