شاخه و حد

برای قطعیت، ما فرض می‌کنیم که هدف پیدا کردن حداقل مقدار یک تابع (f(x است، که در آن x در دامنه مجموعه S که از راه حل‌های مجاز و پیشنهادی است، می‌باشد (فضای جستجو یا منطقه مجاز). توجه داشته باشید که با پیدا کردن حداکثر مقدار (g(x) = -f(x، می‌توان حداقل مقدار (f(x را پیدا کرد. (برای مثال اگر S مجموعه‌ای از برنامه‌های ممکن برای ناوگان اتوبوس باشد، (f(x را می‌توان انتظار از درآمد برنامه‌های x دانست). روش شاخه و حد به دو ابزار نیاز دارد: اول روش تقسیم کردن مجموعه پیشنهاد شده S است که داده شده، که دو یا چند مجموعه کوچکتر را بازمی‌گرداند، که مجموعاً S را پوشش می‌دهند. توجه داشته باشید که مقدار حداقل (f(x بر روی{... , S ,min{V1 , V2 است، که هر Vi حداقل (f(x به همراه Si است. این مرحله شاخه شدن نامیده می‌شود. از وقتی که برنامه‌های بازگشتی، یک درخت تعریف شدند (درخت جستجو) گره‌ها همان زیرمجموعه‌های S هستند. ابزار دیگر روش محاسبه مرزهای بالایی و پایینی برای محاسبه مقدار حداقل (f(x با زیر مجموعه داده شده از S. این مرحله Bounding نامیده می‌شود. ایده کلیدی الگوریتم شاخه و حد این است: درصورتی که حد پایین برای بعضی گره‌های درخت (مجموعه‌ای از راه حل‌های پیشنهادی) A بزرگتر از دیگر گره‌ها B است، در آن صورت با اطمینان می‌تواند A از جستجو دور انداخته شود. این مرحله هرس کردن نام دارد و معمولاً با متغیر جهانی m (مشترک در میان تمام گره‌ها از درخت) پیاده‌سازی می‌شود، که حداقل حد بالایی که تاکنون دیده شده در میان تمام حاشیه‌ها را ثبت می‌کند. هر گره کران پایین که بزرگتر از m است می‌تواند دور انداخته شود.

تابع بازگشتی زمانی متوقف می‌شود که مجموعه راه حل پیشنهادی جاری S به یک عنصر کاهش یابد، و همچنین زمانی که حد بالای مجموعه S منطبق بر حد پایین شود. در هر صورت، هر عنصر از S حداقل تابع را در درون Sخواهد بود.

این رویکرد برای حل تعدادی از مسائل NP سخت استفاده می‌شود. از قبیل:

• مسئله کوله پشتی
• برنامه‌ریزی عددصحیح
• برنامه‌ریزی غیر خطی
• مسئله فروشنده دوره‌گرد
• مشکل تخصیص درجه دوم
• Maximum satisfiability problem
• جستجو نزدیکترین همسایه
• مسئله برش موجودی
• تجزیه و تحلیل نویزهای اشتباه

می‌توان در شاخه و حد ابتکارات مختلفی بکار برد. برای مثال، ممکن است کسی بخواهد مرحله شاخه کردن را زمانی که شکاف بین حد پایین و بالا به کوچکتر از یک آستانه شد، پایان دهد. این هنگامی استفاده می‌شود که راه حل به اندازه کافی برای اهداف کاربردی خوب باشد و می‌تواند محاسبات لازم را تا حد زیادی کاهش دهد. این نوع راه حل قابل اجرا است بخصوص زمانیکه تابع هزینه به کار رفته شلوغ یا حاصل برآورد آماری باشد، و همچنین دقیقاً شناخته نشده باشد، بلکه در طیف وسیعی از ارزش‌ها با احتمال خاص شناخته شده‌اند. نمونه‌ای از کاربرد آن در زیست‌شناسی است. هنگام انجام تجزیه و تحلیل برای ارزیابی روابط تکاملی بین موجودات، که اغلب در آن مجموعه داده‌های غیرعملی بزرگی هستند. به همین دلیل روش شاخه و حد اغلب در الگوریتم درخت جستجو در بازی استفاده می‌شود که مهم‌ترین آن‌ها در هرس آلفا-بتا استفاده می‌شود.