الخوارزميات الجشعة
تبني الخوارزميات الجشعة حلاً بشكل تدريجي عن طريق اتخاذ الخيار الذي يبدو الأفضل في الخطوة الحالية مرارًا وتكرارًا، وتكون صحيحة تحديدًا عندما تؤدي هذه الخيارات المثلى محليًا بشكل قاطع إلى حل أمثل عالميًا.
Definition
تبني الخوارزمية الجشعة حلاً من خلال سلسلة من الخيارات، يُختار كل منها لتحسين معيار محلي معين، دون مراجعة الخيارات السابقة أبدًا؛ وتكون صحيحة فقط عندما تؤدي الخيارات المثلى محليًا إلى نتيجة مثلى عالميًا.
Scope
يغطي هذا الموضوع النموذج الجشع: خاصية الاختيار الجشع والبنية الفرعية المثلى التي تبرره، وتقنيات الإثبات القياسية (حجج التبادل وإطار الماترويد)، والخوارزميات الجشعة الأساسية بما في ذلك ترميز هوفمان، وأشجار الامتداد الدنيا (كروسكال وبريم)، وأقصر المسارات لديجكسترا، وجدولة الفترات. كما يتناول متى تعمل الاستراتيجيات الجشعة كاستدلالات تقريبية فقط بدلاً من كونها طرقًا دقيقة.
Core questions
- ما هي خاصية الاختيار الجشع، وكيف يتم إثباتها لمشكلة معينة؟
- كيف تُظهر حجة التبادل أن الاختيار الجشع آمن؟
- ما هي المشكلات التي تحتوي على بنية ماترويد تضمن الأمثلية الجشعة؟
- متى تكون الطريقة الجشعة مجرد تقريب وليست خوارزمية دقيقة؟
- كيف تقارن الطريقة الجشعة بالبرمجة الديناميكية لنفس المشكلة؟
Key concepts
- خاصية الاختيار الجشع
- البنية الفرعية المثلى
- حجة التبادل
- الماترويدات
- ترميز هوفمان
- شجرة الامتداد الدنيا
- جدولة الفترات
- مسألة حقيبة الظهر الكسرية
Key theories
- خاصية الاختيار الجشع وحجج التبادل
- تقبل المشكلة حلاً جشعًا عندما يمكن دائمًا تعديل الحل الأمثل عالميًا ليتوافق مع الاختيار الجشع الأول دون فقدان الأمثلية؛ وتُضفي حجج التبادل (أو 'الجشع يبقى متقدمًا') الطابع الرسمي على ذلك.
- الماترويدات والأمثلية الجشعة
- عندما تشكل الحلول الممكنة المجموعات المستقلة لماترويد مرجح، فإن الخوارزمية الجشعة تجد دائمًا مجموعة مستقلة ذات وزن أقصى؛ وهذا يوحد النتائج مثل أمثلية خوارزمية شجرة الامتداد الدنيا لكروسكال.
Clinical relevance
تدفع الخوارزميات الجشعة أنظمة مستخدمة على نطاق واسع: ترميز هوفمان في تنسيقات ضغط البيانات، وخوارزميات شجرة الامتداد الدنيا في تصميم الشبكات، وخوارزمية ديجكسترا في التوجيه والملاحة، وجدولة جشعة واستدلالات تغطية المجموعات في أنظمة التشغيل وتخصيص الموارد.
History
يظهر التفكير الجشع في نتائج كلاسيكية مثل خوارزميات شجرة الامتداد الدنيا لكروسكال (1956) وبريم (1957)، ورموز البادئة المثلى لهوفمان (1952)، وخوارزمية أقصر المسارات لديجكسترا (1959). وقد تم تطوير التفسير النظري للماترويد لمتى تنجح الطرق الجشعة بواسطة إدموندز وآخرين في الستينيات والسبعينيات.
Key figures
- David A. Huffman
- Joseph Kruskal
- Robert Prim
- Edsger W. Dijkstra
Related topics
Seminal works
- dijkstra1959
- cormen2009
Frequently asked questions
- لماذا تعمل الخوارزمية الجشعة لمسألة حقيبة الظهر الكسرية ولكن ليس لمسألة حقيبة الظهر 0/1؟
- في مسألة حقيبة الظهر الكسرية، يمكن تقسيم العناصر، لذا فإن أخذ العنصر ذي أعلى قيمة لكل وزن أولاً يكون آمنًا دائمًا ومثاليًا بشكل قاطع. في مسألة حقيبة الظهر 0/1، العناصر غير قابلة للتجزئة، ويمكن أن يمنع الاختيار الجشع تركيبة أفضل، وتتطلب البرمجة الديناميكية للحصول على الأمثل الدقيق.
- كيف تثبت صحة خوارزمية جشعة؟
- التقنيتان القياسيتان هما حجة التبادل، التي تحول أي حل أمثل إلى الحل الجشع دون تدهوره، وحجة 'الجشع يبقى متقدمًا'، التي تُظهر أن الحل الجزئي الجشع لا يقل جودة عن أي حل آخر في كل خطوة. توفر نظرية الماترويد شرطًا كافيًا عامًا.