question of streetparade को विस्तारित करने के बीच अंतर, मैं पूछना चाहता हूं कि स्टोकैस्टिक और हेरिस्टिक एल्गोरिदम के बीच क्या अंतर है, यदि कोई है।एक स्टोकास्टिक और एक ह्युरिस्टिक एल्गोरिदम
क्या यह कहना सही होगा कि एक स्टोकास्टिक एल्गोरिदम वास्तव में एक प्रकार का ह्युरिस्टिक है?
TTBOMK, "स्टोकेस्टिक एल्गोरिथ्म" नहीं है एक मानक शब्द। "यादृच्छिक एल्गोरिदम" हालांकि, और शायद यह यहां क्या है इसका मतलब है।
यादृच्छिक: किसी भी तरह यादृच्छिकता का उपयोग करता है। दो स्वाद हैं: मोंटे कार्लो एल्गोरिदम हमेशा बाध्य समय में समाप्त होते हैं, लेकिन एक इष्टतम समाधान की गारंटी नहीं देते हैं, जबकि लास वेगास एल्गोरिदम किसी भी सीमित समय में समाप्त होने की गारंटी नहीं है, लेकिन इष्टतम समाधान खोजने का वादा करता है । (आमतौर पर उन्हें एक सीमित अपेक्षित चलने का समय भी आवश्यक होता है।) आम मोंटे कार्लो एल्गोरिदम के उदाहरण: एमसीएमसी, नकली एनीलिंग, और मिलर-राबिन प्रारंभिक परीक्षण। यादृच्छिक पिवट विकल्प के साथ Quicksort एक लास वेगास एल्गोरिदम है जो हमेशा सीमित समय में खत्म होता है। एक एल्गोरिदम जो किसी भी यादृच्छिकता का उपयोग नहीं करता है निर्धारक है।
हेरिस्टिक: सही उत्तर खोजने की गारंटी नहीं है। एक एल्गोरिदम जो हेरिस्टिक नहीं है सटीक है।
कई हेरिस्टिक्स इनपुट के "आकस्मिक" गुणों के प्रति संवेदनशील होते हैं जो वास्तविक समाधान को प्रभावित नहीं करते हैं, जैसे ऑर्डर आइटम को बिन पैकिंग समस्या के लिए प्रथम-फिट ह्यूरिस्टिक में माना जाता है। इस मामले में उन्हें मोंटे कार्लो यादृच्छिक एल्गोरिदम के रूप में सोचा जा सकता है: आप यादृच्छिक रूप से इनपुट को अनुमति दे सकते हैं और उन्हें फिर से शुरू कर सकते हैं, हमेशा आपको सबसे अच्छा जवाब मिलते हैं।ओटीओएच, अन्य हेरिस्टिक्स में यह संपत्ति नहीं है - उदा। फर्स्ट-फिट-डिक्रीजिंग ह्युरिस्टिक दृढ़तावादी है, क्योंकि यह हमेशा पहले आकार घटाने में वस्तुओं को टाइप करता है।
एक विशेष यादृच्छिक एल्गोरिथ्म के संभावित आउटपुट के सेट परिमित और, सही जवाब शामिल तो यह काफी लंबे समय "व्यावहारिक रूप से गारंटी" है अंत में यह पता लगाने के लिए (भावना में चल रहे हैं कि नहीं की संभावना इसे खोजना मनमाने ढंग से छोटा हो सकता है, लेकिन कभी नहीं 0)। ध्यान दें कि यह स्वचालित रूप से मामला नहीं है कि एक ह्युरिस्टिक को इनपुट के कुछ क्रमपरिवर्तन के परिणामस्वरूप सटीक उत्तर मिल जाएगा - फर्स्ट-फिट के मामले में, यह पता चला है कि यह सत्य है, लेकिन यह केवल 200 9 में साबित हुआ था
कभी-कभी यादृच्छिक एल्गोरिदम के अभिसरण के बारे में मजबूत बयान किए जा सकते हैं: ये आमतौर पर "किसी भी छोटे थ्रेसहोल्ड डी के लिए, टी चरणों के बाद हम संभाव्यता के साथ इष्टतम समाधान के भीतर होंगे (टी, डी) ", एफ (टी, डी) टी और डी के बढ़ते कार्य के साथ।
बूथ दृष्टिकोण आमतौर पर
स्टोकेस्टिक एल्गोरिदम का उपयोग अनियमितता
वे सभी संयोजनों का उपयोग लेकिन क्रम में नहीं, लेकिन इसके बजाय एनपी पूरा समस्याओं का समाधान genere और परीक्षण तेजी लाने के लिए उपयोग किया जाता है वे समाधान को जल्द से जल्द हिट करने की उम्मीद की संभावनाओं की पूरी श्रृंखला से यादृच्छिक लोगों का उपयोग करें। कार्यान्वयन (निरंतर समय)
Heuristics एल्गोरिदम
वे संयोजन नहीं बेतरतीब ढंग से इस्तेमाल किया लेकिन प्रक्रिया, इनपुट डाटासेट, या उपयोग के बजाय पर कुछ ज्ञान के आधार पर लेने के तेज़, आसान और एकल पुनरावृत्ति भी तेज है। इसलिए वे संयोजनों की संख्या को केवल उन लोगों तक कम करते हैं जो संभवतः समाधान हैं और केवल उन लोगों का उपयोग करते हैं, लेकिन आमतौर पर समाधान के मिलने तक उनमें से सभी का उपयोग करते हैं।
कार्यान्वयन जटिलता समस्या पर निर्भर करती है, एकल पुनरावृत्ति आमतौर पर बहुत धीमी होती है तो स्टोकास्टिक दृष्टिकोण (निरंतर समय) इसलिए हेरिस्टिक्स का उपयोग केवल तभी किया जाता है जब वास्तविक गति के लिए संभावनाओं की संख्या कम हो जाती है, क्योंकि एल्गोरिदम जटिलता अनुमानी आमतौर पर बहुत कम है कभी कभी निरंतर समय काफी बड़ा है और भी धीमी गति से चीजों को नीचे ... (क्रम संदर्भ में)
बूथ दृष्टिकोण को एक साथ जोड़ा जा सकता है
यह उत्तर पूरी तरह सटीक नहीं है। दोनों में से कोई भी केवल एनपी पूर्ण समस्याओं पर लागू नहीं होता है। उदाहरण के लिए यादृच्छिक पिवट चयन, वेल्ज़ल के एल्गोरिदम, स्टोकास्टिक ग्रेडिएंट वंश आदि के साथ क्विकॉर्ट देखें। हेरिस्टिक भी यादृच्छिकरण से धीमे नहीं हैं। – IVlad
@IVlad yep मुझे पता है कि मैंने कभी लिखा नहीं है कि वे केवल इस उद्देश्य के लिए हैं ... लेकिन 'आमतौर पर' शब्द जोड़ना चोट नहीं पहुंचाएगा। गति एकल पुनरावृत्ति निरंतर समय के बारे में है (मैंने कभी भी छोटे निरंतर समय के साथ ह्युरिस्टिक नहीं देखा, फिर स्टोकैस्टिक दृष्टिकोण) – Spektre
@IVlad ने पाठ को थोड़ा सुधार दिया है। यदि आप बेहतर सुधार जानते हैं तो मेरे अंग्रेजी कौशल को संपादित करने के लिए स्वतंत्र महसूस हो रहा है – Spektre
आप निर्धारक एल्गोरिदम का उल्लेख करते हैं और इससे मुझे अतिरिक्त भ्रम पैदा होता है। _deterministic_ और _exact_ एल्गोरिदम एक ही चीज़ नहीं हैं? – orestis21
नहीं, आप निर्धारक हेरिस्टिक हो सकते हैं। बिन पैकिंग के लिए फर्स्ट-फिट-डिक्रीजिंग ह्युरिस्टिक एक निर्धारक है क्योंकि एक ही इनपुट दिया जाता है, यह हमेशा एक ही आउटपुट का उत्पादन करेगा। लेकिन यह सटीक नहीं है, क्योंकि यह इष्टतम समाधान नहीं मिल सकता है। –
यह टिप्पणी काफी प्रबुद्ध है। क्या हम तब कह सकते हैं कि हमारे पास dipoles _deterministic-stochastic_ और _exact-heuristics_ है? – orestis21