बैकट्रैकिंग और ब्रांच एंड बाउंड

बैकट्रैकिंग और ब्रांच एंड बाउंड व्यवस्थित खोज प्रतिमान हैं जो उम्मीदवार समाधानों के स्थान को एक वृक्ष के रूप में खोजते हैं, उन उपवृक्षों को छांटते हैं जो एक वैध या इष्टतम समाधान तक नहीं ले जा सकते हैं ताकि अन्यथा घातीय खोजों को व्यवहार में साध्य बनाया जा सके।

Definition

बैकट्रैकिंग आंशिक उम्मीदवार समाधानों के वृक्ष की एक गहराई-पहली खोज है जो उस क्षण एक शाखा को छांट देती है जब आंशिक उम्मीदवार को एक वैध समाधान के लिए पूरा नहीं किया जा सकता है; ब्रांच एंड बाउंड इसे उद्देश्य पर संख्यात्मक सीमाओं के साथ बढ़ाता है ताकि उन शाखाओं को छोड़ दिया जा सके जिनका सर्वोत्तम संभव मान वर्तमान को नहीं हरा सकता है।

Scope

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

Core questions

• किसी समस्या के समाधान स्थान को आंशिक असाइनमेंट के खोज वृक्ष के रूप में कैसे प्रतिरूपित किया जाता है?
• कौन से बाधा जांच बैकट्रैकिंग को अक्षम शाखाओं को जल्दी छांटने देती हैं?
• अनुकूलन में शाखाओं को छांटने के लिए निचली और ऊपरी सीमाओं की गणना कैसे की जाती है?
• ब्रांचिंग और बाउंडिंग ऑर्डर व्यावहारिक प्रदर्शन को कैसे प्रभावित करते हैं?
• सबसे खराब स्थिति में घातीय होने के बावजूद इन विधियों का उपयोग NP-कठिन समस्याओं के लिए क्यों किया जाता है?

Key concepts

• खोज वृक्ष
• गहराई-पहली खोज
• बाधा प्रसार
• छंटाई
• बाउंडिंग फ़ंक्शन
• वर्तमान समाधान
• N-क्वीन्स समस्या
• पूर्णांक प्रोग्रामिंग रिलैक्सेशन

Key theories

खोज वृक्ष की छंटाई

दोनों प्रतिमान उम्मीदवार समाधानों को एक वृक्ष के रूप में व्यवस्थित करते हैं जिसे गहराई-पहली खोजा जाता है; शुद्धता संपूर्णता से आती है, जबकि दक्षता उन उपवृक्षों को छांटने से आती है जिनमें सिद्ध रूप से एक वैध या सुधारने वाला समाधान नहीं हो सकता है।

ब्रांच एंड बाउंड में बाउंडिंग फ़ंक्शन

ब्रांच एंड बाउंड अब तक पाए गए सर्वोत्तम समाधान और प्रत्येक उपवृक्ष में प्राप्त होने वाले सर्वोत्तम मान पर एक सीमा (जैसे एक LP रिलैक्सेशन) को बनाए रखता है; एक उपवृक्ष को तब छोड़ दिया जाता है जब उसकी सीमा वर्तमान पर सुधार नहीं कर सकती है।

Clinical relevance

ब्रांच एंड बाउंड संचालन अनुसंधान में सटीक संयोजनात्मक अनुकूलन की रीढ़ है, जिसमें शेड्यूलिंग, रूटिंग और योजना के लिए उपयोग किए जाने वाले पूर्णांक और मिश्रित-पूर्णांक प्रोग्रामिंग सॉल्वर शामिल हैं। बैकट्रैकिंग बाधा सॉल्वर, SAT-शैली खोज, पहेली सॉल्वर और पार्सर का आधार है, जहाँ छंटाई के साथ व्यवस्थित खोज सटीक उत्तरों का व्यावहारिक मार्ग है।

History

बैकट्रैकिंग को 1950 और 1960 के दशक में एक सामान्य तकनीक के रूप में व्यवस्थित किया गया था, विशेष रूप से गोलोम्ब और बॉमर्ट द्वारा वर्णित किया गया था। ब्रांच एंड बाउंड को 1960 में आइल्सा लैंड और एलिसन डॉइग द्वारा पूर्णांक रैखिक प्रोग्रामिंग के लिए पेश किया गया था और तब से यह संयोजनात्मक अनुकूलन के लिए केंद्रीय बन गया है, जो आधुनिक मिश्रित-पूर्णांक प्रोग्रामिंग सॉल्वर को शक्ति प्रदान करता है।

Key figures

• Ailsa Land
• Alison Doig
• Solomon Golomb
• Robert Bixby

Seminal works

• landdoig1960
• cormen2009

Frequently asked questions

बैकट्रैकिंग और ब्रांच एंड बाउंड में क्या अंतर है?

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

यदि ये विधियाँ सबसे खराब स्थिति में घातीय हैं, तो उनका उपयोग क्यों करें?

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