خوارزميات

الخوارزميات الجشعة بلغة البسطاء

شرح مُبسط لخوارزميات السهل الممتنع : الخوارزميات الجشعة ( greedy algorithms ) .

الخوارزميات الجشعة ( greedy algorithms ) هي عبارة عن برادايم برمجي يهدف إلى حل مشكلة معينة عبر تقسيمها إلى مراحل ، واختيار الحل اﻷمثل محلياً في كل مرحلة من أجل الوصول إلى الحل الأمثل والعام لكامل المشكلة .

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

في الرياضيات تواجهنا مجموعة من المسائل الشائكة تسمى مشاكل الاستمثال أو مشاكل التحسين ( optimization problems ) ، وهي مسائل تتطلب اختيار الحل الأمثل لمشكلة معينة ضمن فضاءٍ من الحلول الممكنة .

أشهر تقنيات التحسين في الذكاء الإصطناعي : Adam optimizer, momentum, gradient descent .

الطريقة البديهية والأشهر لحل مشاكل الاستمثال هي اختبار كل الخيارات الممكنة ، وكلما حصلنا على حل جديد نقارنه مع الحلول السابقة ، ثم نقوم بحفظه إن كان أمثل من السابق ، هذا هو ما يسمى المقاربة الجشعة (greedy approach) ، وسُميت جشعة لأنها تعتمد حلًا فوريًا محسَّنًا في كل خطوة ( localized optimum solution ) دون النظر إلى الحل الأمثل العام للمشكلة ( globally optimized solution ) . ولهذا السبب تستخدم في بناء نماذج الذكاء الصنعي .

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

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

مسألة العملات المعدنية :

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

  • 1 ,  2 , 5 , 10 , 20 , 50 , 100 , 500 .

مثلاً لو طُلب منك مبلغ 1453 سيكون الناتج :

 2 عملة من فئة 500 .

 1 عملة من فئة 400 .

 1 عملة من فئة 50 .

 1 عملة من فئة 2 .

 1 عملة من فئة 1 .

خطوات حل المسألة

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

  1.  قم بإنشاء قائمة فارغة لحفظ النتائج وسمِّها result وقم بتعريف متغير جديد بقيمة المبلغ المطلوب وسمّه value
  2.  إبحث عن أعلى فئة في صندوق العملات والتي قيمتها أصغر من value .
  3.  أضف هذه الفئة إلى القائمة result ثم اطرح قيمتها من value .
  4.  إذا أصبحت قيمة value == 0 توقف واطبع النتيجة result .
  5.  إذا كانت قيمة value أكبر من صفر : أعد من الأول .

مخطط الخورزمية :

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

الكود ( بايثون 3 ) :

def greedy_coins(Value):
    coins = [1, 2, 5, 10, 20, 50,100, 500 ] 
    n = len(coins) - 1
    result = []
    
    while n >= 0 :
        while Value >= coins[n]:    
            Value -= coins[n]
            result.append(coins[n])
        n -= 1
    return (result)

شرح الكود بالتفصيل :

  • في السطر (1) عرّفنا الدالة greedy_coins التي تقبل متغيراً واحداً هو Value ، هذا المتغير سيمثل المبلغ المطلوب .
  • (2) : عرّفنا جميع الفئات المعدنية ضمن القائمة coins .
  • (3) :  عرّفنا المتغير n الذي يمثل عدد الفئات (قمنا بطرح 1 لأن العد في الحلقات يبدأ من الصفر) .
  • (4) : عرّفنا القائمة result (قائمة فارغة) .
  • (6) : بدأنا حلقة التكرار while التي ستقوم بتكرار نفسها مادامت قيمة المتغير n تساوي أو أكبر من 0 .
  • (7) : بدأنا حلقة تكرار أخرى داخل الحلقة السابقة ، ستقوم بتكرار نفسها مادامت قيمة الفئة المعدنية الحالية [coins[n أصغر من المبلغ Value ، وفي داخل هذه الحلقة إذا تحقق الشرط ستقوم بالتالي :
    •  طرح قيمة العملة coins[n] من قيمة المبلغ Value (السطر 8 ).
    •  إضافة العملة coins[n] إلى القائمة result (السطر 9 ) .
  • (10) : طرحنا 1 من متغير التكرار n .
  • (11) : استخدمنا التعليمة return لإرجاع قيمة المتغير result من الدالة greedy_coins .

الآن إنتهينا من الدالة ، وحان وقت تجربتها ولنفترض أن المبلغ هو 1456:

print( greedy_coins(1654) )

النتيجة :

[500, 500, 500, 100, 50, 2, 2]

 

أشهر تطبيق للخوارزمية الجشعة : مسألة البائع المتجول

مسألة البائع المتجول ( travelling salesman )

تعتبر مسألة البائع المتجول من أهم المسائل في علم التعقيد الحسابي ، ونصها : ذهب تاجر إلى دولة فيها n مدينة ، ويريد أن يزور كل مدينة في الدولة مرة واحدة فقط وبأقل وقت سفر بين المدن .

رغم أن صيغة المشكلة تبدو بسيطة ، إلا أن الحل صعب جدا, فكلما زاد عدد المدن زادت صعوبة المشكل: يحتاج الحاسوب إلى حوالي قرنين من الزمن لإيجاد أقصر مسار يمر على 100 مدينة !

إذن فهذه المسألة تم تصنيفها ضمن المسائل الرياضية الشديدة الصعوبة ،  و بعبارة أدق تم تصنيفها ضمن المشاكل الحدودية غير المحددة الكاملة (NP-complet) .

هذه المسألة إلى اليوم لا يوجد لها أي حل ناجح في كل الحالات باستثناء خوارزمية كريستوفيدس ( Christofides algorithm ) التي وصلت إلى نسبة تقريب 3/2 من الحلول المحسنة (optimal solutions) ، وتعتبر خوارزمية كريستوفيدس من الخوارزميات الجشعة التي تطبق على نظرية المخططات ( Graph theory ) .

 

أسماء أخرى للخوارزميات الجشعة :

  • الخوارزميات الطماعة : هو الإسم الذي اختاره د.محمد عمر الحوارات أستاذ وباحث في علوم الحاسب –  جامعة الأمير سطّام بن عبدالعزيز (السعودية) ، و د.احمد خلفة عبيد العجيلي من جامعة بابل ( العراق ) .
  • الخوارميات الطموحة : هذه الترجمة اختارتها جامعة دمشق ومجموعة من كليات علوم الحاسب بالشام  .

مغالطات شائعة بخصوص إسم الخوارزمية الجشعة :

  • الخوارزميات الديناميكية (Dynamic Programming ) : هناك فئة كثيرة من المبرمجين تخلط بين البرمجة الدينامية والمقاربة الجشعة ، الفرق بينهما يكمن في كون الخوارزمية الديناميكية تقسم المشكلة إلى مجموعة من المشاكل الصغيرة ، والخوارزمية الجشعة تقسم المشكلة إلى مراحل زمنية تسمى ( stages ) .
  • الخوارزمية الجينية ( Genetic Algorithm ): هي خوارزمية تحسين في الأصل، تقوم على مبدأ البقاء للحل الأصلح ولها مجموعة من القواعد والأساسات ، وهي تختلف كثيراً عن الخورزمية الجشعة في مسألة أنها تدمج وتولد الحلول وتركز على لحل الأمثل العام للمشكلة ( globally optimized solution ) .

وصلنا إلى نهاية المقال ، شاركونا بآرائكم وتجاربكم عبر التعليقات .

 

الوسوم

محمد هشوم

مبرمج عربي ، مهتم بالذكاء الصنعي وخبير بيانات .. ومدون !

‫4 تعليقات

  1. مقال واضح و بسيط..وغني أيضا.
    في حل مشكلة العملات النقدية ،يبدو أن السطور التالية :
    while Value >= coins[n]:
    Value -= coins[n]
    result.append(coins[n])
    هي التي تعبر عن جشع الخوارزمية.

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

زر الذهاب إلى الأعلى
إغلاق
إغلاق