वापसtracराजा एल्गोरिथम

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

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

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

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

कैसे वापसtracक्या किंग एल्गोरिदम काम करता है?

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

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

पीछेtracकिंग एल्गोरिदम किसी समस्या को हल करने के लिए निम्नलिखित सामान्य चरणों का पालन करता है:

चरण 1) आरंभीकरण: एक खाली या आंशिक घोल से शुरुआत करें।

चरण 2) चयन: दी गई सीमाओं के आधार पर, वर्तमान समाधान को विस्तारित करने के लिए एक संभावित विकल्प का चयन करें।

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

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

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

चरण 6) वापसtracराजा: जब वर्तमान विकल्प समस्या का समाधान नहीं कर पाता है, तो पिछली स्थिति पर वापस जाएं और एक नए विकल्प को आज़माएं।

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

बैक की पुनरावर्ती प्रकृतिtracराजा एल्गोरिथम

वापसtracकिंग एल्गोरिदम स्वाभाविक रूप से पुनरावर्ती होते हैं। यह फ़ंक्शन तब तक अलग-अलग मापदंडों के साथ खुद को कॉल करता है जब तक कि उसे कोई वैध समाधान नहीं मिल जाता या वह हर संभावना को समाप्त नहीं कर देता।

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)

पीठ से संबंधित सामान्य शब्दtracराजा की समस्याएं

ये बैक से जुड़े मूलभूत शब्द हैंtracराजा तकनीक:

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

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

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

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

पीठ के प्रकारtracराजा की समस्याएं

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

1. निर्णय समस्या: लक्ष्य यह निर्धारित करना है कि क्या कोई व्यवहार्य समाधान मौजूद है। इसका उत्तर हाँ या ना में होगा। उदाहरण के लिए, एन-क्वीन्स समस्या एक निर्णय समस्या है जिसमें यह पूछा जाता है कि क्या एन रानियों को एन x एन शतरंज बोर्ड पर एक-दूसरे पर हमला किए बिना रखा जा सकता है।
2. अनुकूलन समस्या: लक्ष्य कई विकल्पों में से सर्वोत्तम संभव समाधान खोजना है। इसमें किसी फ़ंक्शन या चर के अधिकतम या न्यूनतम मान की पहचान करना शामिल हो सकता है। नैपसैक समस्या, जिसमें उद्देश्य वजन सीमा का पालन करते हुए वस्तुओं के कुल मूल्य को अधिकतम करना है, इसका एक उत्कृष्ट उदाहरण है।
3. गणना संबंधी समस्या: इसका उद्देश्य किसी दी गई समस्या के सभी वैध समाधानों को बिना छोड़े सूचीबद्ध करना है। दिए गए अक्षरों के समूह से सभी संभावित अक्षर संयोजनों को उत्पन्न करना इसका एक उदाहरण है।

पीठ के अनुप्रयोगtracराजा और उदाहरण

वापसtracking का उपयोग कई वास्तविक दुनिया और शैक्षणिक परिदृश्यों में होता है। कुछ लोकप्रिय अनुप्रयोगों को उनके स्यूडो कोड के साथ नीचे समझाया गया है।

1. Sudoku Solver: पीछेtracकिंग तकनीक खाली खानों को वैध संख्याओं से भर देती है और जब भी कोई संख्या सुडोकू नियमों का उल्लंघन करती है तो उसे वापस पहले जैसी स्थिति में कर देती है।

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

2. एन-क्वीन समस्या: पीछेtracराजा की भूमिका में, रानियों को N x 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

3. उपसमुच्चय योग समस्या: वापसtracराजा दिए गए समुच्चय में से संख्याओं का वह उपसमुच्चय ढूंढता है जिसका योग एक विशिष्ट लक्ष्य योग के बराबर होता है।

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)

4. हैमिल्टोनियन चक्र समस्या: वापसtracकिंग विधि का उपयोग ग्राफ में एक बंद टूर खोजने के लिए किया जाता है जो प्रत्येक वर्टेक्स पर ठीक एक बार जाता है।
5. भूलभुलैया में फंसे चूहे की समस्या: वापसtracराजा एक चूहे का रास्ता ढूंढता है जो भूलभुलैया के शुरुआती बिंदु से निकास तक जाता है, और उन चालों को उलट देता है जो दीवारों की ओर ले जाती हैं।

पीठ के लाभ और हानिtracराजा एल्गोरिथम

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

पीठ के लाभtracराजा एल्गोरिथम

वापसtracकिंग तकनीकें कई प्रभावी तरीकों से जटिल समस्याओं को हल करती हैं:

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

पीठ के नुकसानtracराजा एल्गोरिथम

वापसtracकिंग प्रोग्रामिंग में कुछ सीमाएँ भी हैं, विशेष रूप से समय जटिलता के संदर्भ में। इसकी कमियाँ निम्नलिखित हैं:

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

पीठ के बीच का अंतरtracराजा और पुनरावृति

वापसtracकिंग गेम रिकर्सन पर आधारित है, लेकिन दोनों एक समान नहीं हैं। नीचे दी गई तालिका प्रमुख अंतरों को दर्शाती है।

अक्सर पूछे जाने वाले प्रश्न