الفرق بين المراجعتين لصفحة: «Algorithms/Greedy Algorithms»
لا ملخص تعديل |
لا ملخص تعديل |
||
| سطر 1: | سطر 1: | ||
<noinclude>{{DISPLAYTITLE:الخوارزميات الجشعة}}</noinclude> | <noinclude>{{DISPLAYTITLE:الخوارزميات الجشعة}}</noinclude> | ||
الخوارزميات الجشعة هي إحدى [[Algorithms/Algorithm Paradigms|أساليب الخوارزميات Algorithm paradigm]] التي تصل إلى الحل خطوة فخطوة وذلك بالحرص على أن تقدّم الخطوة التالية أعظم فائدة ممكنة في طريق الوصول إلى الحل؛ ولهذا فإنّ المسائل التي يؤدي فيها اختيار حلول محلية فضلى local optimal إلى الوصول إلى حلول عامة فضلى global optimal، تكون هي الأكثر ملائمة للخوارزميات الجشعة، مثل مسألة حقيبة الظهر المجزئة Fractional Knapsack | الخوارزميات الجشعة هي إحدى [[Algorithms/Algorithm Paradigms|أساليب الخوارزميات Algorithm paradigm]] التي تصل إلى الحل خطوة فخطوة وذلك بالحرص على أن تقدّم الخطوة التالية أعظم فائدة ممكنة في طريق الوصول إلى الحل؛ ولهذا فإنّ المسائل التي يؤدي فيها اختيار حلول محلية فضلى local optimal إلى الوصول إلى حلول عامة فضلى global optimal، تكون هي الأكثر ملائمة للخوارزميات الجشعة، مثل [[Algorithms/fractional knapsack|مسألة حقيبة الظهر المجزئة Fractional Knapsack Problem]]، إذ يكون الحل المحلّي الأفضل هو اختيار العنصر الذي يمتلك أعلى نسبة (قيمة إلى وزن). يؤدي الاعتماد على هذه الطريقة إلى الوصول إلى حل مثالي عام وذلك لأنّ اختيار أجزاء من العناصر مسموح به في هذه الحالة. | ||
تستخدم الخوارزميات الجشعة كذلك في حل مسائل الأمثلية optimization problems. إن كان بالإمكان اتخاذ قرار يكون هو الأفضل في كلّ خطوة وكان بالإمكان الوصول إلى الحل الأمثل للمسألة برمتها، فيمكن للخوارزمية الجشعة حينئذٍ حلّ هذه المسألة. | تستخدم الخوارزميات الجشعة كذلك في حل مسائل الأمثلية optimization problems. إن كان بالإمكان اتخاذ قرار يكون هو الأفضل في كلّ خطوة وكان بالإمكان الوصول إلى الحل الأمثل للمسألة برمتها، فيمكن للخوارزمية الجشعة حينئذٍ حلّ هذه المسألة. | ||
إن كان بإمكان الخوارزمية الجشعة إيجاد حل لمسألة معينة، فإنّ نموذج الخورازميات هذا سيكون النموذج الأفضل لحلّ المسألة لأنّه أكثر فعّاليةً من الأساليب الأخرى مثل [[Algorithms/Dynamic Programming|البرمجة الديناميكية]]. ولكن لا يمكن تطبيق نموذج الخوارزمية الجشعة في كل الحالات، فعلى سبيل المثال يمكن حل | إن كان بإمكان الخوارزمية الجشعة إيجاد حل لمسألة معينة، فإنّ نموذج الخورازميات هذا سيكون النموذج الأفضل لحلّ المسألة لأنّه أكثر فعّاليةً من الأساليب الأخرى مثل [[Algorithms/Dynamic Programming|البرمجة الديناميكية]]. ولكن لا يمكن تطبيق نموذج الخوارزمية الجشعة في كل الحالات، فعلى سبيل المثال يمكن حل مسألة حقيبة الظهر المجزئة باستخدام هذا النموذج ولكن لا يمكن حل مسألة حقيبة الظهر 1-0 بواسطة هذا النموذج. | ||
يمكن استخدام أسلوب الخوارزميات الجشعة في بعض الأحيان للحصول على حل تقريبي لبعض مسائل الأمثلية الصعبة. فعلى سبيل المثال تصنف مسألة البائع المتجول ضمن مشاكل NP-Hard. والاختيار الجشع هنا هو في التقاط أقرب مدينة غير مزورة من المدينة الحالية في كل خطوة من خطوات الحل. قد لا تعطي هذه الطريقة الحل الأمثل في كل مرة ولكن يمكن الاستفادة منها في الوصول إلى حل مثالي تقريبًا. | |||
== خوارزميات جشعة == | == خوارزميات جشعة == | ||
| سطر 10: | سطر 12: | ||
=== [[Algorithms/Huffman coding|ترميز هوفمان]] === | === [[Algorithms/Huffman coding|ترميز هوفمان]] === | ||
ترميز هوفمان هو من إحدى تقنيات الضغط دون خسارة البيانات. يُسند هذا الترميز رموز بتات bit codes ذات أطوال مختلفة إلى محارف مختلفة. الاختيار الجشع هنا هو إسناد شيفرة الرموز الأقصر طولًا للمحارف الأكثر تكرارًا. | ترميز هوفمان هو من إحدى تقنيات الضغط دون خسارة البيانات. يُسند هذا الترميز رموز بتات bit codes ذات أطوال مختلفة إلى محارف مختلفة. الاختيار الجشع هنا هو إسناد شيفرة الرموز الأقصر طولًا للمحارف الأكثر تكرارًا. | ||
=== [[Algorithms/activity selection|مسألة اختيار النشاط]] === | === [[Algorithms/activity selection|مسألة اختيار النشاط]] === | ||
| سطر 21: | سطر 21: | ||
=== [[Algorithms/egpytian fraction|مسألة الكسر المصري]] === | === [[Algorithms/egpytian fraction|مسألة الكسر المصري]] === | ||
يمكن تمثيل أي كسر موجب كمجموع لعدد من الكسور الوحدية unit fractions الفريدة. يكون الكسر كسرًا وحديًا عندما يكون بسطه <code>1</code> ومقامه عددًا صحيحًا موجبًا، فعلى سبيل المثال يمثل الكسر <code>1/3</code> كسرًا وحديًّا. تسمى طريقة التمثيل هذه بالكسر المصري Egyptian Fraction وذلك لأنّها كانت تستخدم من قبل المصريين القدماء. | يمكن تمثيل أي كسر موجب كمجموع لعدد من الكسور الوحدية unit fractions الفريدة. يكون الكسر كسرًا وحديًا عندما يكون بسطه <code>1</code> ومقامه عددًا صحيحًا موجبًا، فعلى سبيل المثال يمثل الكسر <code>1/3</code> كسرًا وحديًّا. تسمى طريقة التمثيل هذه بالكسر المصري Egyptian Fraction وذلك لأنّها كانت تستخدم من قبل المصريين القدماء. | ||
=== [[Algorithms/job sequencing|مسألة تسلسل الأعمال]] === | |||
لنفترض أن لدينا مصفوفة تضمّ عددًا من الأعمال التي يرتبط كلٌّ منها بموعد للإنجاز وبمردود مالي يمكن الحصول عليه عند إتمام العمل قبل الموعد المحدد. ولنفترض أنّ كل عمل يستغرق وحدة واحدة من الزمن، وبهذا يكون أقل موعد مسموح به لإنجاز العمل هو <code>1</code>. كيف يمكن زيادة المردود المالي الكلي إن كان بالإمكان القيام بعمل واحد فقط في نفس الوقت؟ | |||
=== [[Algorithms/shelves fitting|مسألة ملائمة الرفوف على الحائط]] === | |||
لو كان هناك جدار (<code>w</code>) ورفوف ذات طولين مختلفين <code>m</code> و <code>n</code>، فما هو عدد الرفوف من كلا النوعين والذي يجب استخدامه بشرط أن تكون المساحة الفارغة المتبقية قليلة قدر الإمكان. | |||
=== [[Algorithms/min max product subset|إيجاد مجموعة فرعية من مصفوفة تعطي حاصل الضرب المطلوب]] === | |||
تبحث هذه الخوارزمية عن المجموعة الفرعية ضمن مصفوفة الأعداد الصحيحة المعطاة والتي تعطي أكبر قيمة أو أصغر قيمة ممكنة لحاصل ضرب عناصر المجموعة الفرعية. | |||
=== [[Algorithms/partition allocation methods|طرق تعيين الأقسام في إدارة الذاكرة]] === | |||
عند توفّر أكثر من جزء واحد شاغر لتلبية متطلبات عملية معيّنة، فيجب حينئذٍ اختيار جزء من الذاكرة، وتتطلب عملية الاختيار هذه استخدام طريقة معيّنة في حجز جزء معين من الذاكرة. | |||
== الخوارزميات الجشعة في الرسوم البيانية == | == الخوارزميات الجشعة في الرسوم البيانية == | ||
| سطر 33: | سطر 45: | ||
تشبه خوارزمية ديكسترا خوارزمية برم إلى حدٍّ كبير، إذ يُبنى المسار الأقصر ضلعًا تلو الآخر، وهناك مجموعتان في هذه الخوارزمية: الأولى هي مجموعة الرؤوس الموجودة فعلًا في الشجرة الممتدة الصغرى والثانية هي مجموعة الرؤوسة غير الموجودة في الشجرة. الاختيار الجشع هنا هو انتخاب الضلع الذي يربط بين المجموعتين بشرط أن يكون على المسار الذي يمتلك أصغر وزن من المصدر إلى المجموعة التي تحتوي على الرؤوس غير المضمّنة في الشجر بعد. | تشبه خوارزمية ديكسترا خوارزمية برم إلى حدٍّ كبير، إذ يُبنى المسار الأقصر ضلعًا تلو الآخر، وهناك مجموعتان في هذه الخوارزمية: الأولى هي مجموعة الرؤوس الموجودة فعلًا في الشجرة الممتدة الصغرى والثانية هي مجموعة الرؤوسة غير الموجودة في الشجرة. الاختيار الجشع هنا هو انتخاب الضلع الذي يربط بين المجموعتين بشرط أن يكون على المسار الذي يمتلك أصغر وزن من المصدر إلى المجموعة التي تحتوي على الرؤوس غير المضمّنة في الشجر بعد. | ||
=== [[Algorithms/Boruvka MST|خوارزمية بوروفكا]] === | |||
تعدّ خوارزمية بوروفكا أقدم خوارزمية لإيجاد الشجرة الممتدة الصغرى وقد وضعها بوروفكا سنة 1926م، قبل اختراع الحواسيب بفترة طويلة، وقد نشرت هذه الخوارزمية كطريقة لبناء شبكة فعّالة من التمديدات الكهربائية. | |||
[[تصنيف: الخوارزميات]] | [[تصنيف: الخوارزميات]] | ||
[[تصنيف: الخوارزميات الجشعة]] | [[تصنيف: الخوارزميات الجشعة]] | ||
مراجعة 06:36، 8 ديسمبر 2019
الخوارزميات الجشعة هي إحدى أساليب الخوارزميات Algorithm paradigm التي تصل إلى الحل خطوة فخطوة وذلك بالحرص على أن تقدّم الخطوة التالية أعظم فائدة ممكنة في طريق الوصول إلى الحل؛ ولهذا فإنّ المسائل التي يؤدي فيها اختيار حلول محلية فضلى local optimal إلى الوصول إلى حلول عامة فضلى global optimal، تكون هي الأكثر ملائمة للخوارزميات الجشعة، مثل مسألة حقيبة الظهر المجزئة Fractional Knapsack Problem، إذ يكون الحل المحلّي الأفضل هو اختيار العنصر الذي يمتلك أعلى نسبة (قيمة إلى وزن). يؤدي الاعتماد على هذه الطريقة إلى الوصول إلى حل مثالي عام وذلك لأنّ اختيار أجزاء من العناصر مسموح به في هذه الحالة.
تستخدم الخوارزميات الجشعة كذلك في حل مسائل الأمثلية optimization problems. إن كان بالإمكان اتخاذ قرار يكون هو الأفضل في كلّ خطوة وكان بالإمكان الوصول إلى الحل الأمثل للمسألة برمتها، فيمكن للخوارزمية الجشعة حينئذٍ حلّ هذه المسألة.
إن كان بإمكان الخوارزمية الجشعة إيجاد حل لمسألة معينة، فإنّ نموذج الخورازميات هذا سيكون النموذج الأفضل لحلّ المسألة لأنّه أكثر فعّاليةً من الأساليب الأخرى مثل البرمجة الديناميكية. ولكن لا يمكن تطبيق نموذج الخوارزمية الجشعة في كل الحالات، فعلى سبيل المثال يمكن حل مسألة حقيبة الظهر المجزئة باستخدام هذا النموذج ولكن لا يمكن حل مسألة حقيبة الظهر 1-0 بواسطة هذا النموذج.
يمكن استخدام أسلوب الخوارزميات الجشعة في بعض الأحيان للحصول على حل تقريبي لبعض مسائل الأمثلية الصعبة. فعلى سبيل المثال تصنف مسألة البائع المتجول ضمن مشاكل NP-Hard. والاختيار الجشع هنا هو في التقاط أقرب مدينة غير مزورة من المدينة الحالية في كل خطوة من خطوات الحل. قد لا تعطي هذه الطريقة الحل الأمثل في كل مرة ولكن يمكن الاستفادة منها في الوصول إلى حل مثالي تقريبًا.
خوارزميات جشعة
ترميز هوفمان
ترميز هوفمان هو من إحدى تقنيات الضغط دون خسارة البيانات. يُسند هذا الترميز رموز بتات bit codes ذات أطوال مختلفة إلى محارف مختلفة. الاختيار الجشع هنا هو إسناد شيفرة الرموز الأقصر طولًا للمحارف الأكثر تكرارًا.
مسألة اختيار النشاط
تنص مسألة اختيار النشاط Activity Selection Problem على ما يلي:
إن كان هناك n من النشاطات مع أوقات بدء وانتهاء كلّ نشاط. اختر أقصى عدد ممكن من النشاطات التي يمكن لشخص واحد أن يؤديها بافتراض أنّ ذلك الشخص قادرٌ على تأدية نشاط واحدة في كل مرة.
مسألة الكسر المصري
يمكن تمثيل أي كسر موجب كمجموع لعدد من الكسور الوحدية unit fractions الفريدة. يكون الكسر كسرًا وحديًا عندما يكون بسطه 1 ومقامه عددًا صحيحًا موجبًا، فعلى سبيل المثال يمثل الكسر 1/3 كسرًا وحديًّا. تسمى طريقة التمثيل هذه بالكسر المصري Egyptian Fraction وذلك لأنّها كانت تستخدم من قبل المصريين القدماء.
مسألة تسلسل الأعمال
لنفترض أن لدينا مصفوفة تضمّ عددًا من الأعمال التي يرتبط كلٌّ منها بموعد للإنجاز وبمردود مالي يمكن الحصول عليه عند إتمام العمل قبل الموعد المحدد. ولنفترض أنّ كل عمل يستغرق وحدة واحدة من الزمن، وبهذا يكون أقل موعد مسموح به لإنجاز العمل هو 1. كيف يمكن زيادة المردود المالي الكلي إن كان بالإمكان القيام بعمل واحد فقط في نفس الوقت؟
مسألة ملائمة الرفوف على الحائط
لو كان هناك جدار (w) ورفوف ذات طولين مختلفين m و n، فما هو عدد الرفوف من كلا النوعين والذي يجب استخدامه بشرط أن تكون المساحة الفارغة المتبقية قليلة قدر الإمكان.
إيجاد مجموعة فرعية من مصفوفة تعطي حاصل الضرب المطلوب
تبحث هذه الخوارزمية عن المجموعة الفرعية ضمن مصفوفة الأعداد الصحيحة المعطاة والتي تعطي أكبر قيمة أو أصغر قيمة ممكنة لحاصل ضرب عناصر المجموعة الفرعية.
طرق تعيين الأقسام في إدارة الذاكرة
عند توفّر أكثر من جزء واحد شاغر لتلبية متطلبات عملية معيّنة، فيجب حينئذٍ اختيار جزء من الذاكرة، وتتطلب عملية الاختيار هذه استخدام طريقة معيّنة في حجز جزء معين من الذاكرة.
الخوارزميات الجشعة في الرسوم البيانية
خوارزمية كروسكال للشجرة الممتدة الصغرى
يتم إنشاء الشجرة الممتدة الصغرى في هذه الخوارزمية عن طريق اختيار الأضلاع واحدًا تلو الآخر. الاختيار الجشع هنا هو التقاط الضلع الذي يمتلك أصغر وزن بحيث لا يتسبب ذلك في إنشاء دائرة في الشجرة الممتدة قيد الإنشاء.
خوارزمية برم للشجرة الممتدة الصغرى
يتم إنشاء الشجرة الممتدة الصغرى في هذه الخوارزمية كذلك عن طريق اختيار الأضلاع واحدًا تلو الآخر. هناك مجموعتان في هذه الخوارزمية: الأولى هي مجموعة الرؤوس الموجودة فعلًا في الشجرة الممتدة الصغرى والثانية هي مجموعة الرؤوسة غير الموجودة في الشجرة. الاختيار الجشع هنا هو التقاط الضلع الذي يمتلك أصغر وزن والذي يربط بين المجموعتين.
خوارزمية ديكسترا لإيجاد المسار الأقصر
تشبه خوارزمية ديكسترا خوارزمية برم إلى حدٍّ كبير، إذ يُبنى المسار الأقصر ضلعًا تلو الآخر، وهناك مجموعتان في هذه الخوارزمية: الأولى هي مجموعة الرؤوس الموجودة فعلًا في الشجرة الممتدة الصغرى والثانية هي مجموعة الرؤوسة غير الموجودة في الشجرة. الاختيار الجشع هنا هو انتخاب الضلع الذي يربط بين المجموعتين بشرط أن يكون على المسار الذي يمتلك أصغر وزن من المصدر إلى المجموعة التي تحتوي على الرؤوس غير المضمّنة في الشجر بعد.
خوارزمية بوروفكا
تعدّ خوارزمية بوروفكا أقدم خوارزمية لإيجاد الشجرة الممتدة الصغرى وقد وضعها بوروفكا سنة 1926م، قبل اختراع الحواسيب بفترة طويلة، وقد نشرت هذه الخوارزمية كطريقة لبناء شبكة فعّالة من التمديدات الكهربائية.