शाखा और बंधन

ब्रांच और बाउंड (BB, B&B, या BnB) अनुकूलन समस्याओं को छोटी उप-समस्याओं में तोड़कर और उप-समस्याओं को खत्म करने के लिए एक बाउंडिंग फ़ंक्शन का उपयोग करके हल करने की एक विधि है जिसमें इष्टतम समाधान नहीं हो सकता है। यह असतत अनुकूलन और संयोजी अनुकूलन समस्याओं के साथ-साथ गणितीय अनुकूलन के लिए एक कलन विधि एल्गोरिथम प्रतिमान है। एक शाखा-और-बाध्य एल्गोरिथ्म में राज्य अंतरिक्ष खोज के माध्यम से उम्मीदवार समाधानों की एक व्यवस्थित गणना होती है: उम्मीदवार समाधानों के सेट को रूट पर पूर्ण सेट के साथ ट्री (ग्राफ़ सिद्धांत) बनाने के रूप में माना जाता है। एल्गोरिद्म इस पेड़ की शाखाओं की पड़ताल करता है, जो समाधान सेट के सबसेट का प्रतिनिधित्व करती है। एक शाखा के उम्मीदवार समाधानों की गणना करने से पहले, शाखा को इष्टतम समाधान पर ऊपरी और निचले अनुमानित सीमा के खिलाफ जांचा जाता है, और अगर यह एल्गोरिथम द्वारा अब तक मिले सबसे अच्छे समाधान से बेहतर समाधान नहीं दे पाता है तो उसे छोड़ दिया जाता है।

एल्गोरिथ्म खोज स्थान के क्षेत्रों/शाखाओं की निचली और ऊपरी सीमा के कुशल आकलन पर निर्भर करता है। यदि कोई सीमा उपलब्ध नहीं है, तो एल्गोरिथम एक संपूर्ण खोज के लिए पतित हो जाता है।

1960 में असतत अनुकूलन के लिए BP द्वारा प्रायोजित लंदन स्कूल ऑफ इकोनॉमिक्स में शोध करते समय पहली बार Ailsa Land और Alison Harcourt द्वारा विधि प्रस्तावित की गई थी। और एनपी कठिन अनुकूलन समस्याओं को हल करने के लिए सबसे अधिक इस्तेमाल किया जाने वाला उपकरण बन गया है।ब्रांच और बाउंड नाम सबसे पहले लिटिल एट अल के काम में आया। यात्रा विक्रेता समस्या पर।

सिंहावलोकन

ब्रांच-एंड-बाउंड एल्गोरिथम का लक्ष्य एक मान खोजना है x जो वास्तविक-मूल्यवान फ़ंक्शन के मान को अधिकतम या कम करता है f(x), कुछ सेट के बीच एक ऑब्जेक्टिव फ़ंक्शन कहा जाता है S स्वीकार्य, या उम्मीदवार समाधान। सेट S को खोज स्थान या व्यवहार्य क्षेत्र कहा जाता है। इस खंड के बाकी हिस्सों में माना जाता है कि कम से कम f(x) वांछित है; यह धारणा व्यापकता के नुकसान के बिना आती है, क्योंकि कोई अधिकतम मूल्य पा सकता है f(x) का न्यूनतम ज्ञात करके g(x) = −f(x). एक बी एंड बी एल्गोरिदम दो सिद्धांतों के अनुसार काम करता है:

• यह पुनरावर्ती रूप से खोज स्थान को छोटे स्थानों में विभाजित करता है, फिर छोटा करता है f(x) इन छोटे स्थानों पर; विभाजन को ब्रांचिंग कहा जाता है।
• अकेले ब्रांचिंग क्रूर-बल खोज | ब्रूट-फोर्स एन्यूमरेशन ऑफ़ कैंडिडेट सॉल्यूशंस और उन सभी का परीक्षण करने की राशि होगी। ब्रूट-फोर्स सर्च के प्रदर्शन में सुधार करने के लिए, B&B एल्गोरिद्म कम से कम सीमा का ट्रैक रखता है जिसे वह खोजने की कोशिश कर रहा है, और इन सीमाओं का उपयोग खोज स्थान की छंटाई (निर्णय ट्री) करने के लिए करता है, उम्मीदवार समाधानों को समाप्त करता है जो यह साबित कर सकता है एक इष्टतम समाधान शामिल नहीं है।

विशिष्ट अनुकूलन समस्या के लिए इन सिद्धांतों को एक ठोस एल्गोरिदम में बदलने के लिए कुछ प्रकार की डेटा संरचना की आवश्यकता होती है जो उम्मीदवार समाधान के सेट का प्रतिनिधित्व करती है। इस तरह के प्रतिनिधित्व को समस्या का उदाहरण कहा जाता है। एक उदाहरण के उम्मीदवार समाधान के सेट को निरूपित करें I द्वारा S_I. उदाहरण के प्रतिनिधित्व को तीन परिचालनों के साथ आना है:

• branch(I) दो या दो से अधिक उदाहरण उत्पन्न करता है जिनमें से प्रत्येक एक सबसेट का प्रतिनिधित्व करता है S_I. (आमतौर पर, उपसमुच्चय असम्बद्ध सेट होते हैं जो एल्गोरिदम को एक ही उम्मीदवार समाधान पर दो बार जाने से रोकते हैं, लेकिन इसकी आवश्यकता नहीं है। हालांकि, बीच में एक इष्टतम समाधान S_I कम से कम एक सबसेट में शामिल होना चाहिए।)
• bound(I) द्वारा दर्शाए गए स्थान में किसी भी उम्मीदवार समाधान के मूल्य पर निचली सीमा की गणना करता है I, वह है, bound(I) ≤ f(x) सभी के लिए x में S_I.
• solution(I) निर्धारित करता है कि क्या I एकल उम्मीदवार समाधान का प्रतिनिधित्व करता है। (वैकल्पिक रूप से, यदि ऐसा नहीं होता है, तो ऑपरेशन बीच में से कुछ व्यवहार्य समाधान वापस करने का विकल्प चुन सकता है S_I.) अगर solution(I) तब एक समाधान लौटाता है f(solution(I)) व्यवहार्य समाधानों के पूरे स्थान पर इष्टतम उद्देश्य मान के लिए ऊपरी सीमा प्रदान करता है।

इन परिचालनों का उपयोग करते हुए, एक बी एंड बी एल्गोरिदम शाखा संचालन द्वारा गठित उदाहरणों के खोज पेड़ के माध्यम से एक शीर्ष-नीचे पुनरावर्ती खोज करता है। एक उदाहरण पर जाने पर I, यह जांचता है कि क्या bound(I) वर्तमान ऊपरी सीमा के बराबर या उससे अधिक है; यदि ऐसा है तो, I को खोज से सुरक्षित रूप से हटाया जा सकता है और पुनरावर्तन बंद हो जाता है। यह छंटाई कदम आमतौर पर एक वैश्विक चर को बनाए रखने के द्वारा कार्यान्वित किया जाता है जो कि अब तक की जांच की गई सभी उदाहरणों में देखी गई न्यूनतम ऊपरी सीमा को रिकॉर्ड करता है।

सामान्य संस्करण

निम्नलिखित एक सामान्य शाखा का कंकाल है और मनमाने ढंग से उद्देश्य समारोह को कम करने के लिए बाध्य एल्गोरिदम है f. इससे एक वास्तविक एल्गोरिथम प्राप्त करने के लिए, एक बाउंडिंग फ़ंक्शन की आवश्यकता होती है bound, जो निम्न सीमा की गणना करता है f सर्च ट्री के नोड्स पर, साथ ही एक समस्या-विशिष्ट ब्रांचिंग नियम। जैसे, यहाँ प्रस्तुत सामान्य एल्गोरिथ्म एक उच्च-क्रम का कार्य है।

1. एक अनुमानी का उपयोग करके एक समाधान खोजें x_h अनुकूलन समस्या के लिए। इसका मूल्य संग्रहीत करें, B = f(x_h). (यदि कोई अनुमानी उपलब्ध नहीं है, तो सेट करें B अनंत की ओर।) B अब तक मिले सर्वोत्तम समाधान को दर्शाएगा, और उम्मीदवार समाधानों पर ऊपरी सीमा के रूप में उपयोग किया जाएगा।
2. असाइन की गई समस्या के किसी भी चर के साथ आंशिक समाधान रखने के लिए एक कतार आरंभ करें।
3. कतार खाली होने तक लूप करें:
   1. एक नोड लें N कतार से बाहर।
   2. अगर N एकल उम्मीदवार समाधान का प्रतिनिधित्व करता है x और f(x) < B, तब x अब तक का सबसे अच्छा समाधान है। इसे रिकॉर्ड करें और सेट करें B ← f(x).
   3. वरना, आगे बढ़ो N नए नोड बनाने के लिए N_i. इनमें से प्रत्येक के लिए:
      1. अगर bound(N_i) > B, कुछ भी नहीं है; चूंकि इस नोड पर निचली सीमा समस्या की ऊपरी सीमा से अधिक है, इसलिए यह कभी भी इष्टतम समाधान की ओर नहीं ले जाएगी, और इसे त्याग दिया जा सकता है।
      2. वरना, स्टोर करें N_i कतार में।

कई अलग-अलग कतार (सार डेटा प्रकार) डेटा संरचनाओं का उपयोग किया जा सकता है। यह फीफो (कंप्यूटिंग और इलेक्ट्रॉनिक्स) आधारित कार्यान्वयन एक चौड़ाई-पहली खोज देता है। एक ढेर (डेटा संरचना) (एलआईएफओ कतार) गहराई-पहली खोज|गहराई-पहला एल्गोरिदम उत्पन्न करेगा। एक श्रेष्ठ-प्रथम खोज|सर्वश्रेष्ठ-प्रथम शाखा और बाउंड एल्गोरिथम एक प्राथमिकता क्यू का उपयोग करके प्राप्त किया जा सकता है जो उनके निचले बाउंड पर नोड्स को सॉर्ट करता है।इस आधार के साथ सर्वश्रेष्ठ-प्रथम खोज एल्गोरिदम के उदाहरण दिज्क्स्ट्रा के एल्गोरिदम और इसके वंशज A* खोज हैं। डेप्थ-फर्स्ट वैरिएंट की सिफारिश तब की जाती है जब एक प्रारंभिक समाधान तैयार करने के लिए कोई अच्छा अनुमानी उपलब्ध नहीं होता है, क्योंकि यह जल्दी से पूर्ण समाधान तैयार करता है, और इसलिए ऊपरी सीमा।

{{Anchor|Code}स्यूडोकोड

एक सी ++ - उपरोक्त के स्यूडोकोड कार्यान्वयन की तरह है: <वाक्यविन्यास प्रकाश लैंग = सी ++ लाइन = 1> // सी ++ - शाखा और बाध्य कार्यान्वयन की तरह, // यह मानकर कि उद्देश्य फलन f को न्यूनतम किया जाना है कॉम्बिनेटरियल सॉल्यूशन ब्रांच_एंड_बाउंड_सॉल्व (

   कॉम्बिनेटरियल प्रॉब्लम प्रॉब्लम,
   ऑब्जेक्टिवफंक्शन ऑब्जेक्टिव_फंक्शन /*f*/,
   बाउंडिंगफंक्शन लोअर_बाउंड_फंक्शन / * बाउंड * /)

{

   // चरण 1 ऊपर
   डबल प्रॉब्लम_अपर_बाउंड = एसटीडी :: न्यूमेरिक_लिमिट्स <डबल> :: इन्फिनिटी; // = बी
   मिश्रित समाधान अनुमानी समाधान = अनुमानी समाधान (समस्या); // x_h
   प्रॉब्लम_अपर_बाउंड = ऑब्जेक्टिव_फंक्शन (हेयुरिस्टिक_सोल्यूशन); // बी = एफ (x_h)
   कॉम्बिनेटरियल सोल्यूशन करंट_ऑप्टिमम = ह्यूरिस्टिक_सोल्यूशन;
   // चरण 2 ऊपर
   कतार <कैंडिडेटसोल्यूशन ट्री> कैंडिडेट_क्यू;
   // समस्या-विशिष्ट कतार आरंभीकरण
   कैंडिडेट_क्यू = पॉप्युलेट_कैंडिडेट्स (समस्या);
   जबकि (!candidate_queue.empty()) { // चरण 3 ऊपर
       // चरण 3.1
       कैंडिडेटसोल्यूशन ट्री नोड = कैंडिडेट_क्यू.पॉप ();
       // नोड ऊपर एन का प्रतिनिधित्व करता है
       if (node.represents_single_candidate()) { // चरण 3.2
           अगर (उद्देश्य_फंक्शन (नोड.कैंडिडेट ()) <समस्या_अपर_बाउंड) {
               current_optimum = node.candidate ();
               प्रॉब्लम_अपर_बाउंड = ऑब्जेक्टिव_फंक्शन (current_optimum);
           }
           // अन्यथा, नोड एक एकल उम्मीदवार है जो इष्टतम नहीं है
       }
       और { // चरण 3.3: नोड उम्मीदवार समाधान की एक शाखा का प्रतिनिधित्व करता है
           // Child_branch उपरोक्त N_i का प्रतिनिधित्व करता है
           के लिए (ऑटो&& चाइल्ड_ब्रांच: नोड.कैंडिडेट_नोड्स) {
               अगर (लोअर_बाउंड_फंक्शन (चाइल्ड_ब्रांच) <= प्रॉब्लम_अपर_बाउंड) {
                   कैंडिडेट_क्यू.एनक्यू (चाइल्ड_ब्रांच); // चरण 3.3.2
               }
               // अन्यथा, बाध्य (N_i)> बी इसलिए हम शाखा को चुभते हैं; चरण 3.3.1
           }
       }
   }
   वापसी वर्तमान_optimum;

} </वाक्यविन्यास हाइलाइट>

उपरोक्त स्यूडोकोड में, functions heuristic_solve और populate_candidates समस्या के लिए उपयुक्त के रूप में सबरूटीन्स के रूप में बुलाया जाना चाहिए। कार्य f (objective_function) और bound (lower_bound_function) लिखित रूप में समारोह वस्तु के रूप में माना जाता है, और सी ++ प्रोग्रामिंग भाषा में अज्ञात फ़ंक्शंस, समारोह सूचक और अन्य प्रकार के कॉल करने योग्य ऑब्जेक्ट्स के अनुरूप हो सकता है।

सुधार

कब $\mathbf {x}$ का सदिश है $\mathbb {R} ^{n}$, शाखा और बाउंड एल्गोरिदम को अंतराल अंकगणित के साथ जोड़ा जा सकता है वैश्विक न्यूनतम के गारंटीकृत संलग्नक प्रदान करने के लिए अंतराल ठेकेदार तकनीकें।

अनुप्रयोग

इस दृष्टिकोण का उपयोग कई एनपी-हार्ड समस्याओं के लिए किया जाता है:

• पूर्णांक प्रोग्रामिंग
• नॉनलाइनियर प्रोग्रामिंग
• ट्रैवलिंग सेल्समैन की समस्या (TSP)
• द्विघात असाइनमेंट समस्या (QAP)
• अधिकतम संतुष्टि समस्या (मैक्स-सैट)
• निकटतम पड़ोसी खोज (कीनोसुके फुकुनागा द्वारा)
• फ्लो शॉप शेड्यूलिंग
• स्टॉक की समस्या में कटौती
• कम्प्यूटेशनल फाइलोजेनेटिक्स
• उलटा सेट करें
• अनुमान लगाएं
• 0/1 बस्ता समस्या
• कवर समस्या सेट करें
• यंत्र अधिगम में फ़ीचर चयन
• कंप्यूटर दृष्टि में संरचित भविष्यवाणी
• चाइनीज पोस्टमैन समस्या सहित आर्क रूटिंग समस्या
• प्रतिभा निर्धारण , सीन शूटिंग अरेंजमेंट प्रॉब्लम

ब्रांच-एंड-बाउंड भी विभिन्न अनुमानों का आधार हो सकता है। उदाहरण के लिए, जब ऊपरी और निचली सीमा के बीच का अंतर एक निश्चित सीमा से छोटा हो जाता है, तो शाखाकरण को रोकना चाह सकता है। इसका उपयोग तब किया जाता है जब समाधान व्यावहारिक उद्देश्यों के लिए पर्याप्त अच्छा होता है और आवश्यक संगणनाओं को बहुत कम कर सकता है। इस प्रकार का समाधान विशेष रूप से तब लागू होता है जब उपयोग किया जाने वाला लागत फ़ंक्शन शोर है या आंकड़ों का परिणाम है और इसलिए ठीक से ज्ञात नहीं है बल्कि केवल एक विशिष्ट संभावना वाले मूल्यों की सीमा के भीतर ही जाना जाता है।

अन्य एल्गोरिदम से संबंध

नौ एट अल। शाखा और बाउंड का एक सामान्यीकरण प्रस्तुत करता है जो A* खोज एल्गोरिद्म|A*, B* और Alpha–beta pruning|alpha-beta search एल्गोरिद्म को समाहित करता है।

अनुकूलन उदाहरण

इस समस्या को हल करने के लिए शाखा और बाउंड का उपयोग किया जा सकता है

अधिकतम $Z=5x_{1}+6x_{2}$ इन बाधाओं के साथ

$x_{1}+x_{2}\leq 50$

$4x_{1}+7x_{2}\leq 280$

$x_{1}x_{2}\geq 0$

$x_{1}$ और $x_{2}$ पूर्णांक हैं।

पहला कदम पूर्णांक बाधा को आराम देना है। एक रेखा बनाने वाले पहले समीकरण के लिए हमारे पास दो चरम बिंदु हैं: ${\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}={\begin{bmatrix}50\\0\end{bmatrix}}$ और ${\begin{bmatrix}0\\50\end{bmatrix}}$. हम सदिश बिंदुओं के साथ दूसरी पंक्ति बना सकते हैं ${\begin{bmatrix}0\\40\end{bmatrix}}$ और ${\begin{bmatrix}70\\0\end{bmatrix}}$.

दो पंक्तियाँ।

तीसरा बिंदु है ${\begin{bmatrix}0\\0\end{bmatrix}}$. यह एक उत्तल पतवार है इसलिए समाधान क्षेत्र के किसी एक कोने पर स्थित है। हम पंक्ति में कमी का उपयोग करके चौराहे का पता लगा सकते हैं, जो कि है ${\begin{bmatrix}70/3\\80/3\end{bmatrix}}$, या ${\begin{bmatrix}23.333\\26.667\end{bmatrix}}$ 276.667 के मान के साथ। हम क्षेत्र के ऊपर रेखा को स्वीप करके अन्य समापन बिंदुओं का परीक्षण करते हैं और पाते हैं कि यह वास्तविक से अधिक अधिकतम है।

इस मामले में, हम अधिकतम भिन्नात्मक भाग वाले चर को चुनते हैं $x_{2}$ शाखा और बाउंड विधि के लिए पैरामीटर बन जाता है। हम शाखा करते हैं $x_{2}\leq 26$ और 276 @ प्राप्त करें $\langle 24,26\rangle$. हम एक पूर्णांक समाधान तक पहुँच चुके हैं इसलिए हम दूसरी शाखा में जाते हैं $x_2\ge <!--\; \ge \; -->$