شاخه و حد

شاخه و حد یک الگوریتم عمومی برای پیدا کردن راه حل‌های بهینه مسائل مختلف است، بخصوص در بهینه سازی گسسته و ترکیبی .

این الگوریتم تمام راه حل‌های یک مسئله را شمارش می‌کند که در این بین راه حل‌های بی ثمر بسیاری هستند که می‌توان با حذف آنها با تخمین مرزهای بالایی و پایینی، بهینه شود.

این روش اولین بار توسط A. H. Land و A. G. Doig برای برنامه نویسی گسسته در سال 1960 پیشنهاد شد

توصیف کلی

برای قطعیت، ما فرض می‌کنیم که هدف پیدا کردن حداقل مقدار یک تابع (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
• جستجو نزدیکترین همسایه
• مسئله برش موجودی
• تجزیه و تحلیل نویز‌های اشتباه
  

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