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

الخوارزميات الجشعة هي إحدى أساليب الخوارزميات Algorithm paradigm التي تصل إلى الحل خطوة فخطوة وذلك بالحرص على أن تقدّم الخطوة التالية أعظم فائدة ممكنة في طريق الوصول إلى الحل؛ ولهذا فإنّ المسائل التي يؤدي فيها اختيار حلول محلية فضلى local optimal إلى الوصول إلى حلول عامة فضلى global optimal، تكون هي الأكثر ملائمة للخوارزميات الجشعة، مثل مسألة حقيبة الظهر المجزئة Fractional Knapsack Problem، إذ يكون الحل المحلّي الأفضل هو اختيار العنصر الذي يمتلك أعلى نسبة (قيمة إلى وزن). يؤدي الاعتماد على هذه الطريقة إلى الوصول إلى حل مثالي عام وذلك لأنّ اختيار أجزاء من العناصر مسموح به في هذه الحالة.

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

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

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

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

ترميز هوفمان

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

مسألة اختيار النشاط

المطلوب في مسألة اختيار النشاط Activity Selection Problem هو تحديد كيفية اختيار أقصى عدد ممكن من النشاطات التي يمكن لشخص واحد أن يؤديها بافتراض أنّ ذلك الشخص قادرٌ على تأدية نشاط واحدة في كل مرة، إن كان هناك n من النشاطات مع أوقات بدء وانتهاء كلّ نشاط.

مسألة حقيبة الظهر المجزأة

المطلوب في مسألة حقيبة الظهر المجزّأة Fractional Knapsack هو وضع مجموعة من العناصر ذات أوزان وقيم محددة في حقيبة ظهر تتسع لعدد معين من العناصر مع مراعاة الحصول على أكبر قيمة ممكنة لمجموع قيم العناصر الموجودة في الحقيبة.

مسألة الكسر المصري

يمكن تمثيل أي كسر موجب كمجموع لعدد من الكسور الوحدية unit fractions الفريدة. يكون الكسر كسرًا وحديًا عندما يكون بسطه 1 ومقامه عددًا صحيحًا موجبًا، فعلى سبيل المثال يمثل الكسر 1/3 كسرًا وحديًّا. تسمى طريقة التمثيل هذه بالكسر المصري Egyptian Fraction وذلك لأنّها كانت تستخدم من قبل المصريين القدماء.

مسألة تسلسل الأعمال

لنفترض أن لدينا مصفوفة تضمّ عددًا من الأعمال التي يرتبط كلٌّ منها بموعد للإنجاز وبمردود مالي يمكن الحصول عليه عند إتمام العمل قبل الموعد المحدد. ولنفترض أنّ كل عمل يستغرق وحدة واحدة من الزمن، وبهذا يكون أقل موعد مسموح به لإنجاز العمل هو 1. كيف يمكن زيادة المردود المالي الكلي إن كان بالإمكان القيام بعمل واحد فقط في نفس الوقت؟

مسألة ملائمة الرفوف على الحائط

لو كان هناك جدار (w) ورفوف ذات طولين مختلفين m و n، فما هو عدد الرفوف من كلا النوعين والذي يجب استخدامه بشرط أن تكون المساحة الفارغة المتبقية قليلة قدر الإمكان.

إيجاد مجموعة فرعية من مصفوفة تعطي حاصل الضرب المطلوب

تبحث هذه الخوارزمية عن المجموعة الفرعية ضمن مصفوفة الأعداد الصحيحة المعطاة والتي تعطي أكبر قيمة أو أصغر قيمة ممكنة لحاصل ضرب عناصر المجموعة الفرعية.

تقسيم مكعب إلى مكعبات بأقصى حجم ممكن

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

طرق تعيين الأقسام في إدارة الذاكرة

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

الخوارزميات الجشعة في الرسوم البيانية

خوارزمية كروسكال للشجرة الممتدة الصغرى

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

خوارزمية برم للشجرة الممتدة الصغرى

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

خوارزمية ديكسترا لإيجاد المسار الأقصر

تشبه خوارزمية ديكسترا خوارزمية برم إلى حدٍّ كبير، إذ يُبنى المسار الأقصر ضلعًا تلو الآخر، وهناك مجموعتان في هذه الخوارزمية: الأولى هي مجموعة الرؤوس الموجودة فعلًا في الشجرة الممتدة الصغرى والثانية هي مجموعة الرؤوسة غير الموجودة في الشجرة. الاختيار الجشع هنا هو انتخاب الضلع الذي يربط بين المجموعتين بشرط أن يكون على المسار الذي يمتلك أصغر وزن من المصدر إلى المجموعة التي تحتوي على الرؤوس غير المضمّنة في الشجر بعد.

خوارزمية بوروفكا

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