बैकट्रैकिंग एल्गोरिदम

बैकट्रैकिंग एल्गोरिदम क्या है?

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

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

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

बैकट्रैकिंग एल्गोरिदम कैसे काम करता है?

बैकट्रैकिंग एल्गोरिदम एक समस्या-समाधान तकनीक है जिसमें चरण दर चरण वैध समाधान खोजना शामिल है। यदि किसी चरण की बाध्यताएँ कुछ शर्तों को पूरा नहीं करती हैं, तो एल्गोरिदम पिछले चरण पर वापस लौटता है।

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

किसी समस्या को हल करने के लिए बैकट्रैकिंग एल्गोरिथ्म में सामान्यतः निम्नलिखित चरण होते हैं:

चरण 1) आरंभीकरण: प्रारंभिक खाली/आंशिक समाधान से शुरुआत करें।

चरण 2) चयनविशिष्ट मानदंडों और बाधाओं के आधार पर, वर्तमान समाधान का विस्तार करने के लिए एक विकल्प का चयन करें।

चरण 3) अन्वेषणचुने हुए उम्मीदवार पर विचार करके और समस्या-समाधान प्रक्रिया में आगे बढ़ते हुए पुनरावर्ती समाधान करें।

चरण 4) बाधा जाँच: जाँच करें कि क्या वर्तमान आंशिक समाधान हर चरण में किसी भी प्रतिबंध का उल्लंघन करता है। यदि ऐसा है, तो पिछले चरण पर वापस जाएँ और एक अलग उम्मीदवार का प्रयास करें।

चरण 5) समाप्तिबैकट्रैकिंग प्रक्रिया तब रुक जाती है जब या तो कोई वैध समाधान मिल जाता है, या सभी संयोजन समाप्त हो जाते हैं।

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

चरण 7) दोहराएँसमस्या का समाधान होने या सभी विकल्पों का पता लगाने तक इन चरणों को जारी रखें।

बैकट्रैकिंग एल्गोरिदम की पुनरावर्ती प्रकृति

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

def find_solutions(n, other_params):
    if found_a_solution():
        increment_solutions_found()
        display_solution()
        if solutions_found >= solution_target:
            exit_program()
        return	

    for val in range(first, last+1):
        if is_valid(val, n):
            apply_value(val, n)
            find_solutions(n + 1, other_params)
            remove_value(val, n)

बैकट्रैकिंग समस्याओं से संबंधित सामान्य शब्द

बैकट्रैकिंग तकनीक से संबंधित कुछ बुनियादी शब्द इस प्रकार हैं:

समाधान वेक्टर: समाधानों को n-टपल के रूप में प्रदर्शित करता है, जैसे (X1, X2, …, Xn).
की कमी: X मानों को सीमित करने वाले नियम, अंतर्निहित और स्पष्ट।
समाधान स्थान: स्पष्ट प्रतिबंधों को संतुष्ट करने वाले सभी वैध X मान।
राज्य अंतरिक्ष वृक्ष: समाधान स्थान को वृक्ष के रूप में दर्शाता है।
राज्य स्थान: राज्य स्थान वृक्ष में पथों का वर्णन करता है।
समस्या की स्थितिखोज वृक्ष में नोड्स जो आंशिक समाधान दर्शाते हैं।
समाधान राज्यएस में वैध समाधान ट्यूपल बनाने वाली स्थितियाँ।
उत्तर राज्यअंतर्निहित बाधाओं को संतुष्ट करें और वांछित समाधान प्राप्त करें।
आशाजनक नोड: वांछित समाधान की ओर ले जाता है और व्यवहार्य रहता है।
गैर-आशाजनक नोड: अव्यवहार्य स्थितियों की ओर ले जाता है, जिसका आगे अन्वेषण नहीं किया जाता।
लाइव नोड: अज्ञात बच्चों के साथ उत्पन्न.
ई-नोड: चालू चाइल्ड जेनरेशन के साथ लाइव नोड.
मृत नोड: उत्पन्न सभी बच्चों का आगे कोई विस्तार नहीं।
गहराई-प्रथम नोड पीढ़ी: अगले ई-नोड के रूप में नवीनतम लाइव नोड का उपयोग करता है।
बाउंडिंग फ़ंक्शनअनुकूलन के लिए B(x1, x2, …, Xa) को अधिकतम या न्यूनतम करता है।
स्थिर वृक्ष: समस्या के उदाहरण से स्वतंत्र वृक्ष निर्माण.
गतिशील पेड़: वृक्ष का निर्माण समस्या के उदाहरण के साथ बदलता रहता है।

बैकट्रैकिंग एल्गोरिदम का उपयोग कब करें?

हम किसी जटिल समस्या को हल करने के लिए बैकट्रैकिंग तकनीक का चयन तब कर सकते हैं जब:

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

बैकट्रैकिंग समस्याओं के प्रकार

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

निर्णय समस्या: इस प्रकार की समस्या में, लक्ष्य यह निर्धारित करना है कि कोई व्यवहार्य समाधान मौजूद है या नहीं। हम "हाँ" और "नहीं" उत्तरों की जाँच करते हैं। उदाहरण के लिए, n-रानियाँ समस्या। यह एक निर्णय समस्या है जो n × n शतरंज की बिसात पर n रानियों को एक दूसरे पर हमला किए बिना रखने की संभावना की जाँच करती है।
अनुकूलन समस्याअनुकूलन समस्याओं में, लक्ष्य कई विकल्पों में से सर्वोत्तम संभव समाधान खोजना होता है। इसमें किसी निश्चित फ़ंक्शन या चर के अधिकतम और न्यूनतम मान निर्धारित करना शामिल हो सकता है। उदाहरण के लिए, बैकपैक समस्या पर विचार करें, जहाँ उद्देश्य बैग में मौजूद वस्तुओं के कुल मूल्य को अधिकतम करना है, जबकि इसकी वज़न सीमा का पालन करना है।
गणना समस्या: इसका उद्देश्य किसी दी गई समस्या के सभी संभावित समाधान ढूँढना है। हम हर वैध विकल्प को बिना किसी चूक के सूचीबद्ध करते हैं। एक उदाहरण किसी दिए गए वर्ण सेट से सभी संभावित अक्षर संयोजन उत्पन्न करना होगा।

बैकट्रैकिंग के अनुप्रयोग और उदाहरण

बैकट्रैकिंग के विभिन्न अनुप्रयोग हैं। उनमें से कुछ को उनके छद्म कोड के साथ नीचे समझाया गया है।

Sudoku Solver: इस समस्या में डुप्लिकेट संख्याओं वाला 3×3 सबग्रिड शामिल है। बैकट्रैकिंग तकनीक से पता चलेगा कि समाधान गलत रिटर्न देता है, जो एक अलग नंबर प्लेसमेंट की आवश्यकता को दर्शाता है।

function solveSudoku(board):
    if no empty cells:
        return true  # Sudoku is solved
    for each empty cell (row, col):
        for num from 1 to 9:
            if num is valid in (row, col):
                place num in (row, col)
                if solveSudoku(board):
                    return true
                remove num from (row, col)
    return false  # No valid solution

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

function solveNQueens(board, col):
    if col >= N:
        return true  # All queens are placed
    for each row in the column col:
        if isSafe(board, row, col):
            place queen at (row, col)
            if solveNQueens(board, col + 1):
                return true
            remove queen from (row, col)
    return false  # No valid solution in this branch

उपसमुच्चय योग समस्याइसका उपयोग किसी दिए गए समूह से संख्याओं के उस उपसमूह को खोजने के लिए किया जाता है जो एक विशेष लक्ष्य राशि के बराबर होता है।

function subsetSum(nums, target, index, currentSubset):
    if target == 0:
        print(currentSubset)  # Subset with the target sum found
        return
    if index >= len(nums) or target < 0:
        return
   currentSubset.add(nums[index])
   subsetSum(nums, target - nums[index], index + 1, currentSubset)
   currentSubset.remove(nums[index])
   subsetSum(nums, target, index + 1, currentSubset)

हैमिल्टनियन चक्र समस्याबैकट्रैकिंग का उपयोग ग्राफ में एक बंद टूर को खोजने के लिए किया जा सकता है जो प्रत्येक शीर्ष पर ठीक एक बार जाता है।
भूलभुलैया में चूहे की समस्याबैकट्रैकिंग तकनीक का उपयोग भूलभुलैया के शुरुआती बिंदु से निकास तक चूहे का रास्ता खोजने के लिए किया जाता है।

बैकट्रैकिंग एल्गोरिदम के फायदे और नुकसान

बैकट्रैकिंग एल्गोरिदम के लाभ

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

बाधाओं से निपटने के लिए बैकट्रैकिंग तकनीक कुशल है।
यह विधि अनुकूलन समस्याओं को हल करने के लिए अच्छी है।
यह तकनीक विभिन्न प्रकार की समस्याओं के लिए काम करती है।
यह प्रक्रिया सभी संभावित समाधानों की समीक्षा करने में मदद कर सकती है।
चूंकि यह बैकट्रैक करता है, इसलिए यह ब्रूटफोर्स तकनीक की तुलना में अधिक मेमोरी बचाता है।

बैकट्रैकिंग एल्गोरिदम के नुकसान

बैकट्रैकिंग तकनीक की भी कुछ सीमाएँ हैं, जैसे समय की जटिलता। इस तकनीक में निम्नलिखित कमियाँ हैं:

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

बैकट्रैकिंग और रिकर्सन के बीच अंतर

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

निष्कर्ष

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

इसके अतिरिक्त, मशीन लर्निंग मॉडल पहले से सीखे गए पैटर्न के आधार पर निर्णय लेने में मार्गदर्शन कर सकते हैं।

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