बैक ट्रैकिंग

For लाइन खोज एल्गोरिदम अप्रतिबंधित अनुकूलन में उपयोग किया जाता है, see बैकट्रैकिंग लाइन खोज.

अप्रतिबंधित अनुकूलन में प्रयुक्त लाइन खोज कलन विधि के लिए, बैकट्रैकिंग लाइन खोज देखें। बैकट्रैकिंग कुछ कम्प्यूटेशनल समस्याओ के समाधान खोजने के लिए कलन विधि का एक वर्ग है, विशेष रूप से यह संतुष्टि की समस्याओं को बाधित करता है जो उम्मीदवारों को समाधान के लिए बनाता है और एक उम्मीदवार ("बैकट्रैक्स") को छोड़ देता है जैसे ही यह निर्धारित करता है कि उम्मीदवार संभवतः एक वैध समाधान के लिए पूरा नहीं किया जा सकता है।

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

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

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

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

शब्द "बैकट्रैक" 1950 के दशक में अमेरिकी गणितज्ञ डी. एच. लेहमर द्वारा गढ़ा गया था। अग्रणी स्ट्रिंग-प्रसंस्करण भाषा स्नोबोल (1962) अंतर्निहित सामान्य बैकट्रैकिंग सुविधा प्रदान करने वाली पहली हो सकती है।

विधि का विवरण

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

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

बैकट्रैकिंग एल्गोरिथ्म इस खोज ट्री को गहराई से पहले क्रम में जड़ से नीचे तक पुनरावर्ती रूप से पार करता है। प्रत्येक नोड c पर एल्गोरिथ्म जाँचता है कि क्या c को एक वैध समाधान के लिए पूरा किया जा सकता है। यदि यह नहीं हो सकता है तो सी पर जड़ वाले पूरे उप-वृक्ष को छोड़ दिया जाता है (काट दिया जाता है)। अन्यथा एल्गोरिथ्म (1) जाँचता है कि क्या c स्वयं एक वैध समाधान है और यदि ऐसा है तो यह उपयोगकर्ता को रिपोर्ट करता है और (2) पुनरावर्ती रूप से c के सभी उप-वृक्षों की गणना करता है। दो परीक्षण और प्रत्येक नोड के बच्चे उपयोगकर्ता द्वारा दी गई प्रक्रियाओं द्वारा परिभाषित किए गए हैं।

इसलिए, एल्गोरिथम द्वारा ट्रैवर्स किया गया वास्तविक खोज ट्री संभावित ट्री का केवल एक भाग है। कलन विधि की कुल लागत प्रत्येक नोड को प्राप्त करने और संसाधित करने की लागत के वास्तविक पेड़ के नोड्स की संख्या है। संभावित खोज ट्री का चयन करते समय और छंटाई परीक्षण को प्रायुक्त करते समय इस तथ्य पर विचार किया जाना चाहिए।

स्यूडोकोड

समस्याओं के एक विशिष्ट वर्ग के लिए बैकट्रैकिंग प्रायुक्त करने के लिए, किसी को हल की जाने वाली समस्या के विशेष उदाहरण के लिए डेटा P प्रदान करना होगा, और छह प्रक्रियात्मक पैरामीटर, रूट, अस्वीकार, पहले, अगले और आउटपुट को स्वीकार करते हैं। इन प्रक्रियाओं को उदाहरण डेटा P को पैरामीटर के रूप में लेना चाहिए और निम्न कार्य करना चाहिए:

1. रूट (P): आंशिक उम्मीदवार को खोज पेड़ की जड़ में वापस कर दें।
2. अस्वीकार (P, c): आंशिक उम्मीदवार c पूरा होने के लायक नहीं होने पर ही सही लौटें।
3. स्वीकार करें (P, c): यदि c P का समाधान है, और अन्यथा गलत है तो सही लौटें।
4. पहला (P, c): उम्मीदवार c का पहला विस्तार उत्पन्न करें।
5. अगला (P, S): एक्सटेंशन S के बाद उम्मीदवार का अगला वैकल्पिक एक्सटेंशन उत्पन्न करें।
6. आउटपुट (P, c): आवेदन के लिए उपयुक्त P के समाधान 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 का कोई संभावित विस्तार P के लिए वैध समाधान नहीं है। यदि प्रक्रिया निश्चित निष्कर्ष तक नहीं पहुंच पाती है, तो उसे झूठी वापसी करनी चाहिए। एक गलत सही परिणाम के कारण बैकट्रैक प्रक्रिया कुछ वैध समाधानों को याद कर सकती है। प्रक्रिया यह मान सकती है कि खोज ट्री में c के प्रत्येक पूर्वज t के लिए अस्वीकार (P, t) गलत है।

दूसरी ओर, बैकट्रैकिंग कलन विधि की दक्षता उन उम्मीदवारों के लिए रिजेक्ट रिटर्निंग ट्रू पर निर्भर करती है जो रूट के जितना संभव हो उतना करीब हैं। यदि अस्वीकार हमेशा गलत होता है, तो एल्गोरिथ्म अभी भी सभी समाधान खोजेगा, लेकिन यह क्रूर-बल खोज के बराबर होगा।

यदि c समस्या उदाहरण P के लिए एक पूर्ण और वैध समाधान है, और अन्यथा गलत है, तो स्वीकार करने की प्रक्रिया सही होनी चाहिए। यह माना जा सकता है कि पेड़ में आंशिक उम्मीदवार c और उसके सभी पूर्वजों ने अस्वीकार परीक्षण पास कर लिया है।

उपरोक्त सामान्य छद्म कोड यह नहीं मानता है कि वैध समाधान हमेशा संभावित खोज वृक्ष के पत्ते होते हैं। दूसरे शब्दों में, यह संभावना को स्वीकार करता है कि P के लिए एक वैध समाधान को अन्य वैध समाधान प्राप्त करने के लिए आगे बढ़ाया जा सकता है।

पेड़ के नोड c के बच्चों की गणना करने के लिए बैकट्रैकिंग कलन विधि द्वारा पहली और अगली प्रक्रियाओं का उपयोग किया जाता है, अर्थात् उम्मीदवार जो एकल विस्तार चरण से c से भिन्न होते हैं। पहले कॉल (P, c) को किसी क्रम में c के पहले बच्चे को उत्पन्न करना चाहिए; और अगले कॉल (P, S) को उस क्रम में नोड S के अगले भाई को वापस करना चाहिए। यदि अनुरोधित बच्चा उपस्थित नहीं है, तो दोनों कार्यों को विशिष्ट शून्य उम्मीदवार वापस करना चाहिए।

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

प्रारंभिक स्टॉपिंग वेरिएंट

उपरोक्त छद्म कोड उन सभी उम्मीदवारों के लिए आउटपुट कॉल करेगा जो दिए गए उदाहरण P के समाधान हैं। कलन विधि को पहला समाधान, या समाधानों की एक निर्दिष्ट संख्या खोजने के बाद रोकने के लिए संशोधित किया जा सकता है; या आंशिक उम्मीदवारों की एक निर्दिष्ट संख्या का परीक्षण करने के बाद, या केंद्रीय प्रसंस्करण इकाई समय की एक निश्चित राशि खर्च करने के बाद।

उदाहरण

बैकट्रैकिंग द्वारा हल किया गया एक सुडोकू।

उदाहरण जहां पहेलियों या समस्याओं को हल करने के लिए बैकट्रैकिंग का उपयोग किया जा सकता है:

• आठ रानियों की पहेली, वर्ग पहेली, मौखिक अंकगणित, सुडोकू के कलन विधि जैसी पहेलियाँ, और पेग सॉलिटेयर।
• मिश्रित अनुकूलन समस्याएं जैसे पार्सिंग और नैपसैक समस्या।
• लॉजिक प्रोग्रामिंग भाषा जैसे आइकॉन प्रोग्रामिंग भाषा, प्लानर प्रोग्रामिंग भाषा और प्रोलॉग, जो उत्तर उत्पन्न करने के लिए आंतरिक रूप से बैकट्रैकिंग का उपयोग करते हैं।

निम्नलिखित उदाहरण है जहां बाधा संतुष्टि समस्या के लिए बैकट्रैकिंग का उपयोग किया जाता है:

बाधा संतुष्टि

सामान्य बाधा संतुष्टि समस्या में पूर्णांकों x = (x[1], x[2], …, x[n]) की सूची प्राप्त करना शामिल है, प्रत्येक किसी सीमा में {1, 2, …, m}, जो कुछ मनमाना बाधा (बूलियन फलन) F को संतुष्ट करता है।

समस्याओं के इस वर्ग के लिए, उदाहरण डेटा P पूर्णांक m और n होगा, और विधेय F होगा। इस समस्या के एक विशिष्ट बैकट्रैकिंग समाधान में, कोई आंशिक उम्मीदवार को 0 और n के बीच किसी भी k के लिए पूर्णांकों c = (c[1], c[2], …, c[k]) की सूची के रूप में परिभाषित कर सकता है, जिसे पहले k वेरिएबल्स x[1], x[2], …, x[k] को असाइन किया जाना है। मूल उम्मीदवार तब खाली सूची () होगी। इसके बाद पहली और अगली प्रक्रिया होगी

function first(P, c) is
    k ← length(c)
    if k = n then
        return NULL
    else
        return (c[1], c[2], …, c[k], 1)

function next(P, s) is
    k ← length(s)
    if s[k] = m then
        return NULL
    else
        return (s[1], s[2], …, s[k − 1], 1 + s[k])

यहां लंबाई (c) सूची c में तत्वों की संख्या है।

कॉल अस्वीकार (P, c) को सही होना चाहिए यदि बाधा एफ एन पूर्णांक की किसी भी सूची से संतुष्ट नहीं हो सकती है जो c के के तत्वों से प्रारंभ होती है। बैकट्रैकिंग प्रभावी होने के लिए कम से कम कुछ उम्मीदवारों के लिए, उन सभी m^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] पर निर्भर करते हैं, और उनका आगे सर्च ट्री में परीक्षण किया गया होगा।

यह मानते हुए कि अस्वीकार ऊपर के रूप में प्रायुक्त किया गया है, फिर स्वीकार करें (P, c) को केवल यह जांचने की आवश्यकता है कि क्या c पूर्ण है, अर्थात इसमें एन तत्व हैं या नहीं हैं।

सामान्यतः चरों की सूची को क्रमबद्ध करना उत्तम होता है ताकि यह सबसे महत्वपूर्ण लोगों से प्रारंभ हो (अर्थात् सबसे कम मान विकल्पों वाले, या जो बाद के विकल्पों पर अधिक प्रभाव डालते हैं)।

कोई भी अगले फलन को यह चुनने की अनुमति दे सकता है कि पहले से ही असाइन किए गए चर के मानों के आधार पर आंशिक उम्मीदवार को विस्तारित करते समय किस चर को असाइन किया जाना चाहिए। बाधा प्रचार की विधि से और सुधार प्राप्त किए जा सकते हैं।

बैकअप में उपयोग किए जाने वाले न्यूनतम पुनर्प्राप्ति मानों को बनाए रखने के अतिरिक्त, बैकट्रैकिंग कार्यान्वयन सामान्यतः मान परिवर्तन इतिहास को रिकॉर्ड करने के लिए एक चर निशान रखते हैं। कुशल कार्यान्वयन दो लगातार परिवर्तनों के बीच एक चर निशान प्रविष्टि बनाने से बच जाएगा, जब कोई विकल्प बिंदु नहीं होगा, क्योंकि बैकट्रैकिंग एक ही ऑपरेशन के रूप में सभी परिवर्तनों को मिटा देगा।

वेरिएबल ट्रेल का विकल्प एक टाइमस्टैम्प रखना है जब वेरिएबल में आखिरी बदलाव किया गया था। टाइमस्टैम्प की तुलना पसंद बिंदु के टाइमस्टैम्प से की जाती है। यदि पसंद बिंदु का संबद्ध समय बाद में चर की तुलना में है, तो पसंद बिंदु के पीछे जाने पर चर को वापस करना अनावश्यक है, क्योंकि यह विकल्प बिंदु होने से पहले बदल दिया गया था।

यह भी देखें

• एरिडेन का धागा (तर्क)
• पीछे कूदना
• बैकवर्ड चेनिंग
• गणना एल्गोरिथ्म
• सुडोकू हल करने वाले कलन विधि

अग्रिम पठन

• 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