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

Question

बैकट्रैकिंग और रिकर्सन के बीच क्या अंतर है? यह प्रोग्राम कैसे काम कर रहा है?

void generate_all(int n) 
{ 
    if(n<1) printf("%s\n", ar); 
    else{ 
      ar[n-1]='0';  //fix (n)th bit as '0' 
      generate_all(n-1); //generate all combinations for other n-1 positions. 
      ar[n-1]='1';  //fix (n)th bit as '1' 
      generate_all(n-1); //generate all combinations for other n-1 positions. 
    } 

Answer 1

Recursion वही कार्य है कि आप में हैं बुला वर्णन करता है। एक पुनरावर्ती समारोह के विशिष्ट उदाहरण भाज्य, यानी कुछ की तरह

int fact(int n) { 
    int result; 
    if(n==1) return 1; 
    result = fact(n-1) * n; 
    return result; 
} 

क्या आप यहाँ देख तथ्य यह है कि है खुद को बुलाता है इसे रिकर्सन कहा जाता है। आपको हमेशा ऐसी स्थिति की आवश्यकता होती है जो रिकर्सन स्टॉप बनाता है। यहाँ यह if(n==1) तथ्य के साथ संयुक्त है कि n हमेशा हर बार यह कहा जाता है (fact(n-1))

बैकट्रेस कमी होगी एक एल्गोरिथ्म एक समाधान दिए गए मापदंडों को खोजने के लिए कोशिश करता है। यह समाधान के लिए उम्मीदवार बनाता है और उन शर्तों को त्याग देता है जो शर्तों को पूरा नहीं कर सकते हैं। हल करने के लिए एक कार्य के लिए एक सामान्य उदाहरण Eight Queens Puzzle होगा। बैकट्रैकिंग का प्रयोग आमतौर पर न्यूरोनल नेटवर्क के भीतर भी किया जाता है।

आपके द्वारा वर्णित कार्यक्रम रिकर्सन का उपयोग करता है। फैक्टोरियल फ़ंक्शन के समान, यह तर्क को कम करता है और समाप्त होता है यदि n < 1 (क्योंकि तब यह शेष करने के बजाय ar प्रिंट करेगा)।

Answer 2

यह प्रश्न पूछने की तरह है कि एक कार और एक डेलोरियन के बीच क्या अंतर है।

रिकर्सन फ़ंक्शन में बेस केस तक पहुंचने तक स्वयं को कॉल किया जाता है।

बैकट्रैकिंग में आप सभी संभावनाओं का पता लगाने के लिए रिकर्सन का उपयोग करते हैं जब तक आपको समस्या का सर्वोत्तम परिणाम न मिल जाए।

थोड़ा समझने के लिए मुश्किल हो सकता है, मैं here से कुछ पाठ देते हैं:

"वैचारिक रूप से, आप एक पेड़ की जड़ में शुरू; पेड़ शायद कुछ अच्छी पत्ते और कुछ बुरी पत्ते है, हालांकि यह हो सकता है हो सकता है कि पत्तियां सभी अच्छी या बुरी हों। आप एक अच्छे पत्ते पर जाना चाहते हैं। प्रत्येक नोड पर, रूट से शुरू होने पर, आप अपने बच्चों में से एक को स्थानांतरित करने के लिए चुनते हैं, और जब तक आप पत्ते तक नहीं पहुंच जाते

मान लीजिए कि आप एक बुरे पत्ते पर आते हैं। आप अपनी सबसे हाल की पसंद को रद्द करके और विकल्पों के उस सेट में अगला विकल्प चुनकर एक अच्छे पत्ते की तलाश जारी रखने के लिए बैकट्रैक कर सकते हैं। यदि आप विकल्पों से बाहर निकलते हैं, choic रद्द करें ई जो आपको यहाँ मिला, और उस नोड पर एक और विकल्प आज़माएं। आप कोई विकल्प नहीं छोड़ा साथ जड़ में अंत है, वहाँ कोई अच्छा पत्ते पाया जा सकता है। "

यह एक उदाहरण की जरूरत है।

गए कोड का टुकड़ा बस प्रत्यावर्तन, आप के रूप में है यदि परिणाम आपके लक्ष्य में फिट नहीं होता है तो कभी वापस न आएं।

Answer 3

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