इस ट्यूटोरियल में, आप सीखेंगे कि बैकग्राउंडिंग एल्गोरिथ्म क्या है। साथ ही, आपको एक पीछे आने वाले दृष्टिकोण का एक उदाहरण मिलेगा।
बैकट्रैकिंग एल्गोरिथ्म एक समस्या को हल करने वाला एल्गोरिथ्म है जो वांछित आउटपुट खोजने के लिए एक क्रूर बल दृष्टिकोण का उपयोग करता है ।
ब्रूट बल दृष्टिकोण सभी संभव समाधानों को आज़माता है और वांछित / सर्वोत्तम समाधान चुनता है।
बैकट्रैकिंग शब्द बताता है कि यदि वर्तमान समाधान उपयुक्त नहीं है, तो बैकट्रैक और अन्य समाधानों का प्रयास करें। इस प्रकार, इस दृष्टिकोण में पुनरावृत्ति का उपयोग किया जाता है।
इस दृष्टिकोण का उपयोग उन समस्याओं को हल करने के लिए किया जाता है जिनमें कई समाधान होते हैं। यदि आप एक इष्टतम समाधान चाहते हैं, तो आपको गतिशील प्रोग्रामिंग के लिए जाना चाहिए।
राज्य अंतरिक्ष वृक्ष
एक अंतरिक्ष राज्य का पेड़ एक प्रारंभिक अवस्था के रूप में जड़ से एक टर्मिनल राज्य के रूप में जड़ से समस्या के सभी संभव राज्यों (समाधान या निरर्थक) का प्रतिनिधित्व करने वाला एक पेड़ है।
राज्य अंतरिक्ष वृक्ष
एल्गोरिथ्म पीछे
Backtrack (x) यदि x सॉल्यूशन रिटर्न झूठा नहीं है यदि x सॉल्यूशंस की सूची में एक नया सॉल्यूशन है तो बैकट्रैक (एक्स का विस्तार करें)
उदाहरण बैकट्रैकिंग दृष्टिकोण
समस्या: आप 3 बेंचों पर 2 लड़कों और 1 लड़की की व्यवस्था के सभी संभावित तरीकों को खोजना चाहते हैं। बाधा: लड़की को मध्य बेंच पर नहीं होना चाहिए।
समाधान: कुल 3 हैं! = 6 संभावनाएँ। हम सभी संभावनाओं का प्रयास करेंगे और संभव समाधान प्राप्त करेंगे। हम सभी संभावनाओं का पुनरावर्ती प्रयास करते हैं।
सभी संभावनाएं हैं:
सभी संभावनाएं
निम्नलिखित राज्य स्पेस ट्री संभावित समाधान दिखाता है।
सभी समाधानों के साथ राज्य का पेड़
बैकग्राउंडिंग एल्गोरिथ्म एप्लीकेशन
- एक ग्राफ में मौजूद सभी हैमिल्टन पथों को खोजने के लिए।
- एन क्वीन समस्या को हल करने के लिए।
- भूलभुलैया समस्या का समाधान।
- नाइट की दौरे की समस्या।
