Branch and bound — طريقة الفروع والحدود

طريقة الفروع والحدود (بالإنجليزية: Branch and Bound، وتُختصر إلى B&B أو BnB) هي نموذج عام لبناء خوارزميات دقيقة لحل مسائل التحسين المتقطع والتحسين التوافقي، وخاصة المسائل من فئة NP-صعبة^[1]. تمثل هذه الطريقة استراتيجية بحث شامل موجه، حيث يتم تقسيم مجموعة الحلول الممكنة بأكملها بشكل متسلسل إلى مجموعات فرعية (التفريع)، ويتم حساب تقديرات (حدود) لقيمة الدالة الهدف لكل منها. تتيح هذه التقديرات استبعاد (تشذيب) المجموعات الفرعية التي من المؤكد أنها لا تحتوي على حلول مثلى، مما يقلل بشكل كبير من فضاء البحث^[2].

اقترح هذه الطريقة لأول مرة أ. لاند و أ. دويغ في عام 1960 لحل مسائل البرمجة الصحيحة^[3]. ومنذ ذلك الحين، أصبحت واحدة من أهم المنهجيات الأساسية في بحوث العمليات وعلوم الحاسوب. السمة الرئيسية للطريقة هي مرونتها: فهي ليست خوارزمية محددة، بل هي مخطط استراتيجي عالي المستوى (إطار عمل) يمكن تكييفه مع بنية المسألة المراد حلها.

المكونات الرئيسية للطريقة

ترتكز الطريقة على ثلاث عمليات أساسية تُطبق على المجموعات الفرعية لفضاء الحلول، والتي يتم تنظيمها على شكل شجرة بحث.

التفريع (بالإنجليزية: Branching) — هي عملية تقسيم مجموعة الحلول الممكنة الحالية $S_{i}$ بشكل تعاودي إلى عدة مجموعات فرعية أصغر، وعادة ما تكون غير متقاطعة $S_{i 1}, S_{i 2}, \dots, S_{i k}$ . كل مجموعة فرعية من هذه المجموعات تقابل مسألة فرعية جديدة وتُمثل كعقدة ابن في شجرة البحث. على سبيل المثال، في مسائل البرمجة الصحيحة، غالبًا ما يتم التفريع بناءً على متغير له قيمة كسرية في حل الاسترخاء الخطي (LP-relaxation).

تقدير الحدود (بالإنجليزية: Bounding) — لكل عقدة في شجرة البحث (أي لكل مسألة فرعية)، يتم حساب تقدير لقيمة الدالة الهدف. بالنسبة لمسألة تصغير (minimization)، يكون هذا التقدير هو الحد الأدنى (lower bound)، وهو تقدير مضمون للقيمة الدنيا لأي حل ضمن هذه المجموعة الفرعية. في أغلب الأحيان، يتم الحصول على هذا التقدير عن طريق حل استرخاء (relaxation) للمسألة الفرعية الأصلية — وهي نسخة مبسطة يتم فيها تجاهل بعض القيود المعقدة مؤقتًا (مثل قيود الأعداد الصحيحة). النوع الأكثر شيوعًا هو الاسترخاء الخطي.

التشذيب (بالإنجليزية: Pruning) — هي عملية استبعاد العقد (والأشجار الفرعية الكاملة المرتبطة بها) من البحث، والتي من المؤكد أنها لا يمكن أن تحتوي على الحل الأمثل. يتم تشذيب العقدة في إحدى الحالات التالية:

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

الخوارزمية العامة

يمكن وصف الخوارزمية العامة لطريقة الفروع والحدود لمسألة تصغير (minimization) بالخطوات التالية:

التهيئة: إيجاد حل أولي ممكن (باستخدام استدلال ما، على سبيل المثال) وتعيين قيمته كحد أعلى أولي (الحل الحالي الأفضل) $U$ . إنشاء قائمة انتظار للعقد النشطة $Q$ تحتوي على العقدة الجذر (المسألة الأصلية).
الحلقة الرئيسية: طالما أن قائمة الانتظار Q ليست فارغة:
- اختر عقدة من $Q$ وفقًا لاستراتيجية البحث (مثل البحث بالعمق أولاً أو البحث حسب أفضل تقدير).
- قم بحل الاسترخاء لهذه العقدة للحصول على الحد الأدنى $L$ .
- قم بتشذيب العقدة إذا كان $L \geq U$ .
- إذا كان حل الاسترخاء ممكنًا للمسألة الأصلية، قم بتحديث الحل الحالي الأفضل: $U \leftarrow L$ .
- إذا لم يتم تشذيب العقدة وكان الحل غير ممكن، قم بتنفيذ عملية التفريع بتقسيمها إلى عقد أبناء وإضافتها إلى قائمة الانتظار $Q$ .
الإنهاء: عندما تصبح قائمة الانتظار $Q$ فارغة، تنتهي الخوارزمية. الحل الذي تم العثور عليه، والذي يقابل الحل الحالي الأفضل $U$ ، هو الحل الأمثل العالمي.

الخصائص والنظريات الرئيسية

الصحة والتقارب: تضمن الخوارزمية العثور على الحل الأمثل العالمي في عدد محدود من الخطوات، بشرط أن تكون مجموعة الحلول الممكنة محدودة، وأن تكون عملية التفريع متقاربة (أي أن المجموعات الفرعية عند تقسيمها بشكل تعاودي "تتقلص" نحو نقاط محددة)^[4].
استراتيجية البحث: تعتمد كفاءة الخوارزمية بشكل كبير على استراتيجية اختيار العقدة التالية للتفريع (مثل البحث بالعمق أولاً، أو البحث بالعرض أولاً، أو البحث حسب أفضل تقدير) وعلى اختيار المتغير الذي سيتم التفريع بناءً عليه. غالبًا ما تستخدم برامج الحل الحديثة استراتيجيات هجينة^[5].

أمثلة

مسألة البرمجة الصحيحة: تطبيق كلاسيكي للطريقة. يتم استخدام البرمجة الخطية كاسترخاء. يحدث التفريع بناءً على متغير كسري $x_{j}$ ، مما ينشئ مسألتين فرعيتين مع قيود إضافية: $x_{j} \leq ⌊ x_{j}^{*} ⌋$ و $x_{j} \geq ⌈ x_{j}^{*} ⌉$ .
مسألة البائع المتجول: فضاء الحلول هو جميع الدورات الهاملتونية الممكنة في الرسم البياني. يمكن أن يتم التفريع بناءً على الأضلاع (تضمين/استبعاد ضلع من المسار). يمكن استخدام حلول المسائل الأبسط كحدود دنيا، مثل مسألة التعيين أو بناء شجرة الامتداد الأصغر^[6].

مفاهيم وتطبيقات ذات صلة

طريقة الفروع والقطع (Branch-and-Cut): طريقة هجينة تجمع بين B&B وطريقة المستويات القاطعة. عند كل عقدة في شجرة البحث، بالإضافة إلى حل الاسترخاء، يتم إنشاء متباينات إضافية (قواطع) تعمل على تقوية الحد الأدنى، مما يؤدي إلى تشذيب أكثر كفاءة للفروع.
البحث مع التراجع (Backtracking): يمكن اعتبار طريقة الفروع والحدود تعميمًا لهذه الخوارزمية لمسائل التحسين.
تقليم ألفا-بيتا: مفهوم مشابه يستخدم في أشجار الألعاب لتشذيب الفروع الخاسرة بشكل مؤكد.

انظر أيضًا

البرمجة الصحيحة
التحسين التوافقي
مسألة البائع المتجول
مسألة NP-صعبة
طريقة سيمبلكس

المراجع

↑ Wikipedia contributors. (2025). Branch and bound. In Wikipedia, The Free Encyclopedia. Retrieved 2025-10-26, from https://en.wikipedia.org/wiki/Branch_and_bound
↑ Wikipedia contributors. (2023). Метод ветвей и границ. In Русская Википедия. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ
↑ Land, A. H.; Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520. DOI: 10.2307/1910129. URL: https://www.jstor.org/stable/1910129
↑ Conitzer, V. (2008). Solving (mixed) integer programs using branch and bound. Duke University, Department of Computer Science. URL: https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf
↑ Maudet, G.; Danoy, G. (2024). Search Strategy Generation for Branch and Bound Using Genetic Programming. arXiv preprint arXiv:2412.09444. DOI: 10.48550/arXiv.2412.09444. URL: https://arxiv.org/abs/2412.09444
↑ Little, J. D. C.; Murty, K. G.; Sweeney, D. W.; Karel, C. (1963). An Algorithm for the Traveling Salesman Problem. Operations Research, 11(6), 972–989. DOI: 10.1287/opre.11.6.972. URL: https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf

[en-wiki-bnb-1] Wikipedia contributors. (2025). Branch and bound. In Wikipedia, The Free Encyclopedia. Retrieved 2025-10-26, from https://en.wikipedia.org/wiki/Branch_and_bound

[ru-wiki-bnb-2] Wikipedia contributors. (2023). Метод ветвей и границ. In Русская Википедия. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ

[land-doig-1960-3] Land, A. H.; Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520. DOI: 10.2307/1910129. URL: https://www.jstor.org/stable/1910129

[conitzer-duke-4] Conitzer, V. (2008). Solving (mixed) integer programs using branch and bound. Duke University, Department of Computer Science. URL: https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf

[maudet-danoy-2024-5] Maudet, G.; Danoy, G. (2024). Search Strategy Generation for Branch and Bound Using Genetic Programming. arXiv preprint arXiv:2412.09444. DOI: 10.48550/arXiv.2412.09444. URL: https://arxiv.org/abs/2412.09444

[little-1963-6] Little, J. D. C.; Murty, K. G.; Sweeney, D. W.; Karel, C. (1963). An Algorithm for the Traveling Salesman Problem. Operations Research, 11(6), 972–989. DOI: 10.1287/opre.11.6.972. URL: https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf

[1]

[2]

[3]

[4]

[5]

[6]

Branch and bound — طريقة الفروع والحدود

Contents

المكونات الرئيسية للطريقة

الخوارزمية العامة

الخصائص والنظريات الرئيسية

أمثلة

مفاهيم وتطبيقات ذات صلة

انظر أيضًا

المراجع

Navigation menu

Branch and bound — طريقة الفروع والحدود

المكونات الرئيسية للطريقة

الخوارزمية العامة

الخصائص والنظريات الرئيسية

أمثلة

مفاهيم وتطبيقات ذات صلة

انظر أيضًا

المراجع

Navigation menu

Search