--- title: "Branch and bound — روش شاخه و کران" source: "https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86" wiki: "systems-analysis.info/int" article: "Branch_and_bound_—_روش_شاخه_و_کران" language: "fa" categories: - "Category:Operations research" - "Category:Persian" revision_id: 813 wiki_created_at: 2026-09-06T22:39:12Z wiki_modified_at: 2026-09-06T22:39:12Z downloaded_at: 2026-09-07T22:42:30Z --- # Branch and bound — روش شاخه و کران **روش شاخه و کران** (به انگلیسی: *Branch and Bound*، مخفف **B&B** یا **BnB**) یک الگوی کلی برای ساخت الگوریتم‌های دقیق جهت حل مسائل بهینه‌سازی گسسته و ترکیبیاتی، به‌ویژه مسائل NP-سخت است[\[1\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_note-en-wiki-bnb-1). این روش یک راهبرد جستجوی هدایت‌شده است که در آن کل مجموعه‌ی راه‌حل‌های مجاز به‌تدریج به زیرمجموعه‌هایی تقسیم می‌شود (**شاخه‌بندی**)، و برای هر یک از آن‌ها برآوردهایی (**کران‌ها**) از مقدار تابع هدف محاسبه می‌گردد. این برآوردها امکان حذف (هرس) آن دسته از زیرمجموعه‌هایی را فراهم می‌کنند که مشخصاً راه‌حل بهینه‌ای در خود ندارند، و این امر فضای جستجو را به‌طور قابل توجهی کاهش می‌دهد[\[2\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_note-ru-wiki-bnb-2). این روش برای نخستین بار توسط A. Land و A. Doig در سال ۱۹۶۰ برای حل مسائل برنامه‌ریزی عددصحیح پیشنهاد شد[\[3\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_note-land-doig-1960-3). از آن زمان، این روش به یکی از بنیادی‌ترین رویکردها در تحقیق در عملیات و علوم کامپیوتر تبدیل شده است. ویژگی کلیدی این روش انعطاف‌پذیری آن است: این روش یک الگوریتم مشخص نیست، بلکه یک چارچوب راهبردی سطح‌بالا (framework) است که با ساختار مسئله‌ی مورد حل، سازگار می‌شود. ## اجزای کلیدی روش اساس این روش بر سه عملیات بنیادی استوار است که بر زیرمجموعه‌های فضای راه‌حل، که به صورت درخت جستجو سازمان‌دهی شده‌اند، اعمال می‌شوند. - **شاخه‌بندی** (به انگلیسی: *Branching*) — فرآیند تقسیم بازگشتی مجموعه‌ی فعلی راه‌حل‌های مجاز $S_{i}$ به چند زیرمجموعه‌ی کوچک‌تر، معمولاً ناهم‌پوشان $S_{i1},S_{i2},\ldots,S_{ik}$. هر یک از این زیرمجموعه‌ها به یک زیرمسئله‌ی جدید تناظر دارد و به صورت یک گره‌ی فرزند در درخت جستجو نمایش داده می‌شود. برای مثال، در مسائل برنامه‌ریزی عددصحیح، شاخه‌بندی اغلب روی متغیری انجام می‌شود که در جواب ریلکسیشن LP مقداری کسری دارد. - **برآورد کران‌ها** (به انگلیسی: *Bounding*) — برای هر گره‌ی درخت جستجو (یعنی برای هر زیرمسئله)، برآوردی از مقدار تابع هدف محاسبه می‌شود. برای مسئله‌ی کمینه‌سازی، این برآورد **کران پایین** (*lower bound*) است که یک تخمین تضمین‌شده از پایین برای هر راه‌حل در آن زیرمجموعه ارائه می‌دهد. این برآورد معمولاً از طریق حل *ریلکسیشن* زیرمسئله‌ی اصلی به دست می‌آید — نسخه‌ای ساده‌شده که در آن برخی قیود دشوار (مثلاً قید صحت) به‌طور موقت نادیده گرفته می‌شوند. رایج‌ترین روش، ریلکسیشن LP است. - **هرس** (به انگلیسی: *Pruning*) — فرآیند حذف گره‌هایی (و کل زیردرخت‌های مربوط به آن‌ها) از بررسی، که مشخصاً نمی‌توانند راه‌حل بهینه داشته باشند. یک گره در یکی از موارد زیر هرس می‌شود: 1. **هرس بر اساس کران**: کران پایین برای گره‌ی مورد نظر از بهترین راه‌حل مجاز یافت‌شده تاکنون که **رکورد** (*incumbent*) نامیده می‌شود، بهتر نیست (یعنی برای مسئله‌ی کمینه‌سازی، بزرگتر یا مساوی است). 2. **هرس بر اساس مجاز بودن**: جواب ریلکسیشن گره برای مسئله‌ی اصلی مجاز است (مثلاً همه‌ی متغیرها عددصحیح هستند). این راه‌حل با رکورد فعلی مقایسه می‌شود و اگر بهتر باشد، رکورد به‌روز می‌شود. شاخه‌بندی بیشتر از این گره ضروری نیست. 3. **هرس بر اساس ناشدنی بودن**: زیرمسئله‌ی متناظر با این گره، هیچ راه‌حل مجازی ندارد. ## الگوریتم کلی الگوریتم تعمیم‌یافته‌ی روش شاخه و کران برای مسئله‌ی کمینه‌سازی را می‌توان با گام‌های زیر توصیف کرد: 1. **مقداردهی اولیه:** یک راه‌حل مجاز اولیه پیدا کنید (مثلاً با استفاده از یک اکتشافی) و مقدار آن را به عنوان کران بالای اولیه (رکورد) تنظیم کنید $U$. یک صف از گره‌های فعال $Q$ ایجاد کنید که شامل گره‌ی ریشه (مسئله‌ی اصلی) باشد. 2. **حلقه‌ی اصلی:** تا زمانی که صف $Q$ خالی نشده است: - یک گره را از $Q$ بر اساس راهبرد جستجو انتخاب کنید (مثلاً جستجوی عمق‌اول یا جستجو با بهترین برآورد). - ریلکسیشن این گره را حل کنید و کران پایین $L$ را به دست آورید. - اگر $L \geq U$، گره را **هرس** کنید. - اگر جواب ریلکسیشن برای مسئله‌ی اصلی مجاز است، رکورد را به‌روز کنید: $U\leftarrow L$. - اگر گره هرس نشده و راه‌حل مجاز نیست، **شاخه‌بندی** انجام دهید، آن را به گره‌های فرزند تقسیم کنید و آن‌ها را به صف $Q$ اضافه کنید. 3. **پایان:** وقتی صف $Q$ خالی می‌شود، الگوریتم به پایان می‌رسد. راه‌حل یافت‌شده متناظر با رکورد $U$، بهینه‌ی سراسری است. ## ویژگی‌ها و قضایای کلیدی - **درستی و همگرایی:** الگوریتم تضمین می‌دهد که در تعداد متناهی از گام‌ها، راه‌حل بهینه‌ی سراسری را پیدا می‌کند، مشروط بر اینکه مجموعه‌ی راه‌حل‌های مجاز متناهی باشد و رویه‌ی شاخه‌بندی همگرا باشد (یعنی در تقسیم‌بندی‌های بازگشتی، زیرمجموعه‌ها به نقاط «منقبض» شوند)[\[4\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_note-conitzer-duke-4). - **راهبرد جستجو:** کارایی الگوریتم به شدت به راهبرد انتخاب گره‌ی بعدی برای شاخه‌بندی (مثلاً جستجوی عمق‌اول، جستجوی سطح‌اول، جستجو با بهترین برآورد) و به انتخاب متغیر برای شاخه‌بندی بستگی دارد. حل‌کننده‌های مدرن اغلب از راهبردهای ترکیبی استفاده می‌کنند[\[5\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_note-maudet-danoy-2024-5). ## مثال‌ها - **مسئله‌ی برنامه‌ریزی عددصحیح**: کاربرد کلاسیک این روش. از برنامه‌ریزی خطی به عنوان ریلکسیشن استفاده می‌شود. شاخه‌بندی روی متغیر کسری $x_{j}$ انجام می‌شود و دو زیرمسئله با قیود اضافه‌ی $x_{j} \leq \lfloor x_{j}^{\ast}\rfloor$ و $x_{j} \geq \lceil x_{j}^{\ast}\rceil$ ایجاد می‌کند. - **مسئله‌ی فروشنده‌ی دوره‌گرد**: فضای راه‌حل شامل تمام دورهای همیلتونی در گراف است. شاخه‌بندی می‌تواند روی یال‌ها انجام شود (درج/حذف یال از مسیر). کران‌های پایین می‌توانند از طریق حل مسائل ساده‌تری مانند مسئله‌ی انتساب یا ساخت درخت پوشای کمینه به دست آیند[\[6\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_note-little-1963-6). ## مفاهیم مرتبط و کاربردها - **روش شاخه و برش** (*Branch-and-Cut*): روشی ترکیبی که B&B را با روش صفحات برش ترکیب می‌کند. در هر گره‌ی درخت جستجو، علاوه بر حل ریلکسیشن، نامساوی‌های اضافه‌ای (برش‌ها) تولید می‌شوند که کران پایین را تقویت می‌کنند و این منجر به هرس مؤثرتر شاخه‌ها می‌شود. - **جستجو با بازگشت** (*Backtracking*): روش شاخه و کران را می‌توان به عنوان تعمیم این الگوریتم برای مسائل بهینه‌سازی در نظر گرفت. - **هرس آلفا-بتا**: یک قیاس مفهومی که در درخت‌های بازی برای هرس شاخه‌های مشخصاً بازنده به کار می‌رود. ## همچنین ببینید - برنامه‌ریزی عددصحیح - بهینه‌سازی ترکیبیاتی - مسئله‌ی فروشنده‌ی دوره‌گرد - مسئله‌ی NP-سخت - روش سیمپلکس ## یادداشت‌ها [\[1\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_note-en-wiki-bnb-1) [\[2\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_note-ru-wiki-bnb-2) [\[3\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_note-land-doig-1960-3) [\[4\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_note-conitzer-duke-4) [\[5\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_note-maudet-danoy-2024-5) [\[6\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_note-little-1963-6) \ 1. ↑ [1.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_ref-en-wiki-bnb_1-0) [1.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_ref-en-wiki-bnb_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. ↑ [2.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_ref-ru-wiki-bnb_2-0) [2.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_ref-ru-wiki-bnb_2-1) Wikipedia contributors. (2023). Метод ветвей и границ. In *Русская Википедия*. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ 3. ↑ [3.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_ref-land-doig-1960_3-0) [3.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_ref-land-doig-1960_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. ↑ [4.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_ref-conitzer-duke_4-0) [4.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_ref-conitzer-duke_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. ↑ [5.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_ref-maudet-danoy-2024_5-0) [5.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_ref-maudet-danoy-2024_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. ↑ [6.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_ref-little-1963_6-0) [6.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B1%D9%88%D8%B4_%D8%B4%D8%A7%D8%AE%D9%87_%D9%88_%DA%A9%D8%B1%D8%A7%D9%86#cite_ref-little-1963_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