اكتشاف فشل النهج الجشع
العثور على أمثلة مضادة قبل الوثوق به
اكتشاف فشل النهج الجشع درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
الخوارزمية الجشعة مغرية
الخوارزمية الجشعة قصيرة وسريعة وتبدو بديهية، وهذا تحديدًا ما قد يوقعك في الفخ. فالفكرة الواضحة ليست بالضرورة صحيحة. ⚠️
فخ تبديل العملات
مع العملات 1 و3 و4، يؤدي تكوين القيمة 6 بطريقة جشعة إلى اختيار 4، ثم الحاجة إلى عملتي 1، أي ما مجموعه ثلاث عملات. أما الحل الأفضل فعلًا فهو عملتا 3.
ما الذي حدث بشكل خاطئ
كانت أكبر عملة مكسبًا محليًا، لكنها منعت الحل الأفضل عالميًا. لم تستطع الخوارزمية الجشعة التراجع عن اختيارها، فأخفقت في الوصول إلى إجابة العملتين.
ابحث عن مثال مضاد
أسرع اختبار لك هو مثال مضاد صغير: مُدخل صغير تختلف فيه نتيجة الخوارزمية الجشعة عن الحل الأمثل الحقيقي. يكفي مثال واحد لرفضها.
حقيبة الظهر 0/1 مجددًا
تفشل الخوارزمية الجشعة المعتمدة على النسبة مع العناصر غير القابلة للتقسيم؛ فقد يزاحم عنصر صغير ذو كثافة عالية عنصرين يتفوقان عليه عند أخذهما معًا. كانت إمكانية التقسيم هي الحرية المفقودة.
عندما تتفاعل الاختيارات
إذا غيّر اختيار عنصر ما العناصر الأخرى التي لا يزال يستحق أخذها، فغالبًا ما تفشل الخوارزمية الجشعة. وتشير التبعيات المتشابكة إلى استخدام البرمجة الديناميكية.
اختبرها تحت الضغط
اكتب حلًا بطيئًا بالقوة الغاشمة ومولّدًا عشوائيًا، ثم قارنهما على آلاف الحالات الصغيرة. يكشف اختلاف واحد الخلل.
for _ in range(10000):
t = random_case()
assert greedy(t) == brute(t)اختبار الاستبدال
للثقة بالخوارزمية الجشعة، حاول إثبات حجة استبدال. إذا لم تستطع إظهار أن الاختيار الجشع ينسجم مع حل أمثل ما، فابقَ متشككًا.
الخوارزمية الجشعة كإجراء فرعي
حتى عندما لا تكون الحل الكامل، يمكن أن تكون الخوارزمية الجشعة لبنة بناء داخل برمجة ديناميكية أو بحث أكبر. استخدمها حيث تكون آمنة بشكل مثبت.
اقرأ القيود
غالبًا ما يعني صِغر N أنك لا تحتاج إلى الخوارزمية الجشعة أصلًا. قد ينجح الحل بالقوة الغاشمة أو بالبرمجة الديناميكية، كما أنهما يتجنبان خطر الخطأ في الصحة تمامًا.
عادة توفر عليك النقاط
قبل إرسال تخمين جشع، خصص دقيقة للبحث عن مثال مضاد. يمنع هذا الفحص الصغير صدور حكم مؤلم بإجابة خاطئة.
فحص سريع
تشك في أن استراتيجية جشعة قد تكون خاطئة.
مراجعة
تفشل الخوارزمية الجشعة عندما يمنع مكسب محلي الحل الأفضل عالميًا، كما يحدث مع بعض مجموعات العملات وحقيبة الظهر 0/1. ابحث عن أمثلة مضادة واختبرها تحت الضغط قبل أن تثق بها. 🚀
الأسئلة الشائعة
هل درس «اكتشاف فشل النهج الجشع» مجاني؟
نعم — نص درس «اكتشاف فشل النهج الجشع» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «اكتشاف فشل النهج الجشع»؟
العثور على أمثلة مضادة قبل الوثوق به تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «اكتشاف فشل النهج الجشع»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- العقلية الجشعة
- اختيار الأنشطة حسب أقرب وقت انتهاء
- حقيبة العناصر الكسرية حسب النسبة
- اكتشاف فشل النهج الجشع