التفريغ والتحديد (بالانجليزية Branch and bound أو BB أو B&B) هو تصميم لنموذج خوارزمية لمشاكل الأمثل منفصلة واندماجي، فضلا العامة مشاكل قيمتها الحقيقية.[1][2][3] وتتكون الخوارزمية فرع ومحددة من تعداد المنهجي للحلول مرشح عن طريق البحث مساحة الدولة: يعتقد أن مجموعة من الحلول مرشح أنها تشكل شجرة الجذور مع مجموعة كاملة من جذورها. الخوارزمية يستكشف فروع هذه الشجرة، التي تمثل مجموعات فرعية من مجموعة الحل. قبل تعداد الحلول المرشحة فرع، يتم فحص الفرع ضد الحدود العليا والدنيا المقدرة على الحل الأمثل، ويتم تجاهل إذا كان لا يمكن أن تنتج حلا أفضل من أفضل واحد وجدت حتى الآن الخوارزمية.
مراجع
- Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox ( كتاب إلكتروني PDF ). Springer. صفحة 249. مؤرشف من الأصل ( كتاب إلكتروني PDF ) في 19 يونيو 2018.
- Nowozin, Sebastian; Lampert, Christoph H. (2011). "Structured Learning and Prediction in Computer Vision". Foundations and Trends in Computer Graphics and Vision. 6 (3–4): 185–365. doi:10.1561/0600000033. .
- Nau, Dana S.; Kumar, Vipin; Kanal, Laveen (1984). "General branch and bound, and its relation to A∗ and AO∗" ( كتاب إلكتروني PDF ). Artificial Intelligence. 23 (1): 29–58. doi:10.1016/0004-3702(84)90004-3. مؤرشف من الأصل ( كتاب إلكتروني PDF ) في 23 أبريل 2013.