خوارزميات شرهة فعّالة

مقدّمة

تُعَدّ الخوارزميات الشرهة (‎Greedy Algorithms‎) من الأدوات الأساسية في صندوق عدّة الباحث والممارس في علوم الحاسوب وهندسة البرمجيات. تقوم فكرتها المحورية على اتّخاذ قرارٍ محلّي يبدو «الأفضل» لحظيًّا، على أمل أن يؤدّي تتابع هذه القرارات إلى حلّ عامٍّ مثالي أو قريب من المثالي للمشكلة المطروحة. برغم بساطة المبدأ، فقد أثبتت الخوارزميات الشرهة قدرتها على حلّ طيفٍ واسع من المسائل بفعاليّة زمنيّة وذاكرويّة عالية، ما يجعلها خيارًا مُفضّلًا في التطبيقات التي تتطلّب استجابة سريعة أو تعمل على موارد محدودة.

أصل التسمية والبنية العامة

يرجع مصطلح «شرِهة» إلى النزعة الواضحة لهذا النوع من الخوارزميات لاقتناص أفضل خيار متاح في كلّ خطوة دون النظر بعيدًا إلى العواقب البعيدة المدى. على الصعيد البنيوي، تتكوّن أيّ خوارزمية شرهة من العناصر الآتية:

1. مجموع مرشّح للحالات – تمثيل للمشكلة على هيئة حالات ينتقل الخوارزم من إحداها إلى الأخرى.

2. دالّة اختيار محلي – معيارٌ يُقَيِّم الخيارات المتاحة ويُعطي درجة «أفضلية» لكلٍّ منها.

3. خاصيّة التقلّص‎ (Feasibility)‎ – اختبار يُحدِّد إنْ كان الانتقال المقترح يقع ضمن نطاق الحلول الممكنة.

4. قاعدة الإنهاء – شرطٌ يحدد متى ينتهي الخوارزم بإنتاج مخرجاته أو إعلان فشله.

تفضي هذه العناصر إلى خوارزمية سهلة الصياغة، واضحة التنفيذ، قليلة المتطلّبات الذاكروية، وغالبًا ذات تعقيد زمني أخذ الشكل ‎$O(n \log n)$‎ أو ‎$O(n)$‎ في أصعب الحالات.

المرتكزات النظرية لصحة الخوارزميات الشرهة

لا تنجح الخوارزميات الشرهة في جميع المعضلات، إذ يتوقّف نجاحها على تحقّق شرطين نظريّين جوهريّين:

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

أشهر المسائل القابلة للحل بالأسلوب الشره

1. جدولة الأنشطة ‎(Activity Selection)‎

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

2. مسألة الشجرة الممتدة الأدنى ‎(Minimum Spanning Tree)‎

يُستخدَم خوارزما ‎Kruskal‎ وخوارزما ‎Prim‎، وكلاهما من النمط الشره. يختار ‎Kruskal‎، مثلًا، أصغر حافة متاحة لا تكوّن دورةً مع الحواف المختارة. إثبات المثالية يستند إلى مبرهنة القطع (Cut Property) التي تضمن أنّ أصغر حافة تقطع أيّ فصل للمكونات الجزئية لا بدّ أن تنتمي إلى شجرةٍ ممتدّة أدنى.

3. الترميز المثالي لهَفمان ‎(Huffman Coding)‎

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

4. مشكلة التغيير النقدي ‎(Coin Change)‎ لفئات نقود استثنائية

في أنظمة العملة «القياسية» (1، 5، 10، 25 مثلًا)، يكفل الأسلوب الشره بإعطاء أقل عدد قطع، لأنّ بنية الفئات تفي بشرط الترتيب الشره. بالمقابل، قد يفشل إذا كانت الفئات غير متوافقة، كمجموعة {1، 3، 4} لتكوين 6 وحدات؛ إذ يعطي الاختيار الشره (4 + 1 + 1) بثلاث قطع بينما الأمثل (3 + 3) بقطعتين.

تنفيذ نموذجي: بناء شجرة شفرة هَفمان

python
CopyEdit
import heapq
from collections import Counter, namedtuple

Node = namedtuple('Node', ['weight', 'symbol', 'left', 'right'])

def build_huffman_tree(data: str) -> Node:
    # حساب تواترات الرموز
    freq = Counter(data)
    heap = [Node(w, s, None, None) for s, w in freq.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        n1 = heapq.heappop(heap)
        n2 = heapq.heappop(heap)
        merged = Node(n1.weight + n2.weight, None, n1, n2)
        heapq.heappush(heap, merged)

    return heap[0]

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

تحليل التعقيد

حدود الخوارزميات الشرهة واستراتيجيات التحسين

1. فشل المثالية في غياب خاصية البنية المثلى
   
      تُعالَج بالتحوّل إلى البرمجة الديناميكية أو التحسين المقيّد (Branch and Bound).

2. التشعّب الزائف في حالات خاصّة
   
      يمكن الحدّ منه بتقنيات تشذيب مثل «مبدأ الحواف المتطابقة» في ‎Kruskal‎.

3. عدم التكيّف مع الأوزان السالبة أو المُعتمة
   
      تستلزم هذه الحالات خوارزميات بديلة كـ ‎Bellman‑Ford‎ للمسارات الأقصر.

تطبيقات عملية في البرمجيات المعاصرة

• مديري التحميل (Download Managers): تقسيم الملفات إلى شرائح وتحميل الشريحة الأسرع استنادًا إلى عرض النطاق الحالي.

• أنظمة الملاحة الآنيّة: اختيار أسرع مسار لحظي وتحديثه عند تغيّر حركة المرور.

• خدمات البثّ التكيّفي (Adaptive Streaming): اختيار جودة الفيديو المثلى بناءً على سرعة الاتصال لحظيًّا.

تأثير الخوارزميات الشرهة في تصميم واجهات برمجيّة

يدفع طابعها الحَدَثي المعتمد على قرار لحظي إلى اعتماد بنى متدفّقة (Stream Processing) حيث تُعالَج البيانات بالتتابع دون تخزينها كاملًا. هذا ينسجم مع مبادئ البرمجة التفاعلية التي تفضّل استهلاك الموارد «على قَدْر الحاجة».

خاتمة

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

المراجع

1. ‎Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C.‎ (2009). Introduction to Algorithms (3rd ed.). MIT Press.

2. ‎Kleinberg, J., & Tardos, É.‎ (2005). Algorithm Design. Pearson.