التراجع (Backtracking) والتفرع والتحديد (Branch and Bound)

التراجع والتفرع والتحديد هما نموذجان منهجيان للبحث يستكشفان فضاء الحلول المرشحة كشجرة، ويقومان بتقليم الأشجار الفرعية التي لا يمكن أن تؤدي إلى حل صالح أو أمثل لجعل عمليات البحث التي قد تكون أسية قابلة للتطبيق عمليًا.

Definition

التراجع هو بحث في العمق لشجرة الحلول المرشحة الجزئية يقوم بتقليم الفرع في اللحظة التي لا يمكن فيها إكمال المرشح الجزئي إلى حل صالح؛ ويعزز التفرع والتحديد هذا بحدود رقمية على الهدف بحيث يتم التخلص من الفروع التي لا يمكن لأفضل قيمة ممكنة لها أن تتجاوز الحل الحالي.

Scope

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

Core questions

• كيف يتم نمذجة فضاء حل المشكلة كشجرة بحث للتخصيصات الجزئية؟
• ما هي فحوصات القيود التي تسمح للتراجع بتقليم الفروع غير المجدية مبكرًا؟
• كيف يتم حساب الحدود الدنيا والعليا لتقليم الفروع في التحسين؟
• كيف يؤثر ترتيب التفرع والتحديد على الأداء العملي؟
• لماذا تُستخدم هذه الأساليب للمشكلات الصعبة من نوع NP على الرغم من أسوأ الحالات الأسية؟

Key concepts

• شجرة البحث
• الاستكشاف بالعمق أولاً
• انتشار القيود
• التقليم
• دوال التحديد
• الحل الحالي
• مشكلة الملكات N
• استرخاء البرمجة العددية

Key theories

تقليم شجرة البحث

ينظم كلا النموذجين الحلول المرشحة كشجرة يتم استكشافها بالعمق أولاً؛ وتأتي الصحة من الشمولية، بينما تأتي الكفاءة من تقليم الأشجار الفرعية التي لا يمكن أن تحتوي بشكل مؤكد على حل صالح أو محسّن.

دوال التحديد في التفرع والتحديد

يحافظ التفرع والتحديد على أفضل حل تم العثور عليه حتى الآن وحد (مثل استرخاء البرمجة الخطية) على أفضل قيمة يمكن تحقيقها في كل شجرة فرعية؛ ويتم التخلص من الشجرة الفرعية عندما لا يمكن لحدها أن يحسن الحل الحالي.

Clinical relevance

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

History

تم تنظيم التراجع كتقنية عامة في الخمسينيات والستينيات من القرن الماضي، وقد وصفه بشكل خاص غولومب وبومرت. وقد قدمت أيلسا لاند وأليسون دويغ التفرع والتحديد في عام 1960 للبرمجة الخطية العددية، ومنذ ذلك الحين أصبح محوريًا في التحسين التوافقي، مما يدعم حلول البرمجة العددية المختلطة الحديثة.

Key figures

• Ailsa Land
• Alison Doig
• Solomon Golomb
• Robert Bixby

Seminal works

• landdoig1960
• cormen2009

Frequently asked questions

ما الفرق بين التراجع والتفرع والتحديد؟

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

إذا كانت هذه الأساليب أسية في أسوأ الحالات، فلماذا تُستخدم؟

بالنسبة للمشكلات الصعبة من نوع NP، لا توجد خوارزمية دقيقة متعددة الحدود معروفة، ولكن التقليم الفعال غالبًا ما يزيل الغالبية العظمى من شجرة البحث في الحالات الحقيقية، لذا فإن حلول التفرع والتحديد والتراجع غالبًا ما تجد حلولًا مثالية مثبتة أسرع بكثير مما تشير إليه حدود أسوأ الحالات.