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

बैकट्रैकिंग समस्या को हल करने के लिए एल्गोरिदम पर आधारित एक तकनीक है। यह समय के साथ बढ़ते हुए मूल्यों द्वारा समाधान चरण बनाकर समाधान खोजने के लिए पुनरावर्ती कॉलिंग का उपयोग करता है। यह उन समाधानों को हटा देता है जो समस्या को हल करने के लिए दी गई बाधाओं के आधार पर समस्या के समाधान को जन्म नहीं देते हैं।

बैकट्रैकिंग एल्गोरिथम कुछ विशिष्ट प्रकार की समस्याओं पर लागू होता है,

• निर्णय समस्या समस्या का एक व्यवहार्य समाधान खोजने के लिए प्रयोग किया जाता है।

• सबसे अच्छा समाधान खोजने के लिए उपयोग की जाने वाली अनुकूलन समस्या जिसे लागू किया जा सकता है।

• समस्या के सभी व्यवहार्य समाधानों के सेट को खोजने के लिए उपयोग की जाने वाली गणना समस्या।

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

उदाहरण,

यहाँ,

हरा प्रारंभ बिंदु है, नीला मध्यवर्ती बिंदु है, लाल ऐसे बिंदु हैं जिनका कोई व्यवहार्य समाधान नहीं है, गहरा हरा अंत समाधान है।

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

एल्गोरिदम

Step 1 − if current_position is goal, return success
Step 2 − else,
Step 3 − if current_position is an end point, return failed.
Step 4 − else, if current_position is not end point, explore and repeat above steps.

आइए इस बैकट्रैकिंग समस्या का उपयोग एन-क्वीन समस्या का समाधान खोजने के लिए करें ।

N-Queen समस्या में, हमें एक NxN शतरंज की बिसात दी जाती है और हमें n रानियों को बोर्ड पर इस प्रकार रखना होता है कि कोई भी दो रानियाँ एक दूसरे पर आक्रमण न करें। एक रानी दूसरी रानी पर हमला करेगी यदि उसे उसके रास्ते में क्षैतिज, ऊर्ध्वाधर या विकर्ण बिंदुओं पर रखा जाए। यहां, हम 4-क्वीन प्रॉब्लम करेंगे।

यहाँ, समाधान है -

यहां, n क्वीन समस्या के लिए बाइनरी आउटपुट 1 के साथ क्वीन्स टू पोजीशन रखा गया है।

{0 , 1 , 0 , 0}
{0 , 0 , 0 , 1}
{1 , 0 , 0 , 0}
{0 , 0 , 1 , 0}

n रानियों की समस्या को हल करने के लिए, हम रानी को एक पंक्ति में विभिन्न स्थितियों में रखने का प्रयास करेंगे। और जाँचता है कि क्या यह अन्य रानियों से टकराता है। यदि रानियों की वर्तमान स्थिति कोई दो रानियाँ एक दूसरे पर आक्रमण कर रही हैं। यदि वे हमला कर रहे हैं, तो हम रानी के पिछले स्थान पर वापस आ जाएंगे और उसकी स्थिति बदल देंगे। और फिर से रानी का संघर्ष देखें।

एल्गोरिदम

Step 1 − Start from 1st position in the array.
Step 2 − Place queens in the board and check. Do,
   Step 2.1 − After placing the queen, mark the position as a part of the solution and then recursively check if this will lead to a solution.
   Step 2.2 − Now, if placing the queen doesn’t lead to a solution and trackback and go to step (a) and place queens to other rows.
   Step 2.3 − If placing queen returns a lead to solution return TRUE.
Step 3 − If all queens are placed return TRUE.
Step 4 − If all rows are tried and no solution is found, return FALSE.

अब, भूलभुलैया में चूहे . को हल करने के लिए बैकट्रैकिंग का उपयोग करें समस्या -

एक भूलभुलैया समस्या में चूहे में, हम एक एनएक्सएन भूलभुलैया के साथ हैं जो भूलभुलैया की पहली स्थिति है यानी [0] [0] और सरणी की स्थिति [एन -1] [एन -1] पर समाप्त होगी। इस रास्ते में कुछ ऐसी भी सड़कें हैं जिनका कोई हल नहीं निकलता है।

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

नीचे दिया गया 2D सरणी दिखाता है कि समस्या कैसी दिखती है।

यहाँ धराशायी रेखाएँ यात्रा का मार्ग दिखाती हैं।