---
title: "Branch and bound — طریقۂ شاخ و حدود"
source: "https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF"
wiki: "systems-analysis.info/int"
article: "Branch_and_bound_—_طریقۂ_شاخ_و_حدود"
language: "ur"
categories:
  - "Category:Operations research"
  - "Category:Urdu"
revision_id: 815
wiki_created_at: 2026-09-06T22:39:14Z
wiki_modified_at: 2026-09-06T22:39:14Z
downloaded_at: 2026-09-07T22:42:31Z
---

# Branch and bound — طریقۂ شاخ و حدود

**طریقۂ شاخ و حدود** (انگ. *Branch and Bound*، اختصار **B&B** یا **BnB**) — یہ گسسته اور اشتراکی اصلاح (combinatorial optimization) کے مسائل، خصوصاً NP-مشکل مسائل کے لیے درست الگورتھم تعمیر کرنے کا ایک عمومی اصولی نمونہ (paradigm) ہے<sup>[\[1\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_note-en-wiki-bnb-1)</sup>۔ یہ طریقہ ہدایت یافتہ تعداد شماری کی ایک حکمت عملی ہے جس میں قابلِ قبول حلوں کے پورے مجموعے کو یکے بعد دیگرے ذیلی مجموعوں میں تقسیم کیا جاتا ہے (**شاخ بندی**)، اور ہر ایک کے لیے ہدف فنکشن کی قدر کا تخمینہ (**حدود**) لگایا جاتا ہے۔ یہ تخمینے ان ذیلی مجموعوں کو رد (کاٹ) کرنے میں مدد دیتے ہیں جن میں بہترین حل یقیناً موجود نہیں، جس سے تلاش کی فضا قابلِ ذکر حد تک کم ہو جاتی ہے<sup>[\[2\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_note-ru-wiki-bnb-2)</sup>۔

یہ طریقہ پہلی بار اے۔ لینڈ اور اے۔ ڈوئگ نے ۱۹۶۰ء میں عدد صحیح پروگرامنگ (integer programming) کے مسائل حل کرنے کے لیے پیش کیا<sup>[\[3\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_note-land-doig-1960-3)</sup>۔ اس وقت سے یہ آپریشنز ریسرچ اور کمپیوٹر سائنس میں انتہائی بنیادی طریقوں میں سے ایک بن گیا ہے۔ اس طریقے کی خاص بات اس کی لچک ہے: یہ کوئی مخصوص الگورتھم نہیں بلکہ ایک اعلیٰ سطحی حکمت عملی کا فریم ورک (framework) ہے جو حل کیے جانے والے مسئلے کی ساخت کے مطابق ڈھل سکتا ہے۔

## اہم اجزاء

اس طریقے کی بنیاد تین فنڈامینٹل عملیات پر ہے جو تلاشی درخت (search tree) کی شکل میں منظم حل کی فضا کے ذیلی مجموعوں پر لاگو ہوتی ہیں۔

- **شاخ بندی** (انگ. *Branching*) — یہ موجودہ قابلِ قبول حلوں کے مجموعے $S_{i}$ کو بالعموم غیر متقاطع چھوٹے ذیلی مجموعوں $S_{i1},S_{i2},\ldots,S_{ik}$ میں بار بار تقسیم کرنے کا عمل ہے۔ ہر ایسا ذیلی مجموعہ ایک نئے ذیلی مسئلے کے مطابق ہوتا ہے اور تلاشی درخت میں ایک ذیلی گرہ (child node) کی صورت میں پیش کیا جاتا ہے۔ مثال کے طور پر، عدد صحیح پروگرامنگ کے مسائل میں شاخ بندی اکثر اس متغیر پر کی جاتی ہے جس کی LP-ریلیکسیشن کے حل میں کسری قدر ہو۔

<!-- -->

- **حدود کا تخمینہ** (انگ. *Bounding*) — تلاشی درخت کے ہر گرہ (یعنی ہر ذیلی مسئلے) کے لیے ہدف فنکشن کی قدر کا تخمینہ لگایا جاتا ہے۔ کمینہ سازی (minimization) کے مسئلے کے لیے یہ **نچلی حد** (*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$ سے مطابق پایا گیا حل عالمی طور پر بہترین ہوتا ہے۔

## اہم خصوصیات اور مضامین

- **درستگی اور یکجائی:** الگورتھم محدود مراحل میں عالمی بہترین حل ضرور تلاش کرتا ہے، بشرطیکہ قابلِ قبول حلوں کا مجموعہ محدود ہو اور شاخ بندی کا طریقہ ہم گرائی (convergent) ہو (یعنی بار بار تقسیم کرنے پر ذیلی مجموعے نقاط کی طرف سمٹتے جائیں)<sup>[\[4\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_note-conitzer-duke-4)</sup>۔
- **تلاشی حکمت عملی:** الگورتھم کی کارکردگی کا انحصار کافی حد تک اگلے گرہ کے انتخاب کی حکمت عملی (مثلاً گہرائی میں تلاش، چوڑائی میں تلاش، بہترین تخمینے کے مطابق تلاش) اور شاخ بندی کے لیے متغیر کے انتخاب پر ہوتا ہے۔ جدید سالوِرز (solvers) اکثر مخلوط حکمت عملیاں استعمال کرتے ہیں<sup>[\[5\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_note-maudet-danoy-2024-5)</sup>۔

## مثالیں

- **عدد صحیح پروگرامنگ کا مسئلہ**: اس طریقے کا کلاسیکی اطلاق۔ ریلیکسیشن کے طور پر خطی پروگرامنگ (linear programming) استعمال ہوتی ہے۔ شاخ بندی کسری متغیر $x_{j}$ پر کی جاتی ہے جس سے اضافی قیود $x_{j} \leq \lfloor x_{j}^{\ast}\rfloor$ اور $x_{j} \geq \lceil x_{j}^{\ast}\rceil$ کے ساتھ دو ذیلی مسائل بنتے ہیں۔
- **سفری سوداگر کا مسئلہ**: حلوں کی فضا گراف میں تمام ممکنہ ہیملٹونی چکر ہیں۔ شاخ بندی کناروں (edges) پر کی جا سکتی ہے (کنارے کو راستے میں شامل کریں یا خارج کریں)۔ نچلی حدوں کے لیے آسان تر مسائل کے حل استعمال ہو سکتے ہیں، جیسے تفویض کا مسئلہ یا کم از کم پھیلاؤ درخت کی تعمیر<sup>[\[6\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_note-little-1963-6)</sup>۔

## متعلقہ تصورات اور اطلاقات

- **طریقۂ شاخ و کٹائی** (*Branch-and-Cut*): ایک مخلوط طریقہ جو B&B کو کاٹنے والے سطوح کے طریقے (cutting plane method) کے ساتھ جوڑتا ہے۔ تلاشی درخت کے ہر گرہ پر، ریلیکسیشن حل کرنے کے علاوہ، اضافی ناہمواریاں (کٹائیاں) بھی پیدا کی جاتی ہیں جو نچلی حد کو مضبوط بناتی ہیں اور شاخوں کی کٹائی زیادہ مؤثر ہو جاتی ہے۔
- **واپسی کے ساتھ تلاش** (*Backtracking*): طریقۂ شاخ و حدود کو اصلاحی مسائل کے لیے اس الگورتھم کا عمومی نسخہ سمجھا جا سکتا ہے۔
- **الفا-بیٹا کٹائی**: ایک تصوراتی مماثلت جو کھیل کے درختوں میں یقیناً ناکام شاخوں کو کاٹنے کے لیے استعمال ہوتی ہے۔

## دیکھیے بھی

- عدد صحیح پروگرامنگ
- اشتراکی اصلاح
- سفری سوداگر کا مسئلہ
- NP-مشکل مسئلہ
- سمپلکس طریقہ

## حواشی

<sup>[\[1\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_note-en-wiki-bnb-1)</sup> <sup>[\[2\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_note-ru-wiki-bnb-2)</sup> <sup>[\[3\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_note-land-doig-1960-3)</sup> <sup>[\[4\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_note-conitzer-duke-4)</sup> <sup>[\[5\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_note-maudet-danoy-2024-5)</sup> <sup>[\[6\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_note-little-1963-6)</sup> \</references\>

1.  <span id="cite_note-en-wiki-bnb-1">↑ <sup>[1.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_ref-en-wiki-bnb_1-0)</sup> <sup>[1.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_ref-en-wiki-bnb_1-1)</sup> Wikipedia contributors. (2025). Branch and bound. In *Wikipedia, The Free Encyclopedia*. Retrieved 2025-10-26, from <a href="https://en.wikipedia.org/wiki/Branch_and_bound" class="external free" rel="nofollow">https://en.wikipedia.org/wiki/Branch_and_bound</a></span>
2.  <span id="cite_note-ru-wiki-bnb-2">↑ <sup>[2.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_ref-ru-wiki-bnb_2-0)</sup> <sup>[2.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_ref-ru-wiki-bnb_2-1)</sup> Wikipedia contributors. (2023). Метод ветвей и границ. In *Русская Википедия*. Retrieved 2025-10-26, from <a href="https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ" class="external free" rel="nofollow">https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ</a></span>
3.  <span id="cite_note-land-doig-1960-3">↑ <sup>[3.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_ref-land-doig-1960_3-0)</sup> <sup>[3.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_ref-land-doig-1960_3-1)</sup> 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: <a href="https://www.jstor.org/stable/1910129" class="external free" rel="nofollow">https://www.jstor.org/stable/1910129</a></span>
4.  <span id="cite_note-conitzer-duke-4">↑ <sup>[4.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_ref-conitzer-duke_4-0)</sup> <sup>[4.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_ref-conitzer-duke_4-1)</sup> Conitzer, V. (2008). *Solving (mixed) integer programs using branch and bound*. Duke University, Department of Computer Science. URL: <a href="https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf" class="external free" rel="nofollow">https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf</a></span>
5.  <span id="cite_note-maudet-danoy-2024-5">↑ <sup>[5.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_ref-maudet-danoy-2024_5-0)</sup> <sup>[5.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_ref-maudet-danoy-2024_5-1)</sup> 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: <a href="https://arxiv.org/abs/2412.09444" class="external free" rel="nofollow">https://arxiv.org/abs/2412.09444</a></span>
6.  <span id="cite_note-little-1963-6">↑ <sup>[6.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_ref-little-1963_6-0)</sup> <sup>[6.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D8%B7%D8%B1%DB%8C%D9%82%DB%82_%D8%B4%D8%A7%D8%AE_%D9%88_%D8%AD%D8%AF%D9%88%D8%AF#cite_ref-little-1963_6-1)</sup> 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: <a href="https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf" class="external free" rel="nofollow">https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf</a></span>