तो मेरे पास कम से कम दो प्रोफेसरों का उल्लेख है कि बैकट्रैकिंग एक एल्गोरिदम गैर-निर्धारिती बनाता है, जो कि क्यों है में बहुत अधिक स्पष्टीकरण देता है। मैं सोचता हूं मैं समझता हूं कि यह कैसे होता है, लेकिन मुझे इसे शब्दों में डालने में परेशानी है। क्या कोई मुझे इसके कारण का संक्षिप्त विवरण दे सकता है?बैकट्रैकिंग एल्गोरिदम गैर-निर्धारिती क्यों बनाती है?
यह इतना मामला नहीं है कि बैकट्रैकिंग एल्गोरिदम गैर-निर्धारिती बनाता है।
इसके बजाय, आपको आमतौर पर गैर-निर्धारिती एल्गोरिदम को संसाधित करने के लिए बैकट्रैकिंग की आवश्यकता होती है, क्योंकि (गैर-निर्धारिती की परिभाषा के अनुसार) आप नहीं जानते कि आपके प्रसंस्करण में किसी विशेष समय पर कौन सा पथ लेना है, लेकिन इसके बजाय आपको कोशिश करनी चाहिए कई।
मैं सिर्फ बोली विकिपीडिया होगी:
एक गैर नियतात्मक प्रोग्रामिंग भाषा एक भाषा है जो इस कार्यक्रम में कुछ बिंदुओं पर, निर्दिष्ट कर सकते हैं ("पसंद अंक" कहा जाता है), प्रोग्राम प्रवाह के लिए विभिन्न विकल्प। एक if-then कथन के विपरीत, इन विकल्पों के बीच पसंद की विधि सीधे प्रोग्रामर द्वारा निर्दिष्ट नहीं है; कार्यक्रम को सभी विकल्पों के लिए लागू कुछ सामान्य विधि के माध्यम से विकल्प के बीच रनटाइम पर निर्णय लेना चाहिए। एक प्रोग्रामर सीमित संख्या में विकल्पों को निर्दिष्ट करता है, लेकिन कार्यक्रम को बाद में उनके बीच चुनना चाहिए। (वास्तव में, "नोडेटर्मिनिस्टिक ऑपरेटर के लिए एक सामान्य नाम है।) पसंद बिंदुओं का एक पदानुक्रम बनाया जा सकता है, उच्च स्तर के विकल्पों में शाखाएं होती हैं जिनमें निम्न स्तर के विकल्प होते हैं।
बैकट्रैकिंग सिस्टम में पसंद का एक तरीका शामिल है, जिसमें कुछ विकल्प "असफल" हो सकते हैं, जिससे प्रोग्राम बैकट्रैक और अन्य विकल्पों को आज़मा सकता है। यदि सभी विकल्प एक विशेष पसंद बिंदु पर असफल होते हैं, तो एक पूरी शाखा विफल हो जाती है, और कार्यक्रम पुराने विकल्प बिंदु पर आगे पीछे हट जाएगा। एक जटिलता यह है कि, क्योंकि कोई भी विकल्प टिकाऊ है और इसे पुनर्निर्मित किया जा सकता है, इसलिए सिस्टम अंततः विफल होने वाली शाखा को आंशिक रूप से निष्पादित करने के कारण दुष्प्रभावों को पूर्ववत करके पुराने प्रोग्राम राज्यों को पुनर्स्थापित करने में सक्षम होना चाहिए।
Nondeterministic Programming लेख में से।
बधाई। एक "विकिपीडिया पढ़ें" जवाब जिसने मुझे पूरी तरह गूंगा महसूस नहीं किया। :-) –
जो सिस्टम को अनिश्चिततापूर्ण नहीं बनाता है, मैं मार्क हैरिसन के उत्तर के साथ जाऊंगा: यह _simulate_ (सैद्धांतिक) गैर निर्धारक मशीन का एक तरीका है। – hasen
हैसन जे, आप किस प्रणाली का मतलब है? पाठ्यक्रम की बैकट्रैकिंग केवल गैर-निर्धारणा को अनुकरण कर सकती है, जब तक यह एक निर्धारक कंप्यूटर पर चलती है। एक प्रमुख उदाहरण एक नियमित अभिव्यक्ति पुस्तकालय है। वे गैर-निर्धारिती वर्णन लेते हैं, और उन्हें निर्धारक राज्य मशीनों में बदलना होगा। –
दुनिया के मानचित्र को रंगने के लिए एल्गोरिदम पर विचार करें। आसन्न देशों पर कोई रंग इस्तेमाल नहीं किया जा सकता है। एल्गोरिदम मनमाने ढंग से एक देश में शुरू होता है और इसे एक मनमाना रंग रंग देता है। तो यह रंगीन देशों के साथ चलता है, प्रत्येक चरण पर रंग बदलता है, "ओह ओह", दो आसन्न देशों में एक ही रंग होता है। खैर, अब हमें पीछे हटना होगा, और एक नया रंग पसंद करना होगा। अब हम एक नोडेटर्मिनिस्टिक एल्गोरिदम के रूप में कोई विकल्प नहीं बना रहे हैं, यह हमारे निर्धारक कंप्यूटरों के लिए संभव नहीं है। इसके बजाय, हम backtracking के साथ nondeterministic एल्गोरिदम अनुकरण कर रहे हैं। एक nondeterministic एल्गोरिदम हर देश के लिए सही विकल्प बनाया होगा।
litb के उत्तर – hasen
सोचा प्रयोग:
1) दृश्य से छिपा वहाँ विद्युत आवेश जो आप से एक शक्ति महसूस के कुछ वितरण है और आप संभावित क्षेत्र वे बनाने के लिए उपाय। मुझे बिल्कुल सभी शुल्कों की स्थिति बताओ।
2) कुछ शुल्क लें और उन्हें व्यवस्थित करें। मुझे बिल्कुल सही क्षेत्र बताएं जो वे बनाते हैं।
केवल दूसरे प्रश्न का एक अनूठा उत्तर है। यह vector fields की गैर विशिष्टता है। यह स्थिति कुछ गैर-निर्धारिती एल्गोरिदम के अनुरूप हो सकती है, जिन पर आप विचार कर रहे हैं। math limits में आगे विचार करें जो अस्तित्व में नहीं है क्योंकि उनके पास अलग-अलग उत्तर हैं जिनके आधार पर आप किस दिशा में असंतोष से संपर्क करते हैं।
यदि आप बैकट्रैकिंग की अनुमति देते हैं तो आप अपने प्रोग्राम में अनंत लूपिंग की अनुमति देते हैं जो इसे गैर-निर्धारिती बनाता है क्योंकि वास्तविक पथ में हमेशा एक और लूप शामिल हो सकता है।
-1 पर मेरी टिप्पणियां देखें, अनंत लूपिंग को निर्धारणा के साथ क्या करना है ?? – hasen
गैर-निर्धारक ट्यूरिंग मशीनें (एनडीटीएम) एक ही चरण में कई शाखाएं ले सकती हैं। दूसरी तरफ डीटीएम परीक्षण-और-त्रुटि प्रक्रिया का पालन करते हैं।
आप नियमित कंप्यूटर के रूप में डीटीएम के बारे में सोच सकते हैं। इसके विपरीत, क्वांटम कंप्यूटर एनडीटीएम के समान होते हैं और गैर-निर्धारणात्मक समस्याओं को बहुत आसान बना सकते हैं (उदा। क्रिप्टोग्राफी तोड़ने में उनके आवेदन को देखें)। तो बैकट्रैकिंग वास्तव में उनके लिए एक रैखिक प्रक्रिया होगी।
एक निर्धारक कंप्यूटर पर बैकट्रैकिंग का चलने का समय फैक्टोरियल है, यानी यह ओ (एन!) में है।
जहां एक गैर-निर्धारिती कंप्यूटर प्रत्येक चरण में तुरंत सही ढंग से अनुमान लगा सकता है, एक निर्धारक कंप्यूटर को विकल्पों के सभी संभावित संयोजनों को आजमा देना पड़ता है।
के बाद से यह असंभव है एक गैर नियतात्मक कंप्यूटर का निर्माण करने, क्या आपके प्रोफेसर शायद मतलब है निम्नलिखित:
जटिलता वर्ग एनपी में एक provenly hard समस्या (सभी समस्याओं है कि एक गैर नियतात्मक कंप्यूटर द्वारा कुशलता से हल कर सकते हैं हमेशा सही अनुमान लगाया जा सकता है) वास्तविक कंप्यूटर पर बैकट्रैकिंग की तुलना में अधिक कुशलता से हल नहीं किया जा सकता है।
उपर्युक्त कथन सत्य है, यदि जटिलता कक्षा पी (सभी समस्याएं जो एक निर्धारक कंप्यूटर कुशलतापूर्वक हल कर सकती हैं) और एनपी समान नहीं हैं। यह प्रसिद्ध पी बनाम एनपी समस्या है। क्ले मैथमैटिक्स इंस्टीट्यूट ने अपने समाधान के लिए $ 1 मिलियन पुरस्कार की पेशकश की है, लेकिन समस्या ने कई सालों से सबूत का विरोध किया है। हालांकि, अधिकांश शोधकर्ता मानते हैं कि पी एनपी के बराबर नहीं है।
इसे समेकित करने का एक आसान तरीका यह होगा: एक गैर-निर्धारक कंप्यूटर हमेशा सही ढंग से अनुमान लगाकर कुशलतापूर्वक हल कर सकता है, इतना कठिन है कि एक निर्धारक कंप्यूटर को संभवतः विकल्पों के सभी संभावित संयोजनों का उपयोग करना होगा, यानी उपयोग बैक ट्रैकिंग।
यह ध्यान देने के लिए संपादित किया गया है कि एल्गोरिदम घातीय के बजाय फैक्टोरियल हैं। –
जटिलता कक्षाओं के मामले में वे घातीय हैं (यानी EXPTIME में)। इसके अलावा, अधिकांश ओ (एन!) समस्याओं को गतिशील प्रोग्रामिंग का उपयोग कर ओ (एन^2 * 2^एन) में हल किया जा सकता है। लेकिन अगर आपको समझना आसान लगता है, तो यह मेरे साथ ठीक है। – mdm
मैंने एक भूलभुलैया धावक लिखा जो बैकट्रैकिंग (बेशक) का उपयोग करता है, जिसे मैं एक उदाहरण के रूप में उपयोग करूंगा।
आप भूलभुलैया के माध्यम से चलते हैं। जब आप एक जंक्शन तक पहुंचते हैं, तो आप यह तय करने के लिए एक सिक्का फिसलते हैं कि किस मार्ग का पालन करना है। यदि आपने मृत अंत का चयन किया है, तो जंक्शन पर वापस जाएं और दूसरा मार्ग लें। यदि आपने उन सभी की कोशिश की, तो पिछले जंक्शन पर वापस आएं। यह एल्गोरिदम गैर-निर्धारक है, बैकट्रैकिंग के कारण नहीं, बल्कि सिक्का फ़्लिपिंग के कारण।
अब एल्गोरिदम बदलें: जब आप जंक्शन तक पहुंचते हैं, तो हमेशा उस बाएं मार्ग का प्रयास करें जिसे आपने अभी तक नहीं आजमाया है। यदि यह एक मृत अंत की ओर जाता है, तो जंक्शन पर वापस लौटें और फिर उस बाएं मार्ग का प्रयास करें जिसे आपने अभी तक नहीं आजमाया है। यह एल्गोरिदम निर्धारक है। इसमें कोई मौका नहीं है, यह अनुमान लगाया जा सकता है: आप हमेशा एक ही मार्ग में उसी मार्ग का पालन करेंगे।
मुझे भूलभुलैया समानता पसंद है। चलो, सादगी के लिए भूलभुलैया के बारे में सोचें, एक बाइनरी पेड़ के रूप में, जिसमें केवल एक रास्ता है।
अब आप भूलभुलैया से सही तरीके खोजने के लिए पहली बार गहराई से प्रयास करना चाहते हैं।
एक गैर-निर्धारक कंप्यूटर प्रत्येक शाखा बिंदु पर, डुप्लिकेट/क्लोन स्वयं करेगा और समानांतर में प्रत्येक आगे की गणना चलाएगा।ऐसा लगता है जैसे भूलभुलैया में व्यक्ति प्रत्येक शाखा बिंदु पर खुद को डुप्लिकेट/क्लोन करेगा (जैसे फिल्म प्रेस्टिज में) और पेड़ के बाएं सबब्रैंच में खुद की एक प्रति भेज दें और दूसरी प्रतिलिपि स्वयं के दाहिनी उप-शाखा में भेजें पेड़।
कंप्यूटर/व्यक्ति जो एक मृत अंत में समाप्त होते हैं वे मर जाते हैं (उत्तर के बिना समाप्त)।
केवल एक कंप्यूटर जीवित रहेगा (एक उत्तर के साथ समाप्त), जो भूलभुलैया से बाहर निकलता है।
बैकट्रैकिंग और गैर-निर्धारणा के बीच का अंतर निम्नलिखित है।
बैकट्रैकिंग के मामले में किसी भी क्षण में केवल एक कंप्यूटर जीवित होता है, वह परंपरागत भूलभुलैया सुलझाने की चाल करता है, बस अपने पथ को चॉक के साथ चिह्नित करता है और जब वह एक मृत अंत तक पहुंच जाता है तो वह बस एक शाखा में बैकट्रैक करता है जिसकी उप शाखाओं ने अभी तक पूरी तरह से अन्वेषण नहीं किया है, बस गहराई की पहली खोज की तरह।
इसके विपरीत:
एक गैर deteministic कंप्यूटर खुद को हर शाखाओं बिंदु पर क्लोन और बाहर उप शाखाओं में समानांतर खोजें चलाकर रास्ता के लिए देख सकते हैं।
तो बैकट्रैकिंग एल्गोरिदम एक अनुक्रमिक/गैर समांतर/निर्धारक कंप्यूटर पर गैर-निर्धारक कंप्यूटर की क्लोनिंग क्षमता को अनुकरण/अनुकरण करता है।
बैकट्रैकिंग एल्गोरिदम गैर-निर्धारिती नहीं बनाता है; कृपया अपना प्रश्न बदलें। – ShreevatsaR
अच्छा सवाल, मैं इस वीडियो व्याख्यान को देखते समय खुद को एक ही सवाल पूछ रहा था: http://youtu.be/UBVcV3LIBeU – jhegedus