الفرق بين المراجعتين ل"Algorithms/Greedy Algorithms"

من موسوعة حسوب
اذهب إلى التنقل اذهب إلى البحث
 
(10 مراجعات متوسطة بواسطة نفس المستخدم غير معروضة)
سطر 1: سطر 1:
 
<noinclude>{{DISPLAYTITLE:الخوارزميات الجشعة}}</noinclude>
 
<noinclude>{{DISPLAYTITLE:الخوارزميات الجشعة}}</noinclude>
 +
الخوارزميات الجشعة هي إحدى [[Algorithms/Algorithm Paradigms|أساليب الخوارزميات Algorithm paradigm]] التي تصل إلى الحل خطوة فخطوة وذلك بالحرص على أن تقدّم الخطوة التالية أعظم فائدة ممكنة في طريق الوصول إلى الحل؛ ولهذا فإنّ المسائل التي يؤدي فيها اختيار حلول محلية فضلى local optimal إلى الوصول إلى حلول عامة فضلى global optimal، تكون هي الأكثر ملائمة للخوارزميات الجشعة، مثل [[Algorithms/fractional knapsack|مسألة حقيبة الظهر المجزئة Fractional Knapsack Problem]]، إذ يكون الحل المحلّي الأفضل هو اختيار العنصر الذي يمتلك أعلى نسبة (قيمة إلى وزن). يؤدي الاعتماد على هذه الطريقة إلى الوصول إلى حل مثالي عام وذلك لأنّ اختيار أجزاء من العناصر مسموح به في هذه الحالة.
  
−
الخوارزميات الجشعة هي إحدى نماذج الخوارزميات Algorithm paradigm التي تصل إلى الحل خطوة فخطوة وذلك بالحرص على أن تقدّم الخطوة التالية أعظم فائدة ممكنة في طريق الوصول إلى الحل؛ ولهذا فإنّ المشاكل التي يؤدي فيها اختيار حلول محلية فضلى local optimal إلى الوصول إلى حلول عامة فضلى global optimal، تكون هي الأكثر ملائمة للخوارزميات الجشعة، مثل مشكلة حقيبة الظهر المجزئة Fractional Knapsack Problem، إذ يكون الحل المحلّي الأفضل هو اختيار العنصر الذي يمتلك أعلى نسبة (قيمة إلى وزن). يؤدي الاعتماد على هذه الطريقة إلى الوصول إلى حل مثالي عام وذلك لأنّ اختيار أجزاء من العناصر مسموح به في هذه الحالة.
+
تستخدم الخوارزميات الجشعة كذلك في حل مسائل الأمثلية optimization problems. إن كان بالإمكان اتخاذ قرار يكون هو الأفضل في كلّ خطوة وكان بالإمكان الوصول إلى الحل الأمثل للمسألة برمتها، فيمكن للخوارزمية الجشعة حينئذٍ حلّ هذه المسألة.
  
−
تستخدم الخوارزميات الجشعة كذلك في حل مشاكل الأمثلية optimization problems. إن كان بالإمكان اتخاذ قرار يكون هو الأفضل في كلّ خطوة وكان بالإمكان الوصول إلى الحل الأمثل للمشكلة بأكملها، فيمكن للخوارزمية الجشعة حينئذٍ حلّ هذه المشكلة.
+
إن كان بإمكان الخوارزمية الجشعة إيجاد حل لمسألة معينة، فإنّ نموذج الخورازميات هذا سيكون النموذج الأفضل لحلّ المسألة لأنّه أكثر فعّاليةً من الأساليب الأخرى مثل [[Algorithms/Dynamic Programming|البرمجة الديناميكية]]. ولكن لا يمكن تطبيق نموذج الخوارزمية الجشعة في كل الحالات، فعلى سبيل المثال يمكن حل مسألة حقيبة الظهر المجزئة باستخدام هذا النموذج ولكن لا يمكن حل مسألة حقيبة الظهر 1-0 بواسطة هذا النموذج.
  
−
إن كان بإمكان الخوارزمية الجشعة إيجاد حل لمشكلة معينة، فإنّ نموذج الخورازميات هذا سيكون النموذج الأفضل لحلّ المشكلة لأنّه أكثل فعّاليةً من النماذج الأخرى مثل البرمجة الديناميكية. ولكن لا يمكن تطبيق نموذج الخوارزمية الجشعة في كل الحالات، فعلى سبيل المثال يمكن حل مشكلة حقيبة الظهر المجزئة باستخدام هذا النموذج ولكن لا يمكن حل مشكلة حقيبة الظهر 1-0 بواسطة هذا النموذج.
+
يمكن استخدام أسلوب الخوارزميات الجشعة في بعض الأحيان للحصول على حل تقريبي لبعض مسائل الأمثلية الصعبة. فعلى سبيل المثال تصنف مسألة البائع المتجول ضمن مشاكل NP-Hard. والاختيار الجشع هنا هو في التقاط أقرب مدينة غير مزورة من المدينة الحالية في كل خطوة من خطوات الحل. قد لا تعطي هذه الطريقة الحل الأمثل في كل مرة ولكن يمكن الاستفادة منها في الوصول إلى حل مثالي تقريبًا.
  
−
الخوارزميات التالية هي خوارزميات جشعة:
+
== خوارزميات جشعة ==
  
−
'''1- خوارزمية كروسكال للشجرة الممتدة الصغرى Kruskal's Minimum Spanning Tree (MST)‎''': يتم إنشاء الشجرة الممتدة الصغرى في هذه الخوارزمية عن طريق اختيار الأضلاع واحدًا تلو الآخر. الاختيار الجشع هنا هو التقاط الضلع الذي يمتلك أصغر وزن بحيث لا يتسبب ذلك في إنشاء دائرة في الشجرة الممتدة قيد الإنشاء.
+
=== [[Algorithms/Huffman coding|ترميز هوفمان]] ===
 +
ترميز هوفمان هو من إحدى تقنيات الضغط دون خسارة البيانات. يُسند هذا الترميز رموز بتات bit codes ذات أطوال مختلفة إلى محارف مختلفة. الاختيار الجشع هنا هو إسناد شيفرة الرموز الأقصر طولًا للمحارف الأكثر تكرارًا.
  
−
'''2- خوارزمية برم للشجرة الممتدة الصغرى''': يتم إنشاء الشجرة الممتدة الصغرى في هذه الخوارزمية كذلك عن طريق اختيار الأضلاع واحدًا تلو الآخر. هناك مجموعتان في هذه الخوارزمية: الأولى هي مجموعة الرؤوس الموجودة فعلًا في الشجرة الممتدة الصغرى والثانية هي مجموعة الرؤوسة غير الموجودة في الشجرة. الاختيار الجشع هنا هو التقاط الضلع الذي يمتلك أصغر وزن والذي يربط بين المجموعتين.
+
=== [[Algorithms/activity selection|مسألة اختيار النشاط]] ===
  
−
'''3- خوارزمية ديكسترا لإيجاد المسار الأقصر Dijkstra's Shortest Path''': تشبه خوارزمية ديكسترا خوارزمية برم إلى حدٍّ كبير، إذ يُبنى المسار الأقصر ضلعًا تلو الآخر، هناك مجموعتان في هذه الخوارزمية: الأولى هي مجموعة الرؤوس الموجودة فعلًا في الشجرة الممتدة الصغرى والثانية هي مجموعة الرؤوسة غير الموجودة في الشجرة. الاختيار الجشع هنا هو التقاط الضلع الذي يربط بين المجموعتين والذي يكون على المسار الذي يمتلك أصغر وزن من المصدر إلى المجموعة التي تحتوي على الرؤوس غير المضمّنة في الشجر بعد.
+
المطلوب في مسألة اختيار النشاط Activity Selection Problem هو تحديد كيفية اختيار أقصى عدد ممكن من النشاطات التي يمكن لشخص واحد أن يؤديها بافتراض أنّ ذلك الشخص قادرٌ على تأدية نشاط واحدة في كل مرة،  إن كان هناك <code>n</code> من النشاطات مع أوقات بدء وانتهاء كلّ نشاط.
  
−
'''4- ترميز هوفمان Huffman Coding''': ترميز هوفمان هو من إحدى تقنيات الضغط دون خسارة البيانات. يُسند هذا الترميز رموز بتات bit codes ذات أطوال مختلفة إلى محارف مختلفة. الاختيار الجشع هنا هو إسناد شيفرة الرموز الأقصر طولًا للمحارف الأكثر تكرارًا.
+
=== [[Algorithms/fractional knapsack|مسألة حقيبة الظهر المجزأة]] ===
 +
المطلوب في مسألة حقيبة الظهر المجزّأة Fractional Knapsack هو وضع مجموعة من العناصر ذات أوزان وقيم محددة في حقيبة ظهر تتسع لعدد معين من العناصر مع مراعاة الحصول على أكبر قيمة ممكنة لمجموع قيم العناصر الموجودة في الحقيبة.
  
−
يمكن استخدام نموذج الخوارزميات الجشعة في بعض الأحيان للحصول على حل تقريبي لبعض مشاكل الأمثلية الصعبة. فعلى سبيل المثال تصنف مشكلة البائع المتجول ضمن مشاكل NP-Hard. والاختيار الجشع هنا هو في التقاط أقرب مدينة غير مزورة من المدينة الحالية في كل خطوة من خطوات الحل. قد لا تعطي هذه الطريقة الحل الأمثلة في كل مرة ولكن يمكن الاستفادة منها في الوصول إلى حل مثالي تقريبًا.
+
=== [[Algorithms/egpytian fraction|مسألة الكسر المصري]] ===
 +
يمكن تمثيل أي كسر موجب كمجموع لعدد من الكسور الوحدية unit fractions الفريدة. يكون الكسر كسرًا وحديًا عندما يكون بسطه <code>1</code> ومقامه عددًا صحيحًا موجبًا، فعلى سبيل المثال يمثل الكسر <code>1/3</code> كسرًا وحديًّا. تسمى طريقة التمثيل هذه بالكسر المصري Egyptian Fraction وذلك لأنّها كانت تستخدم من قبل المصريين القدماء.
  
−
== مسألة اختيار النشاط ==
+
=== [[Algorithms/job sequencing|مسألة تسلسل الأعمال]] ===
 +
لنفترض أن لدينا مصفوفة تضمّ عددًا من الأعمال التي يرتبط كلٌّ منها بموعد للإنجاز وبمردود مالي يمكن الحصول عليه عند إتمام العمل قبل الموعد المحدد. ولنفترض أنّ كل عمل يستغرق وحدة واحدة من الزمن، وبهذا يكون أقل موعد مسموح به لإنجاز العمل هو <code>1</code>. كيف يمكن زيادة المردود المالي الكلي إن كان بالإمكان القيام بعمل واحد فقط في نفس الوقت؟
  
−
تنص مسألة اختيار النشاط Activity Selection Problem على ما يلي:
+
=== [[Algorithms/shelves fitting|مسألة ملائمة الرفوف على الحائط]] ===
 +
لو كان هناك جدار (<code>w</code>) ورفوف ذات طولين مختلفين <code>m</code> و <code>n</code>، فما هو عدد الرفوف من كلا النوعين والذي يجب استخدامه بشرط أن تكون المساحة الفارغة المتبقية قليلة قدر الإمكان.
  
−
إن كان هناك <code>n</code> من النشاطات مع أوقات بدء وانتهاء كلّ نشاط. اختر أقصى عدد ممكن من النشاطات التي يمكن لشخص واحد أن يؤديها بافتراض أنّ ذلك الشخص قادرٌ على تأدية نشاط واحدة في كل مرة.
+
=== [[Algorithms/min max product subset|إيجاد مجموعة فرعية من مصفوفة تعطي حاصل الضرب المطلوب]] ===
 +
تبحث هذه الخوارزمية عن المجموعة الفرعية ضمن مصفوفة الأعداد الصحيحة المعطاة والتي تعطي أكبر قيمة أو أصغر قيمة ممكنة لحاصل ضرب عناصر المجموعة الفرعية.
  
−
=== أمثلة ===
+
=== [[Algorithms/divide cuboid cubes|تقسيم مكعب إلى مكعبات بأقصى حجم ممكن]] ===
 +
المطلوب في هذه الخوارزمية هو تقسيم مكعب معروف الطول والعرض والارتفاع إلى أقل عدد ممكن من المكعبات بشرط أن تكون المكعبات كلها ذات حجم واحد وأن يصل مجموع أحجامها إلى أقصى قيمة ممكنة.
  
−
'''المثال الأول:''' لنفترض أن لدينا ثلاثة أنشطة مرتّبة حسب وقت الانتهاء:
+
=== [[Algorithms/partition allocation methods|طرق تعيين الأقسام في إدارة الذاكرة]] ===
 +
عند توفّر أكثر من جزء واحد شاغر لتلبية متطلبات عملية معيّنة، فيجب حينئذٍ اختيار جزء من الذاكرة، وتتطلب عملية الاختيار هذه استخدام طريقة معيّنة في حجز جزء معين من الذاكرة.
  
−
<source lang="c++">start[] = {10, 12, 20};
+
== الخوارزميات الجشعة في الرسوم البيانية ==
−
finish[] = {20, 25, 30};</source>
 
−
يمكن للشخص أن يؤدي تمرينين على الأكثر، وبهذا تكون أكبر مجموعة من التمارين التي يمكن تنفيذها من قبل شخص واحد هي <code>‎{0, 2}‎</code> (تشير الأرقام إلى موقع التمرين في المصفوفتين <code>start[]‎</code> و <code>finish[]‎</code>).
 
  
−
'''المثال الثاني: '''لنفترض أن لدينا ستة تمارين مرتّبة حسب وقت الانتهاء:
+
=== [[Algorithms/Kruskal MST|خوارزمية كروسكال للشجرة الممتدة الصغرى]] ===
 +
يتم إنشاء الشجرة الممتدة الصغرى في هذه الخوارزمية عن طريق اختيار الأضلاع واحدًا تلو الآخر. الاختيار الجشع هنا هو التقاط الضلع الذي يمتلك أصغر وزن بحيث لا يتسبب ذلك في إنشاء دائرة في الشجرة الممتدة قيد الإنشاء.
  
−
<source lang="c++">start[] = {1, 3, 0, 5, 8, 5};
+
=== [[Algorithms/Prim MST|خوارزمية برم للشجرة الممتدة الصغرى]] ===
−
finish[] = {2, 4, 6, 7, 9, 9};</source>
+
يتم إنشاء الشجرة الممتدة الصغرى في هذه الخوارزمية كذلك عن طريق اختيار الأضلاع واحدًا تلو الآخر. هناك مجموعتان في هذه الخوارزمية: الأولى هي مجموعة الرؤوس الموجودة فعلًا في الشجرة الممتدة الصغرى والثانية هي مجموعة الرؤوسة غير الموجودة في الشجرة. الاختيار الجشع هنا هو التقاط الضلع الذي يمتلك أصغر وزن والذي يربط بين المجموعتين.
−
يمكن للشخص الواحد أن يؤدي أربعة تمارين على الأكثر، وبهذا يصبح أكبر مجموعة من التمارين التي يمكن تنفيذها من قبل شخص واحد هي <code>‎{0, 1, 3, 4}‎</code>. (تشير الأرقام إلى موقع التمرين في المصفوفتين <code>start[]‎</code> و <code>finish[]‎</code>).
 
  
−
الاختيار الجشع هنا هو في التقاط النشاط التالي الذي له أقل وقت للانتهاء مقارنة بالنشاطات المتبقية، ووقت البدء بالنشاط يكون أكبر من وقت انتهاء النشاط السابق الذي تم اختياره أو يساويه. يمكن ترتيب النشاطات وفق وقت الانتهاء وبهذا يصبح النشاط التالي النشاط الذي يمتلك أقل وقت للانتهاء دائمًا.
+
=== [[Algorithms/Dijkstra|خوارزمية ديكسترا لإيجاد المسار الأقصر]] ===
−
 
+
تشبه خوارزمية ديكسترا خوارزمية برم إلى حدٍّ كبير، إذ يُبنى المسار الأقصر ضلعًا تلو الآخر، وهناك مجموعتان في هذه الخوارزمية: الأولى هي مجموعة الرؤوس الموجودة فعلًا في الشجرة الممتدة الصغرى والثانية هي مجموعة الرؤوسة غير الموجودة في الشجرة. الاختيار الجشع هنا هو انتخاب الضلع الذي يربط بين المجموعتين بشرط أن يكون على المسار الذي يمتلك أصغر وزن من المصدر إلى المجموعة التي تحتوي على الرؤوس غير المضمّنة في الشجر بعد.
−
ويمكن تلخيص الخوارزمية بالخطوات التالية:
 
−
 
 
−
# ترتيب النشاطات حسب وقت الانتهاء.
 
−
# اختيار النشاط الأول من المصفوفة ذات العناصر المرتبة وطباعته.
 
−
# إن كان وقت البدء لهذا النشاط أكبر من وقت انتهاء النشاط السابق الذي تم اختياره أو يساويه فسنختار هذا النشاط ونطبعه. (تنفذ هذه الخطوة على العناصر المتبقية في المصفوفة).
 
−
 
 
−
تعرض الشيفرات التالية طريقة تنفيذ هذه الخوارزمية في عدد من لغات البرمجة، وتفترض جميع هذه الشيفرات أنّ النشاطات مرتّبة في المصفوفات وفق وقت الانتهاء.
 
−
* C++‎:
 
−
<source lang="c++">#include<stdio.h>
 
−
 
 
−
// تطبع الدالة أكبر مجموعة من النشاطات التي يمكن لشخص واحد أن ينفذها، بشرط تنفيذ نشاط واحد في كل مرة.
 
−
// n --> العدد الكلي للنشاطات
 
−
// s[] --> مصفوفة تتضمن أوقات البدء الخاصة بكل التمارين
 
−
// f[] --> مصفوفة تتضمن أوقات الانتهاء الخاصة بكل التمارين
 
−
void printMaxActivities(int s[], int f[], int n)
 
−
{
 
−
int i, j;
 
−
 
 
−
printf ("Following activities are selected n");
 
−
 
 
−
// يتم اختيار النشاط الأوّل دائمًا
 
−
i = 0;
 
−
printf("%d ", i);
 
−
 
 
−
// المرور على بقية النشاطات
 
−
for (j = 1; j < n; j++)
 
−
{
 
−
// إن كان النشاط يمتلك وقت بدء أكبر من وقت انتهاء
 
−
    // النشاط السابق الذي تم اختياره أو يساويه
 
−
    // فسنختار هذا النشاط
 
−
if (s[j] >= f[i])
 
−
{
 
−
printf ("%d ", j);
 
−
i = j;
 
−
}
 
−
}
 
−
}
 
−
 
 
−
// اختبار الدوال السابقة
 
−
int main()
 
−
{
 
−
int s[] = {1, 3, 0, 5, 8, 5};
 
−
int f[] = {2, 4, 6, 7, 9, 9};
 
−
int n = sizeof(s)/sizeof(s[0]);
 
−
printMaxActivities(s, f, n);
 
−
return 0;
 
−
}
 
−
</source>
 
−
* بايثون:
 
−
 
 
−
<source lang="python">""" تطبع الدالة أكبر مجموعة من النشاطات التي يمكن لشخص واحد أن ينفذها، بشرط تنفيذ نشاط واحد في كل مرة."""
 
−
# n --> العدد الكلي للنشاطات
 
−
# s[] --> مصفوفة تتضمن أوقات البدء الخاصة بكل التمارين
 
−
# f[] --> مصفوفة تتضمن أوقات الانتهاء الخاصة بكل التمارين
 
−
 
 
−
def printMaxActivities(s , f ):
 
−
n = len(f)
 
−
print "The following activities are selected"
 
−
 
 
−
# يتم اختيار النشاط الأوّل دائمًا
 
−
i = 0
 
−
print i,
 
−
 
 
−
# المرور على بقية النشاطات
 
−
for j in xrange(n):
 
−
 
 
−
 
−
        # إن كان النشاط يمتلك وقت بدء أكبر من وقت انتهاء
 
−
    # النشاط السابق الذي تم اختياره أو يساويه
 
−
    # فسنختار هذا النشاط
 
−
if s[j] >= f[i]:
 
−
print j,
 
−
i = j
 
−
 
 
−
# اختبار الدوال السابقة
 
−
s = [1 , 3 , 0 , 5 , 8 , 5]
 
−
f = [2 , 4 , 6 , 7 , 9 , 9]
 
−
printMaxActivities(s , f) </source>
 
−
* جافا:
 
−
 
 
−
<source lang="java">import java.util.*;
 
−
import java.lang.*;
 
−
import java.io.*;
 
−
 
 
−
class ActivitySelection
 
−
{
 
−
// يطبع التابع أكبر مجموعة من النشاطات التي يمكن لشخص واحد أن ينفذها، بشرط تنفيذ نشاط واحد في كل مرة.
 
−
// n --> العدد الكلي للنشاطات
 
−
// s[] --> مصفوفة تتضمن أوقات البدء الخاصة بكل التمارين
 
−
// f[] --> مصفوفة تتضمن أوقات الانتهاء الخاصة بكل التمارين
 
−
public static void printMaxActivities(int s[], int f[], int n)
 
−
{
 
−
int i, j;
 
−
 
−
System.out.print("Following activities are selected : n");
 
−
 
−
// يتم اختيار النشاط الأول دائمًا
 
−
i = 0;
 
−
System.out.print(i+" ");
 
−
 
−
// المرور على بقية العناصر
 
−
for (j = 1; j < n; j++)
 
−
{
 
−
// إن كان النشاط يمتلك وقت بدء أكبر من وقت انتهاء
 
−
    // النشاط السابق الذي تم اختياره أو يساويه
 
−
    // فسنختار هذا النشاط
 
−
 
 
−
if (s[j] >= f[i])
 
−
{
 
−
System.out.print(j+" ");
 
−
i = j;
 
−
}
 
−
}
 
−
}
 
−
 
−
// اختبار التوابع السابقة
 
−
public static void main(String[] args)
 
−
{
 
−
int s[] = {1, 3, 0, 5, 8, 5};
 
−
int f[] = {2, 4, 6, 7, 9, 9};
 
−
int n = s.length;
 
−
 
−
printMaxActivities(s, f, n);
 
−
}
 
−
 
−
} </source>
 
−
تعطي الشيفرات السابقة المخرجات التالية:
 
−
 
 
−
<source lang="text">Following activities are selected
 
−
0 1 3 4</source>
 
−
لنفترض أنّ لدينا مجموعة الأنشطة التالية <code>S={1, 2, 3, …n}</code>‎ وأنّ هذه الأنشطة مرتّبة حسب وقت انتهائها. الاختيار الجشع هنا هو التقاط النشاط الأول دائمًا، لأنّه الحل المثالي دائمًا مهما كانت محتويات المجموعة. ويمكن أن نبرهن على ذلك بإثبات أنّه في حال وجود الحل <code>B</code> إضافة إلى النشاط الأول، فسيكون هناك حلّ آخر هو الحل <code>A</code> وبالحجم نفسه مع النشاط <code>1</code> ليكون هو النشاط الأول. ولو افترضنا أنّ الحل <code>B</code> هو <code>k</code> فإن المجموعة <code>A</code> ستكون موجودة دائمًا ويمكن التعبير عنها بالعلاقة ‎<code><nowiki>A = {B - {k}} U {1}</nowiki></code>‎ (لاحظ أنّ النشاطات في المجموعة <code>B</code> مستقلة عن بعضها البعض وأنّ النشاط k يمتلك أقل وقت انتهاء من بين جميع النشاطات، ولما لم تكن قيمة <code>k</code> هي <code>1</code> فإنّ <code>finish(k) >= finish(1)‎</code>.
 
−
 
 
−
== التعقيد الزمني: ==
 
−
 
 
−
قد يبلغ التعقيد الزمني <code>O(n log n)</code>‎ إن لم يكن بالإمكان ترتيب النشاطات، أما إن كانت النشاطات مرتّبة دائمًا فإن التعقيد الزمني يبلغ <code>O(n)‎</code>.
 
  
 +
=== [[Algorithms/Boruvka MST|خوارزمية بوروفكا]] ===
 +
تعدّ خوارزمية بوروفكا أقدم خوارزمية لإيجاد الشجرة الممتدة الصغرى وقد وضعها بوروفكا سنة 1926م، قبل اختراع الحواسيب بفترة طويلة، وقد نشرت هذه الخوارزمية كطريقة لبناء شبكة فعّالة من التمديدات الكهربائية.
 
[[تصنيف: الخوارزميات]]
 
[[تصنيف: الخوارزميات]]
 
[[تصنيف: الخوارزميات الجشعة]]
 
[[تصنيف: الخوارزميات الجشعة]]

المراجعة الحالية بتاريخ 18:01، 24 ديسمبر 2019

الخوارزميات الجشعة هي إحدى أساليب الخوارزميات 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م، قبل اختراع الحواسيب بفترة طويلة، وقد نشرت هذه الخوارزمية كطريقة لبناء شبكة فعّالة من التمديدات الكهربائية.

مجلوبة من "https://wiki.hsoub.com/index.php?title=Algorithms/Greedy_Algorithms&oldid=29554"