ما هو Branch and Bound؟ شرح مبسّط لأسلوب التفريع والتقييد في الخوارزميات
Branch and Bound (التفريع والتقييد) هو أسلوب لحل مسائل التحسين — أي المسائل التي تبحث فيها عن أفضل حل ممكن (أقل تكلفة أو أعلى ربح) وسط عدد هائل من الاحتمالات، بدلًا من مجرد فحصها كلها واحدًا واحدًا. الفكرة الجوهرية بسيطة: بدل تجربة كل الحلول الممكنة (وهو ما قد يستغرق زمنًا هائلًا)، نبني "شجرة" من القرارات، ونحسب لكل فرع فيها تقديرًا لأفضل نتيجة يمكن أن يصل إليها. فإذا كان هذا التقدير أسوأ من حلٍّ جيد نملكه بالفعل، نقطع الفرع بالكامل دون أن نكمل استكشافه. هذا "القطع" (Pruning) هو سرّ كفاءة الأسلوب.
كيف يعمل الأسلوب فعليًا؟
يقوم Branch and Bound على ثلاث ركائز متكررة:
- التفريع (Branching): نقسّم المسألة إلى مسائل فرعية أصغر. في مسألة تعتمد على قرارات ثنائية مثلًا (نأخذ عنصرًا أو لا نأخذه)، كل عقدة في الشجرة تتفرّع إلى احتمالين.
- التقييد (Bounding): لكل عقدة نحسب حدًّا (Bound) — وهو تقدير متفائل لأفضل نتيجة يمكن بلوغها من هذا الفرع. في مسائل التصغير (minimization) يكون هذا حدًّا أدنى (lower bound)، وفي مسائل التكبير (maximization) يكون حدًّا أعلى (upper bound).
- القطع (Pruning): نحتفظ دائمًا بأفضل حل كامل وصلنا إليه حتى الآن، ونسمّيه الحل الحالي (incumbent). أي فرع يكون حدّه أسوأ من هذا الحل الحالي يُستبعَد فورًا، لأنه لا يحمل أمل تحسين.
الفكرة الحاسمة هي أن الحدّ يجب أن يكون متفائلًا لكنه صادق: يبالغ في تقدير الأفضل الممكن دون أن يقلّ عنه أبدًا. لو أعطى الحدّ تقديرًا مبالغًا في التفاؤل بشكل خاطئ، فقد نقطع فرعًا يحوي الحل الأمثل ونفقده.
ترتيب استكشاف الشجرة
لا يفرض الأسلوب طريقة واحدة للتنقّل في الشجرة، وهنا يكمن جزء كبير من الأداء:
- البحث بالعمق أولًا (DFS): يصل بسرعة إلى حلّ كامل يصبح مرجعًا للقطع، ويستهلك ذاكرة قليلة.
- الأفضل أولًا (Best-First): يستخدم طابور أولوية (priority queue) يختار دائمًا العقدة صاحبة الحدّ الأكثر وعدًا. غالبًا يصل إلى الحل الأمثل بأقل عدد من العقد، لكنه يحتاج ذاكرة أكبر.
في التطبيقات الحقيقية يُمزج الأسلوبان لموازنة السرعة والذاكرة.
مثال محلول: مشكلة الحقيبة (0/1 Knapsack)
لديك حقيبة تتحمّل وزنًا محددًا، ومجموعة أشياء لكلٍّ منها وزن وقيمة، والهدف تعظيم القيمة دون تجاوز الوزن. مع Branch and Bound:
- نرتّب الأشياء تنازليًا حسب نسبة القيمة إلى الوزن.
- عند كل عقدة نقرّر: نأخذ الشيء الحالي أو نتركه (تفريع).
- نحسب الحدّ الأعلى بافتراض أننا نستطيع ملء ما تبقّى من سعة الحقيبة "كسريًا" بأفضل الأشياء المتبقية — وهذا تقدير متفائل لأنه يتجاهل قيد أن كل شيء يُؤخذ كاملًا أو يُترك.
- أي فرع حدّه الأعلى أقل من أفضل قيمة كاملة وجدناها يُقطَع.
النتيجة: نتفادى استكشاف الغالبية العظمى من التركيبات الممكنة البالغة عددها 2 مرفوعة لعدد الأشياء.
Branch and Bound أم Backtracking؟
يخلط كثيرون بينهما لأن كليهما يبني شجرة ويقطع فروعًا، لكن الفرق جوهري:
| الجانب | Backtracking (التتبّع العكسي) | Branch and Bound (التفريع والتقييد) |
|---|---|---|
| نوع المسألة | إيجاد أي حل صالح أو كل الحلول | إيجاد الحل الأمثل |
| سبب القطع | الفرع غير صالح (يخالف قيدًا) | الفرع صالح لكنه لن يتفوّق على الحل الحالي |
| أداة القطع | شرط الصلاحية | دالة الحدّ (Bound) |
| ترتيب البحث | عمق أولًا عادةً | عمق/أفضل أولًا حسب طابور أولوية |
| مثال نمطي | مسألة الملكات الثماني، Sudoku | البائع المتجول، الحقيبة، الجدولة |
باختصار: Backtracking يسأل «هل هذا الفرع ممكن؟»، بينما Branch and Bound يسأل «هل يستحق هذا الفرع أن أكمله من الأساس؟».
تطبيقات شائعة
- مشكلة البائع المتجول (TSP): إيجاد أقصر مسار يمرّ بمجموعة مدن ويعود لنقطة البداية.
- البرمجة الخطية الصحيحة (Integer Linear Programming): حيث تُحل النسخة المخفّفة أولًا ثم يُفرّع على المتغيرات الكسرية — وهذا جوهر مُحلِّلات مثل CBC وGurobi.
- مسائل الجدولة والتخصيص: توزيع مهام على آلات أو موظفين بأقل زمن أو تكلفة.
ملاحظة عملية وخطأ شائع
جودة دالة الحدّ تحدّد كل شيء. حدّ فضفاض جدًّا (متفائل بإفراط) يقطع فروعًا قليلة، فيقترب أداء الخوارزمية من البحث الشامل البطيء. وحدّ ضيّق ودقيق يقطع مبكرًا وبكثرة فيتسارع الحل. القاعدة العملية: استثمر وقتك في تصميم حدٍّ ذكي أكثر من قلقك على بنية الشجرة.
الخطأ الأكثر شيوعًا لدى المبتدئين هو حساب حدٍّ متشائم عن طريق الخطأ (أقل من الأفضل الممكن في مسألة تكبير)، ما يؤدي إلى قطع فرع يحوي الحل الأمثل. تذكّر دائمًا: الحدّ يجب أن يكون في صف «أفضل مما يمكن تحقيقه فعلًا»، لا العكس.
الأسئلة الشائعة
هل Branch and Bound يضمن الحل الأمثل دائمًا؟ نعم، ما دامت دالة الحدّ صحيحة (لا تقطع فرعًا يحوي الأمثل). الأسلوب دقيق (exact) وليس تقريبيًا، لكنه في أسوأ الحالات قد يقترب من التعقيد الأسّي.
ما الفرق بينه وبين البرمجة الديناميكية؟ البرمجة الديناميكية تعيد استخدام حلول مسائل فرعية متداخلة ومتكرّرة، بينما Branch and Bound يستكشف فضاء بحث شجريًّا ويقطع الأجزاء غير الواعدة. بعض المسائل مثل الحقيبة يمكن حلّها بالطريقتين، لكنّ الأنسب يعتمد على حجم المدخلات وطبيعة القيود.
هل هو أسرع من البحث الشامل (Brute Force) دائمًا؟ في المتوسط نعم بفارق كبير بفضل القطع، لكنه لا يحسّن التعقيد الأسوأ نظريًّا؛ قوته في تجنّب الجزء الأكبر من الحسابات عمليًّا.
هل أحتاج طابور أولوية لتطبيقه؟ لا، يمكن تطبيقه بالعمق أولًا باستخدام مكدّس بسيط. طابور الأولوية (Best-First) مفيد حين تريد الوصول للحل الأمثل بأقل عدد عقد، مقابل استهلاك ذاكرة أعلى.