الخوارزميات الجشعة
ما الذي يجعل الخوارزمية جشعة؟
تقوم الخوارزمية الجشعة ببناء حل خطوة بخطوة، واختيار الخيار الذي يبدو أفضل الآن دائمًا - دون إعادة النظر في الاختيارات السابقة. لا تراجع ولا نظر للأمام.
إنه يعمل عندما تحتوي على خاصيتين:
- خاصية الاختيار الجشع - يؤدي الاختيار الأمثل محليًا إلى الحل الأمثل عالميًا.
- البنية الأساسية المثالية - المشكلة المتبقية بعد كل اختيار هي مثال أصغر لنفس المشكلة.
اختيار النشاط - المثال الكلاسيكي
بالنظر إلى مجموعة من الأنشطة ذات أوقات البدء والانتهاء، حدد الحد الأقصى للأنشطة غير المتداخلة.
استراتيجية الجشع: قم بالفرز حسب وقت الانتهاء، واختر دائمًا النشاط الذي ينتهي مبكرًا.
def max_activities(intervals):
intervals.sort(key=lambda x: x[1])
count, end = 0, 0
for s, e in intervals:
if s >= end:
count += 1
end = e
return count
لماذا يعمل هذا؟ إن اختيار النشاط الذي تم الانتهاء منه في أقرب وقت يترك المجال الأكبر للأنشطة المستقبلية. لا يوجد خيار آخر يمكن أن يفعل ما هو أفضل.
ترميز هوفمان - المفهوم
أنشئ رمزًا ثنائيًا مثاليًا خاليًا من البادئات من خلال الدمج المتكرر للرمزين الأقل ترددًا**. هذا جشع: في كل خطوة، قم بدمج الزوج الأرخص. والنتيجة هي شجرة حيث تحصل الرموز المتكررة على رموز قصيرة.
لعبة القفز
بالنظر إلى مصفوفة حيث nums[i] هو الحد الأقصى لطول القفز من الفهرس i، حدد ما إذا كان يمكنك الوصول إلى الفهرس الأخير.
النهج الجشع: تتبع أبعد مؤشر يمكن الوصول إليه حتى الآن. قم بالمسح من اليسار إلى اليمين - إذا تخلفت عن الركب، فارجع كاذبًا.
def can_jump(nums):
farthest = 0
for i, jump in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + jump)
return True
في لعبة القفز، ماذا يمثل المتغير الجشع ”الأبعد”؟
مناقشة
تسجيل الدخول للانضمام إلى النقاش