स्टोकास्टिक खोज समस्याओं की पूर्णता को परिभाषित करने के लिए कैसे? - एल्गोरिदम, कृत्रिम बुद्धि, कंप्यूटर विज्ञान

क्या हम इसे केवल 1 होने का हल खोजने की प्रायिकता सीमा के साथ खोज करने के लिए परिभाषित कर सकते हैं?

उत्तर:

संक्षिप्त उत्तर: हाँ

लंबा जवाब: एक खोज एल्गोरिथ्म का दावा करने के लिए [यहां तक ​​कि स्टोचस्टिक] "पूर्ण" है आपको यह दिखाना होगा कि यदि कोई उत्तर है, तो एल्गोरिथ्म एक उत्तर देगा, एक परिमित समय में। इसका मतलब है, आपको यह दिखाना होगा कि यदि कोई उत्तर है, तो कोई संभावना नहीं है, एक गैर-परिष्करण [या गलत उत्तर के साथ] पथ है। तो, आपको यह दिखाने की जरूरत है कि संभावना 1 के साथ एक समाधान मिल जाएगा [वास्तव में! लगभग नहीं!], स्टोकेस्टिक एल्गोरिथ्म दिखाने के लिए "पूर्ण" है

उदाहरण के लिए, सबसे ऊंची चढ़ाई पहाड़ी पर साइड वॉक के साथ [आप पड़ोसी के साथ जा सकते हैंसमान उपयोगिता मूल्य] - पूर्ण नहीं है, क्योंकि आप एक अनंत लूप में प्रवेश कर सकते हैं और कभी कोई समाधान नहीं ढूंढ सकते हैं। हालाँकि, यदि आप साइड की संख्या को सीमित संख्या तक सीमित करते हैं K, यह पूर्ण है, क्योंकि अगर कोई स्थानीय न्यूनतम है, तो अंततः एल्गोरिथ्म एक मिलेगा, संभावना 1 के साथ।