बैक ट्रैकिंग
बैकट्रैकिंग कुछ कम्प्यूटेशनल समस्याओं के समाधान खोजने के लिए कलन विधि का एक वर्ग है, विशेष रूप से संतुष्टि की समस्याओं को बाधित करता है, जो उम्मीदवारों को समाधान के लिए बनाता है, और जैसे ही यह निर्धारित करता है कि उम्मीदवार को संभवतः एक वैध समाधान के लिए पूरा नहीं किया जा सकता है (बैकट्रैक) छोड़ देता है। .[1] बैकट्रैकिंग के उपयोग का क्लासिक पाठ्यपुस्तक उदाहरण आठ रानी पहेली है, जो एक मानक शतरंज की बिसात पर आठ शतरंज रानी (शतरंज) की सभी व्यवस्थाओं के लिए पूछता है ताकि कोई रानी किसी अन्य पर हमला न करे। सामान्य बैकट्रैकिंग दृष्टिकोण में, आंशिक उम्मीदवार बोर्ड की पहली k पंक्तियों में k रानियों की व्यवस्था करते हैं, सभी अलग-अलग पंक्तियों और स्तंभों में। कोई भी आंशिक समाधान जिसमें दो पारस्परिक रूप से हमलावर रानियां हों, को छोड़ दिया जा सकता है।
बैकट्रैकिंग केवल उन समस्याओं के लिए लागू किया जा सकता है जो आंशिक उम्मीदवार समाधान की अवधारणा को स्वीकार करते हैं और अपेक्षाकृत त्वरित परीक्षण करते हैं कि क्या इसे संभवतः एक वैध समाधान के लिए पूरा किया जा सकता है। उदाहरण के लिए, किसी अनियंत्रित तालिका में दिए गए मान का पता लगाने के लिए यह बेकार है। हालांकि, जब यह लागू होता है, तो बैकट्रैकिंग अक्सर सभी पूर्ण उम्मीदवारों की क्रूर-बल खोज |ब्रूट-फोर्स एन्यूमरेशन की तुलना में बहुत तेज होती है, क्योंकि यह एक ही परीक्षा के साथ कई उम्मीदवारों को खत्म कर सकती है।
बाधा संतुष्टि समस्याओं को हल करने के लिए बैकट्रैकिंग महत्वपूर्ण उपकरण है,[2] जैसे वर्ग पहेली, मौखिक अंकगणित, सुडोकू के एल्गोरिदम, और कई अन्य पहेलियाँ। यह अक्सर पदच्छेद के लिए सबसे सुविधाजनक तकनीक होती है,[3] नैकपैक समस्या और अन्य संयोजी इष्टतमीकरण समस्याओं के लिए। यह तथाकथित तर्क प्रोग्रामिंग लैंग्वेज जैसे आइकन प्रोग्रामिंग भाषा , योजनाकार प्रोग्रामिंग भाषा और प्रोलॉग का भी आधार है।
बैकट्रैकिंग उपयोगकर्ता द्वारा दिए गए प्रक्रियात्मक मापदंडों पर निर्भर करता है जो हल की जाने वाली समस्या को परिभाषित करता है, आंशिक उम्मीदवारों की प्रकृति, और उन्हें पूर्ण उम्मीदवारों में कैसे बढ़ाया जाता है। इसलिए यह विशिष्ट एल्गोरिथम के बजाय एक मेटाह्यूरिस्टिक है - हालांकि, कई अन्य मेटा-हेरिस्टिक्स के विपरीत, यह सीमित समय में एक सीमित समस्या के सभी समाधान खोजने की गारंटी है।
बैकट्रैक शब्द अमेरिकी गणितज्ञ डेरिक हेनरी लेहमर|डी द्वारा गढ़ा गया था। 1950 के दशक में एच. लेहमर।[4] अग्रणी स्ट्रिंग-प्रसंस्करण भाषा SNOBOL (1962) अंतर्निहित सामान्य बैकट्रैकिंग सुविधा प्रदान करने वाली पहली हो सकती है।
विधि का विवरण
बैकट्रैकिंग एल्गोरिदम आंशिक उम्मीदवारों के एक सेट की गणना करता है, जो सिद्धांत रूप में, दी गई समस्या के सभी संभावित समाधान देने के लिए विभिन्न तरीकों से पूरा किया जा सकता है। उम्मीदवार विस्तार चरणों के अनुक्रम द्वारा पूर्णता को वृद्धिशील रूप से किया जाता है।
संकल्पनात्मक रूप से, आंशिक उम्मीदवारों को वृक्ष संरचना, संभावित खोज वृक्ष के नोड्स के रूप में दर्शाया जाता है। प्रत्येक आंशिक उम्मीदवार उन उम्मीदवारों के माता-पिता हैं जो एक विस्तार कदम से अलग हैं; पेड़ की पत्तियाँ आंशिक उम्मीदवार हैं जिन्हें और आगे नहीं बढ़ाया जा सकता है।
बैकट्रैकिंग एल्गोरिथम इस सर्च ट्री रिकर्सन (कंप्यूटर साइंस) को जड़ से नीचे, गहराई-पहले खोज|गहराई-पहले क्रम में पार करता है। प्रत्येक नोड c पर, एल्गोरिथ्म जाँचता है कि c को एक वैध समाधान के लिए पूरा किया जा सकता है या नहीं। यदि यह नहीं हो सकता है, तो c पर निहित संपूर्ण उप-वृक्ष को छोड़ दिया जाता है (छंटनी की जाती है)। अन्यथा, एल्गोरिथ्म (1) जाँचता है कि क्या c स्वयं एक वैध समाधान है, और यदि ऐसा है तो यह उपयोगकर्ता को रिपोर्ट करता है; और (2) पुनरावर्ती रूप से c के सभी उप-वृक्षों की गणना करता है। दो परीक्षण और प्रत्येक नोड के बच्चे उपयोगकर्ता द्वारा दी गई प्रक्रियाओं द्वारा परिभाषित किए गए हैं।
इसलिए, एल्गोरिथम द्वारा ट्रैवर्स किया गया वास्तविक खोज ट्री संभावित ट्री का केवल एक हिस्सा है। एल्गोरिदम की कुल लागत प्रत्येक नोड को प्राप्त करने और संसाधित करने की लागत के वास्तविक पेड़ के नोड्स की संख्या है। संभावित खोज ट्री का चयन करते समय और छंटाई परीक्षण को लागू करते समय इस तथ्य पर विचार किया जाना चाहिए।
स्यूडोकोड
समस्याओं के एक विशिष्ट वर्ग के लिए बैकट्रैकिंग लागू करने के लिए, किसी को हल की जाने वाली समस्या के विशेष उदाहरण के लिए डेटा P प्रदान करना होगा, और छह प्रक्रियात्मक पैरामीटर, रूट, अस्वीकार, स्वीकार, पहले, अगले और आउटपुट। इन प्रक्रियाओं को उदाहरण डेटा पी को पैरामीटर के रूप में लेना चाहिए और निम्न कार्य करना चाहिए:
- रूट (पी): आंशिक उम्मीदवार को खोज पेड़ की जड़ में वापस कर दें।
- अस्वीकार (पी, सी): आंशिक उम्मीदवार सी पूरा होने के लायक नहीं होने पर ही सही लौटें।
- स्वीकार करें (पी, सी): यदि सी पी का समाधान है, और अन्यथा गलत है तो सही लौटें।
- पहला (पी, सी): उम्मीदवार सी का पहला विस्तार उत्पन्न करें।
- अगला (पी, एस): एक्सटेंशन एस के बाद उम्मीदवार का अगला वैकल्पिक एक्सटेंशन उत्पन्न करें।
- आउटपुट (पी, सी): आवेदन के लिए उपयुक्त पी के समाधान सी का उपयोग करें।
बैकट्रैकिंग एल्गोरिदम समस्या को कॉल बैकट्रैक (रूट (पी)) में कम कर देता है, जहां बैकट्रैक निम्नलिखित पुनरावर्ती प्रक्रिया है:
procedure backtrack(P, c) is
if reject(P, c) then return
if accept(P, c) then output(P, c)
s ← first(P, c)
while s ≠ NULL do
backtrack(P, s)
s ← next(P, s)
उपयोग विचार
अस्वीकार प्रक्रिया बूलियन-मूल्यवान फ़ंक्शन होना चाहिए जो केवल तभी सत्य लौटाता है जब यह निश्चित हो कि सी का कोई संभावित विस्तार पी के लिए वैध समाधान नहीं है। यदि प्रक्रिया निश्चित निष्कर्ष तक नहीं पहुंच पाती है, तो उसे झूठी वापसी करनी चाहिए। एक गलत सही परिणाम के कारण बैकट्रैक प्रक्रिया कुछ वैध समाधानों को याद कर सकती है। प्रक्रिया यह मान सकती है कि खोज ट्री में c के प्रत्येक पूर्वज t के लिए अस्वीकार (P, t) गलत है।
दूसरी ओर, बैकट्रैकिंग एल्गोरिदम की दक्षता उन उम्मीदवारों के लिए रिजेक्ट रिटर्निंग ट्रू पर निर्भर करती है जो रूट के जितना संभव हो उतना करीब हैं। यदि अस्वीकार हमेशा गलत होता है, तो एल्गोरिथ्म अभी भी सभी समाधान खोजेगा, लेकिन यह क्रूर-बल खोज के बराबर होगा।
यदि c समस्या उदाहरण P के लिए एक पूर्ण और वैध समाधान है, और अन्यथा गलत है, तो स्वीकार करने की प्रक्रिया सही होनी चाहिए। यह माना जा सकता है कि पेड़ में आंशिक उम्मीदवार सी और उसके सभी पूर्वजों ने अस्वीकार परीक्षण पास कर लिया है।
उपरोक्त सामान्य छद्म कोड यह नहीं मानता है कि वैध समाधान हमेशा संभावित खोज वृक्ष के पत्ते होते हैं। दूसरे शब्दों में, यह संभावना को स्वीकार करता है कि पी के लिए एक वैध समाधान को अन्य वैध समाधान प्राप्त करने के लिए आगे बढ़ाया जा सकता है।
पेड़ के नोड सी के बच्चों की गणना करने के लिए बैकट्रैकिंग एल्गोरिदम द्वारा पहली और अगली प्रक्रियाओं का उपयोग किया जाता है, यानी उम्मीदवार जो एकल विस्तार चरण से सी से भिन्न होते हैं। पहले कॉल (पी, सी) को किसी क्रम में सी के पहले बच्चे को उत्पन्न करना चाहिए; और अगले कॉल (पी, एस) को उस क्रम में नोड एस के अगले भाई को वापस करना चाहिए। यदि अनुरोधित बच्चा मौजूद नहीं है, तो दोनों कार्यों को विशिष्ट NULL उम्मीदवार वापस करना चाहिए।
साथ में, रूट, पहले और अगले फ़ंक्शन आंशिक उम्मीदवारों के सेट और संभावित खोज ट्री को परिभाषित करते हैं। उन्हें चुना जाना चाहिए ताकि पी का हर समाधान पेड़ में कहीं हो, और कोई आंशिक उम्मीदवार एक से अधिक बार न हो। इसके अलावा, उन्हें कुशल और प्रभावी अस्वीकार विधेय को स्वीकार करना चाहिए।
शुरुआती स्टॉपिंग वेरिएंट
उपरोक्त छद्म कोड उन सभी उम्मीदवारों के लिए आउटपुट कॉल करेगा जो दिए गए उदाहरण पी के समाधान हैं। एल्गोरिदम को पहला समाधान, या समाधानों की एक निर्दिष्ट संख्या खोजने के बाद रोकने के लिए संशोधित किया जा सकता है; या आंशिक उम्मीदवारों की एक निर्दिष्ट संख्या का परीक्षण करने के बाद, या केंद्रीय प्रसंस्करण इकाई समय की एक निश्चित राशि खर्च करने के बाद।
उदाहरण
उदाहरण जहां पहेलियों या समस्याओं को हल करने के लिए बैकट्रैकिंग का उपयोग किया जा सकता है:
- आठ रानियों की पहेली, वर्ग पहेली, मौखिक अंकगणित, सुडोकू के एल्गोरिदम जैसी पहेलियाँ[nb 1], और पेग सॉलिटेयर।
- मिश्रित अनुकूलन समस्याएं जैसे पार्सिंग और नैपसैक समस्या।
- लॉजिक प्रोग्रामिंग लैंग्वेज जैसे आइकॉन प्रोग्रामिंग लैंग्वेज, प्लानर प्रोग्रामिंग लैंग्वेज और प्रोलॉग, जो उत्तर उत्पन्न करने के लिए आंतरिक रूप से बैकट्रैकिंग का उपयोग करते हैं।
निम्नलिखित उदाहरण है जहां बाधा संतुष्टि समस्या के लिए बैकट्रैकिंग का उपयोग किया जाता है:
बाधा संतुष्टि
सामान्य बाधा संतुष्टि समस्या में पूर्णांकों की सूची प्राप्त करना शामिल है x = (x[1], x[2], …, x[n]), प्रत्येक किसी सीमा में {1, 2, …, m}, जो कुछ मनमाना बाधा (बूलियन फ़ंक्शन) F को संतुष्ट करता है।
समस्याओं के इस वर्ग के लिए, उदाहरण डेटा P पूर्णांक m और n होगा, और विधेय F होगा। इस समस्या के एक विशिष्ट बैकट्रैकिंग समाधान में, कोई आंशिक उम्मीदवार को पूर्णांकों की सूची के रूप में परिभाषित कर सकता है c = (c[1], c[2], …, c[k]), 0 और n के बीच किसी भी k के लिए, जिसे पहले k वेरिएबल्स को असाइन किया जाना है x[1], x[2], …, x[k]. मूल उम्मीदवार तब खाली सूची () होगी। इसके बाद पहली और अगली प्रक्रिया होगी
'कार्य' पहले (पी, सी) 'है'
के ← लंबाई (सी)
'अगर' के = एन 'फिर'
'वापसी' शून्य
'अन्य'
'वापसी' (सी[1], सी[2], ..., सी[के], 1)
'फ़ंक्शन' अगला (पी, एस) 'है'
कश्मीर ← लंबाई (ओं)
'अगर' एस [के] = एम 'फिर'
'वापसी' शून्य
'अन्य'
'रिटर्न' (s[1], s[2], ..., s[k − 1], 1 + s[k])
यहां लंबाई (सी) सूची सी में तत्वों की संख्या है।
कॉल अस्वीकार (पी, सी) को सही होना चाहिए यदि बाधा एफ एन पूर्णांक की किसी भी सूची से संतुष्ट नहीं हो सकती है जो सी के के तत्वों से शुरू होती है। बैकट्रैकिंग प्रभावी होने के लिए, इस स्थिति का पता लगाने का तरीका होना चाहिए, कम से कम कुछ उम्मीदवारों के लिए, उन सभी मी की गणना किए बिनाn − k n-टुपल्स।
उदाहरण के लिए, यदि F कई बूलियन विधेय का तार्किक संयोजन है, F = F[1] ∧ F[2] ∧ … ∧ F[p], और प्रत्येक F[i] केवल चरों के छोटे उपसमुच्चय पर निर्भर करता है x[1], …, x[n], तो अस्वीकार करने की प्रक्रिया केवल F [i] की शर्तों की जांच कर सकती है जो केवल चर पर निर्भर करती है x[1], …, x[k], और अगर उनमें से कोई भी शब्द गलत रिटर्न देता है तो सही रिटर्न देता है। वास्तव में, अस्वीकार करने की आवश्यकता केवल उन शर्तों की जांच करती है जो x [k] पर निर्भर करती हैं, क्योंकि वे शब्द जो केवल निर्भर करते हैं x[1], …, x[k − 1] का आगे सर्च ट्री में परीक्षण किया गया होगा।
यह मानते हुए कि अस्वीकार ऊपर के रूप में लागू किया गया है, फिर स्वीकार करें (पी, सी) को केवल यह जांचने की आवश्यकता है कि क्या सी पूर्ण है, अर्थात इसमें एन तत्व हैं या नहीं।
आम तौर पर चरों की सूची को क्रमबद्ध करना बेहतर होता है ताकि यह सबसे महत्वपूर्ण लोगों से शुरू हो (यानी सबसे कम मूल्य विकल्पों वाले, या जो बाद के विकल्पों पर अधिक प्रभाव डालते हैं)।
कोई भी अगले फ़ंक्शन को यह चुनने की अनुमति दे सकता है कि आंशिक उम्मीदवार को विस्तारित करते समय कौन सा चर असाइन किया जाना चाहिए, इसके द्वारा पहले से असाइन किए गए चर के मानों के आधार पर। बाधा प्रचार की तकनीक से और सुधार प्राप्त किए जा सकते हैं।
बैकअप में उपयोग किए जाने वाले न्यूनतम पुनर्प्राप्ति मूल्यों को बनाए रखने के अलावा, बैकट्रैकिंग कार्यान्वयन आमतौर पर मूल्य परिवर्तन इतिहास को रिकॉर्ड करने के लिए एक चर निशान रखते हैं। कुशल कार्यान्वयन दो लगातार परिवर्तनों के बीच एक चर निशान प्रविष्टि बनाने से बच जाएगा, जब कोई विकल्प बिंदु नहीं होगा, क्योंकि बैकट्रैकिंग एक ही ऑपरेशन के रूप में सभी परिवर्तनों को मिटा देगा।
वेरिएबल ट्रेल का विकल्प एक TIMESTAMP रखना है जब वेरिएबल में आखिरी बदलाव किया गया था। टाइमस्टैम्प की तुलना पसंद बिंदु के टाइमस्टैम्प से की जाती है। यदि पसंद बिंदु का संबद्ध समय बाद में चर की तुलना में है, तो पसंद बिंदु के पीछे जाने पर चर को वापस करना अनावश्यक है, क्योंकि यह विकल्प बिंदु होने से पहले बदल दिया गया था।
यह भी देखें
- एरिडेन का धागा (तर्क)
- पीछे कूदना
- बैकवर्ड चेनिंग
- गणना एल्गोरिथ्म
- सुडोकू हल करने वाले एल्गोरिदम
टिप्पणियाँ
संदर्भ
- ↑ Gurari, Eitan (1999). "CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms". Archived from the original on 17 March 2007.
- ↑ Biere, A.; Heule, M.; van Maaren, H. (29 January 2009). संतुष्टि की पुस्तिका. IOS Press. ISBN 978-1-60750-376-7.
- ↑ Watson, Des (22 March 2017). संकलक निर्माण के लिए एक व्यावहारिक दृष्टिकोण. Springer. ISBN 978-3-319-52789-5.
- ↑ Rossi, Francesca; van Beek, Peter; Walsh, Toby (August 2006). "Constraint Satisfaction: An Emerging Paradigm". Handbook of Constraint Programming. Amsterdam: Elsevier. p. 14. ISBN 978-0-444-52726-4. Retrieved 30 December 2008.
अग्रिम पठन
- Gilles Brassard, Paul Bratley (1995). Fundamentals of Algorithmics. Prentice-Hall. ISBN 9780133350685.
बाहरी संबंध
- HBmeyer.de, Interactive animation of a backtracking algorithm
- Solving Combinatorial Problems with STL and Backtracking, Article and C++ source code for a generic implementation of backtracking
