Branch and bound — روش شاخه و کران

روش شاخه و کران (به انگلیسی: Branch and Bound، مخفف B&B یا BnB) یک الگوی کلی برای ساخت الگوریتم‌های دقیق جهت حل مسائل بهینه‌سازی گسسته و ترکیبیاتی، به‌ویژه مسائل NP-سخت است^[1]. این روش یک راهبرد جستجوی هدایت‌شده است که در آن کل مجموعه‌ی راه‌حل‌های مجاز به‌تدریج به زیرمجموعه‌هایی تقسیم می‌شود (شاخه‌بندی)، و برای هر یک از آن‌ها برآوردهایی (کران‌ها) از مقدار تابع هدف محاسبه می‌گردد. این برآوردها امکان حذف (هرس) آن دسته از زیرمجموعه‌هایی را فراهم می‌کنند که مشخصاً راه‌حل بهینه‌ای در خود ندارند، و این امر فضای جستجو را به‌طور قابل توجهی کاهش می‌دهد^[2].

این روش برای نخستین بار توسط A. Land و A. Doig در سال ۱۹۶۰ برای حل مسائل برنامه‌ریزی عددصحیح پیشنهاد شد^[3]. از آن زمان، این روش به یکی از بنیادی‌ترین رویکردها در تحقیق در عملیات و علوم کامپیوتر تبدیل شده است. ویژگی کلیدی این روش انعطاف‌پذیری آن است: این روش یک الگوریتم مشخص نیست، بلکه یک چارچوب راهبردی سطح‌بالا (framework) است که با ساختار مسئله‌ی مورد حل، سازگار می‌شود.

اجزای کلیدی روش

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

شاخه‌بندی (به انگلیسی: Branching) — فرآیند تقسیم بازگشتی مجموعه‌ی فعلی راه‌حل‌های مجاز $S_{i}$ به چند زیرمجموعه‌ی کوچک‌تر، معمولاً ناهم‌پوشان $S_{i 1}, S_{i 2}, \dots, S_{i k}$ . هر یک از این زیرمجموعه‌ها به یک زیرمسئله‌ی جدید تناظر دارد و به صورت یک گره‌ی فرزند در درخت جستجو نمایش داده می‌شود. برای مثال، در مسائل برنامه‌ریزی عددصحیح، شاخه‌بندی اغلب روی متغیری انجام می‌شود که در جواب ریلکسیشن LP مقداری کسری دارد.

برآورد کران‌ها (به انگلیسی: Bounding) — برای هر گره‌ی درخت جستجو (یعنی برای هر زیرمسئله)، برآوردی از مقدار تابع هدف محاسبه می‌شود. برای مسئله‌ی کمینه‌سازی، این برآورد کران پایین (lower bound) است که یک تخمین تضمین‌شده از پایین برای هر راه‌حل در آن زیرمجموعه ارائه می‌دهد. این برآورد معمولاً از طریق حل ریلکسیشن زیرمسئله‌ی اصلی به دست می‌آید — نسخه‌ای ساده‌شده که در آن برخی قیود دشوار (مثلاً قید صحت) به‌طور موقت نادیده گرفته می‌شوند. رایج‌ترین روش، ریلکسیشن LP است.

هرس (به انگلیسی: Pruning) — فرآیند حذف گره‌هایی (و کل زیردرخت‌های مربوط به آن‌ها) از بررسی، که مشخصاً نمی‌توانند راه‌حل بهینه داشته باشند. یک گره در یکی از موارد زیر هرس می‌شود:

هرس بر اساس کران: کران پایین برای گره‌ی مورد نظر از بهترین راه‌حل مجاز یافت‌شده تاکنون که رکورد (incumbent) نامیده می‌شود، بهتر نیست (یعنی برای مسئله‌ی کمینه‌سازی، بزرگتر یا مساوی است).
هرس بر اساس مجاز بودن: جواب ریلکسیشن گره برای مسئله‌ی اصلی مجاز است (مثلاً همه‌ی متغیرها عددصحیح هستند). این راه‌حل با رکورد فعلی مقایسه می‌شود و اگر بهتر باشد، رکورد به‌روز می‌شود. شاخه‌بندی بیشتر از این گره ضروری نیست.
هرس بر اساس ناشدنی بودن: زیرمسئله‌ی متناظر با این گره، هیچ راه‌حل مجازی ندارد.

الگوریتم کلی

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

مقداردهی اولیه: یک راه‌حل مجاز اولیه پیدا کنید (مثلاً با استفاده از یک اکتشافی) و مقدار آن را به عنوان کران بالای اولیه (رکورد) تنظیم کنید $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-سخت
روش سیمپلکس

یادداشت‌ها

^[1] ^[2] ^[3] ^[4] ^[5] ^[6] </references>

↑ ^1.0 ^1.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
↑ ^2.0 ^2.1 Wikipedia contributors. (2023). Метод ветвей и границ. In Русская Википедия. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ
↑ ^3.0 ^3.1 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
↑ ^4.0 ^4.1 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
↑ ^5.0 ^5.1 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
↑ ^6.0 ^6.1 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] 1.0 ^1.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] 2.0 ^2.1 Wikipedia contributors. (2023). Метод ветвей и границ. In Русская Википедия. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ

[land-doig-1960-3] 3.0 ^3.1 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] 4.0 ^4.1 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] 5.0 ^5.1 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] 6.0 ^6.1 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