شرح الخوارزميات الجشعة بأمثلة

ما هي الخوارزمية الجشعة؟

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

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

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

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

تعريف رسمي

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

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

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

مشكلة جدولة الفاصل الزمني

دعنا نتعمق في مشكلة مثيرة للاهتمام يمكن أن تواجهها في أي صناعة تقريبًا أو في أي مجال من مجالات الحياة. بعض حالات المشكلة هي كما يلي:

  • يتم إعطاؤك مجموعة من جداول N من المحاضرات ليوم واحد في الجامعة. الجدول الزمني لمحاضرة محددة هو من النموذج ( الوقت ، الوقت f ) حيث يمثل الوقت s وقت البدء لتلك المحاضرة وبالمثل يمثل الوقت f وقت الانتهاء. بالنظر إلى قائمة جداول المحاضرات N ، نحتاج إلى تحديد أقصى مجموعة من المحاضرات التي سيتم عقدها خلال اليوم بحيث   لا تتداخل أي من المحاضرات مع بعضها البعض ، أي إذا تم تضمين المحاضرة Li و Lj في اختيارنا ، فإن وقت بدء j > = وقت الانتهاء من i أو العكس .
  • يعمل صديقك كمستشار في المخيم ، وهو مسؤول عن تنظيم الأنشطة لمجموعة من المعسكر. تتمثل إحدى خططه في تمرين الترياتلون المصغر التالي: يجب على كل متسابق السباحة 20 لفة في المسبح ، ثم ركوب الدراجة لمسافة 10 أميال ، ثم الركض لمسافة 3 أميال.
  • تتمثل الخطة في إرسال المتسابقين بطريقة متداخلة ، من خلال القاعدة التالية: يجب على المتسابقين استخدام المسبح واحدًا تلو الآخر. بعبارة أخرى ، يسبح المتسابق الأول في ال 20 لفة ويخرج ويبدأ في ركوب الدراجة.
  • بمجرد خروج هذا الشخص الأول من المسبح ، يبدأ المتسابق الثاني في السباحة في ال 20 لفة ؛ بمجرد أن يخرج هو أو هي ويبدأ ركوب الدراجة ، يبدأ متسابق ثالث في السباحة ، وهكذا.
  • لكل متسابق وقت السباحة المتوقع ووقت ركوب الدراجات المتوقع ووقت الجري المتوقع. يريد صديقك تحديد جدول زمني للسباق الثلاثي: ترتيب يتم بموجبه ترتيب بداية المتسابقين.
  • لنفترض أن وقت إكمال الجدول الزمني هو أقرب وقت ينتهي فيه جميع المتسابقين من جميع المراحل الثلاث للسباق الثلاثي ، على افتراض أن توقعات الوقت دقيقة. ما هو أفضل ترتيب لإرسال الأشخاص ، إذا أراد المرء أن تنتهي المنافسة بأكملها في أسرع وقت ممكن؟ بتعبير أدق ، قم بإعطاء خوارزمية فعالة تنتج جدولًا زمنيًا يكون وقت إكماله أقل ما يمكن

مشكلة جدولة المحاضرة

دعونا نلقي نظرة على الطرق المختلفة لحل هذه المشكلة.

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

أقرب وقت بداية أولا

أصغر فترة  زمنية أولاً ، أي أنك ستنتهي باختيار المحاضرات بالترتيب الزمني الإجمالي الذي لا يمثل سوى محاضراتها   finish time - start time. مرة أخرى ، هذا الحل غير صحيح. انظر إلى الحالة التالية.

أقصر فاصل زمني أولا

يمكنك أن ترى بوضوح أن أقصر فترة محاضرة هي المحاضرة في المنتصف ، لكن هذا ليس هو الحل الأمثل هنا. لنلقِ نظرة على حل آخر لهذه المشكلة من خلال استخلاص رؤى من هذا الحل.

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

أقل فترة تعارض أولاً

يوضح لنا الرسم التخطيطي أن الفاصل الزمني الأقل تضاربًا هو الفاصل الزمني الموجود في المنتصف مع تعارضين فقط. بعد ذلك يمكننا فقط اختيار فترتين في النهايتين مع تعارض 3 لكل منهما. لكن الحل الأمثل هو اختيار 4 فترات في المستوى الأعلى.

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

function interval_scheduling_problem(requests) schedule \gets \{\} while requests is not yet empty choose a request i_r \in requests that has the lowest finishing time schedule \gets schedule \cup \{i_r\} delete all requests in requests that are not compatible with i_r end return schedule end 

متى نستخدم الخوارزميات الجشعة

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

تساعدنا الخوارزميات الجشعة في حل الكثير من أنواع المشاكل المختلفة ، مثل:

أقصر طريق مشكلة:

الحد الأدنى من مشكلة الشجرة الممتدة في رسم بياني

مشكلة ترميز هوفمان

مشكلة مراكز K