बैक ट्रैकिंग

यह चित्र दिखाता है, 8 - क्वेन्स पहेली की हल करने की प्रक्रिया बैकट्रैकिंग का उपयोग करके।

बैकट्रैकिंग (Backtracking) कुछ कम्प्यूटेशनल समस्याओं को हल करने के लिए एक एल्गोरिथ्म(algorithm) तकनीक है। यह समाधान खोजने के लिए पुनरावर्ती कॉलिंग (Recursive calling) का उपयोग करता है।

बैकट्रैकिंग के लिए क्लासिक उदाहरण आठ रानियों की पहेली है(8-queen puzzle), जिसमें हमें एक मानक शतरंजबोर्ड पर आठ शतरंज रानियों के सभी संभावित स्थानों को खोजना होता है ताकि कोई रानी किसी अन्य पर हमला न करे।

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

बैकट्रैकिंग के बारे में अच्छी बात यह है कि बैकट्रैकिंग अक्सर सभी पूर्ण उम्मीदवारों की ब्रूट फोर्स(brute force) गणना की तुलना में बहुत तेज है क्योंकि यह एक ही टेस्ट के साथ कई उम्मीदवारों को खत्म कर देता है।

क्रॉसरवर्ड(Crosswords), मौखिक अंकगणित(Verbal Arithmetic), सुडोकू(Sudoku), और कई अन्य पहेलियों जैसे बाधा संतुष्टि समस्याओं(Constraint satisfaction problems) को हल करने के लिए बैकट्रैकिंग एक महत्वपूर्ण उपकरण है। यह लॉजिक प्रोग्रामिंग लैंग्वेज जैसे आइकॉन(Icon), प्लानर(Planner) और प्रोलॉग(Prolog) का आधार भी है।

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

सामान्य बैकट्रैकिंग सुविधा प्रदान करने वाली पहली भाषा रही है।

विधि का वर्णन

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

वैचारिक रूप से, आंशिक उम्मीदवारों को एक पेड़ संरचना(tree structure), संभावित खोज पेड़ के नोड्स के रूप में दर्शाया जाता है। प्रत्येक आंशिक उम्मीदवार उम्मीदवारों का पूर्वज होता है जो एक विस्तार कदम से इससे भिन्न होता है; पेड़ के पत्ते आंशिक उम्मीदवार हैं जिन्हें आगे नहीं बढ़ाया जा सकता है।

बैकट्रैकिंग एल्गोरिथ्म इस खोज के पेड़ को जड़ से नीचे गहराई से पहले (depth first order)क्रम में खोजता है।

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

स्यूडोकोड

बैक ट्रैकिंग की प्रक्रिया

बैक ट्रैकिंग निस्संदेह काफी सरल है - हम प्रत्येक नोड को इस प्रकार "एक्सप्लोर" करते हैं:

"नोड एन" का पता लगाने के लिए:

1. यदि N एक लक्ष्य नोड है, तो "सफलता" लौटाएं

2. यदि एन एक पत्ती नोड है, तो "विफलता" लौटें

3. N के प्रत्येक बच्चे के लिए,

C का अन्वेषण(explore) करें

यदि C सफल रहा, तो "सफलता" लौटाएं

4. वापसी "विफलता"

जनरल स्यूडोकोड

boolean solve(Node N) {  
  
     if n is a goal node, return true  
              
     for each option M possible from N {  
  
          if solve(M) succeeds, return true  
  
     }  
  
     return false  
}

उदाहरण

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

इस छवि में, सुडोकू बैकट्रैकिंग द्वारा हल किया जा रहा है

1. पहेलियाँ जैसे

• 8 रानियाँ पहेली (8-queen puzzle)
• क्रॉसवर्ड (Crosswords)
• मौखिक अंकगणित (Verbal Arithmetic)
• सुडोकू (Sudoku)
• खूंटी त्यागी (Peg Solitaire)

2. कॉम्बिनेटरियल ऑप्टिमाइज़ेशन प्रॉब्लम्स जैसे कि

• पार्सिंग (Parsing)
• नैप्सैक समस्या (Knapsack problem)

3. लॉजिक प्रोग्रामिंग लैंग्वेज जो सॉल्यूशंस जेनरेट करने के लिए आंतरिक रूप से बैकट्रैकिंग का उपयोग करती हैं जैसे

• आइकॉन(Icon)
• प्लानर(Planner)
• प्रोलॉग(Prolog)

बाधा संतुष्टि की समस्या (Constraint satisfaction problem)

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

F = F[1] ∧ F [2] ∧ ... ∧ F [p],

और प्रत्येक F [i] केवल चर x [1],…, x [n] के छोटे उपसमूह पर निर्भर करता है।

इन्हें भी देखें

• Backjumping
• Backward chaining
• Enumeration algorithm
• Sudoku solving algorithms
• Find all The Permutations
• Knight’s Tour Problem