Branch and bound — शाखा और सीमा विधि

From Systems analysis Wiki
Jump to navigation Jump to search

शाखा और सीमा विधि (अंग्रेज़ी: Branch and Bound, संक्षेप में B&B या BnB) — यह असतत और संयोजनात्मक अनुकूलन समस्याओं, विशेष रूप से NP-कठिन समस्याओं को हल करने के लिए सटीक एल्गोरिदम निर्माण की एक सामान्य प्रतिमान है[1]। यह विधि एक निर्देशित गणना की रणनीति है, जिसमें सभी स्वीकार्य हलों के समुच्चय को क्रमशः उपसमुच्चयों में विभाजित किया जाता है (शाखाकरण), और प्रत्येक के लिए उद्देश्य फ़ंक्शन के मान के आकलन (सीमाएँ) की गणना की जाती है। ये आकलन उन उपसमुच्चयों को अस्वीकार (छाँटने) करने की अनुमति देते हैं जो स्पष्ट रूप से इष्टतम हल नहीं रखते, जिससे खोज स्थान में उल्लेखनीय कमी आती है[2]।

यह विधि सर्वप्रथम ए. लैंड और ए. डॉइग द्वारा 1960 में पूर्णांक प्रोग्रामिंग समस्याओं को हल करने के लिए प्रस्तावित की गई थी[3]। तब से यह संचालन अनुसंधान और कंप्यूटर विज्ञान में सबसे मौलिक दृष्टिकोणों में से एक बन गई है। विधि की प्रमुख विशेषता इसकी लचीलापन है: यह कोई विशिष्ट एल्गोरिदम नहीं, बल्कि एक उच्च-स्तरीय रणनीतिक योजना (framework) है, जो हल की जाने वाली समस्या की संरचना के अनुकूल होती है।

विधि के प्रमुख घटक

विधि का आधार तीन मूलभूत क्रियाएँ हैं, जो हल स्थान के उपसमुच्चयों पर लागू होती हैं, जिन्हें एक खोज वृक्ष के रूप में व्यवस्थित किया जाता है।

  • शाखाकरण (अंग्रेज़ी: Branching) — यह वर्तमान स्वीकार्य हलों के समुच्चय Si को कई छोटे, सामान्यतः असंयुक्त उपसमुच्चयों Si1,Si2,…,Sik में पुनरावर्ती रूप से विभाजित करने की प्रक्रिया है। प्रत्येक ऐसा उपसमुच्चय एक नई उपसमस्या से मेल खाता है और खोज वृक्ष में एक बाल नोड के रूप में प्रस्तुत किया जाता है। उदाहरण के लिए, पूर्णांक प्रोग्रामिंग समस्याओं में शाखाकरण अक्सर उस चर के अनुसार किया जाता है जिसका LP-शिथिलीकरण के हल में भिन्नात्मक मान होता है।
  • सीमा आकलन (अंग्रेज़ी: Bounding) — खोज वृक्ष के प्रत्येक नोड (अर्थात् प्रत्येक उपसमस्या) के लिए उद्देश्य फ़ंक्शन के मान का आकलन किया जाता है। न्यूनीकरण समस्या के लिए यह निम्न सीमा (lower bound) होती है, जो दिए गए उपसमुच्चय में किसी भी हल के लिए एक गारंटीकृत निम्न आकलन है। प्रायः यह आकलन मूल उपसमस्या के शिथिलीकरण — एक सरलीकृत संस्करण जिसमें कुछ जटिल बाधाएँ (जैसे पूर्णांकता) अस्थायी रूप से अनदेखी की जाती हैं — को हल करके प्राप्त किया जाता है। सबसे सामान्य LP-शिथिलीकरण है।
  • छँटाई (अंग्रेज़ी: Pruning) — यह उन नोडों (और उनके संपूर्ण उपवृक्षों) को विचार से हटाने की प्रक्रिया है जो स्पष्ट रूप से इष्टतम हल नहीं रख सकते। नोड को निम्नलिखित में से किसी एक स्थिति में छाँटा जाता है:
  1. सीमा द्वारा छँटाई: किसी नोड की निम्न सीमा वर्तमान में पाए गए सर्वोत्तम स्वीकार्य हल के मान से बेहतर नहीं होती (अर्थात् न्यूनीकरण समस्या के लिए उससे बड़ी या बराबर होती है), जिसे रिकॉर्ड (incumbent) कहा जाता है।
  2. स्वीकार्यता द्वारा छँटाई: नोड के शिथिलीकरण का हल मूल समस्या के लिए स्वीकार्य है (उदाहरण के लिए, सभी चर पूर्णांक हैं)। इस हल की तुलना वर्तमान रिकॉर्ड से की जाती है और यदि यह बेहतर है, तो रिकॉर्ड अद्यतन किया जाता है। इस नोड से आगे शाखाकरण की आवश्यकता नहीं होती।
  3. अव्यवहार्यता द्वारा छँटाई: नोड के अनुरूप उपसमस्या का कोई स्वीकार्य हल नहीं है।

सामान्य एल्गोरिदम

न्यूनीकरण समस्या के लिए शाखा और सीमा विधि के सामान्यीकृत एल्गोरिदम को निम्नलिखित चरणों में वर्णित किया जा सकता है:

  1. आरंभीकरण: एक प्रारंभिक स्वीकार्य हल खोजें (उदाहरण के लिए, ह्यूरिस्टिक्स की सहायता से) और उसके मान को प्रारंभिक ऊपरी सीमा (रिकॉर्ड) के रूप में स्थापित करें U। मूल नोड (मूल समस्या) वाली सक्रिय नोडों की प्रतीक्षा सूची Q बनाएँ।
  2. मुख्य चक्र: जब तक प्रतीक्षा सूची Q खाली न हो:
    • खोज रणनीति (जैसे गहराई-प्रथम खोज या सर्वोत्तम-प्रथम खोज) के अनुसार Q से एक नोड चुनें।
    • इस नोड के लिए शिथिलीकरण हल करें और निम्न सीमा L प्राप्त करें।
    • यदि L≥U तो नोड को छाँटें।
    • यदि शिथिलीकरण का हल मूल समस्या के लिए स्वीकार्य है, तो रिकॉर्ड अद्यतन करें: U←L।
    • यदि नोड नहीं छाँटा गया और हल स्वीकार्य नहीं है, तो शाखाकरण करें — इसे बाल नोडों में विभाजित करें और उन्हें प्रतीक्षा सूची Q में जोड़ें।
  3. समापन: जब प्रतीक्षा सूची Q खाली हो जाती है, एल्गोरिदम समाप्त होता है। रिकॉर्ड U के अनुरूप पाया गया हल वैश्विक रूप से इष्टतम है।

प्रमुख गुण और प्रमेय

  • शुद्धता और अभिसरण: एल्गोरिदम परिमित चरणों में वैश्विक रूप से इष्टतम हल खोजने की गारंटी देता है, बशर्ते कि स्वीकार्य हलों का समुच्चय परिमित हो और शाखाकरण प्रक्रिया अभिसारी हो (अर्थात् पुनरावर्ती विभाजन पर उपसमुच्चय बिंदुओं की ओर सिकुड़ते हों)[4]।
  • खोज रणनीति: एल्गोरिदम की दक्षता शाखाकरण के लिए अगले नोड के चयन की रणनीति (जैसे गहराई-प्रथम खोज, चौड़ाई-प्रथम खोज, सर्वोत्तम-आकलन खोज) और शाखाकरण के लिए चर के चयन पर अत्यधिक निर्भर करती है। आधुनिक सॉल्वर प्रायः संकर रणनीतियाँ उपयोग करते हैं[5]।

उदाहरण

  • पूर्णांक प्रोग्रामिंग समस्या: विधि का क्लासिक अनुप्रयोग। शिथिलीकरण के रूप में रैखिक प्रोग्रामिंग का उपयोग किया जाता है। शाखाकरण भिन्नात्मक चर xj के अनुसार होता है, जिससे अतिरिक्त बाधाओं xj≤⌊xj∗⌋ और xj≥⌈xj∗⌉ वाली दो उपसमस्याएँ बनती हैं।
  • विक्रेता यात्रा समस्या (Travelling Salesman Problem): हल स्थान — ग्राफ में सभी संभव हैमिल्टोनियन चक्र। शाखाकरण किनारों के अनुसार किया जा सकता है (मार्ग में किनारे को शामिल करें/हटाएँ)। निम्न सीमाओं के रूप में सरल समस्याओं, जैसे असाइनमेंट समस्या या न्यूनतम आच्छादन वृक्ष निर्माण के हलों का उपयोग किया जा सकता है[6]।

संबंधित अवधारणाएँ और अनुप्रयोग

  • Branch-and-Cut - शाखा और कटौती विधि: एक संकर विधि जो B&B को काटने वाले तलों की विधि के साथ जोड़ती है। खोज वृक्ष के प्रत्येक नोड पर, शिथिलीकरण हल करने के अतिरिक्त, अतिरिक्त असमानताएँ (कटौतियाँ) उत्पन्न की जाती हैं जो निम्न सीमा को सुदृढ़ करती हैं, जिससे शाखाओं की अधिक प्रभावी छँटाई होती है।
  • Backtracking - प्रत्यावर्तन खोज: शाखा और सीमा विधि को अनुकूलन समस्याओं के लिए इस एल्गोरिदम के सामान्यीकरण के रूप में देखा जा सकता है।
  • अल्फा-बीटा छँटाई: खेल वृक्षों में स्पष्ट रूप से हारने वाली शाखाओं को छाँटने के लिए उपयोग की जाने वाली एक वैचारिक सादृश्यता।

यह भी देखें

  • पूर्णांक प्रोग्रामिंग
  • संयोजनात्मक अनुकूलन
  • विक्रेता यात्रा समस्या
  • NP-कठिन समस्या
  • सिम्प्लेक्स विधि

टिप्पणियाँ

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

  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
  2. ↑ 2.0 2.1 Wikipedia contributors. (2023). Метод ветвей и границ. In Русская Википедия. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ
  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
  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
  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
  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
Retrieved from "https://systems-analysis.info/int/index.php?title=Branch_and_bound_—_शाखा_और_सीमा_विधि&oldid=816"