एक झूठ मॉडल में बाइनरी खोज कैसे करें?

Question

प्रश्न इस तरह है: एन संख्याओं की एक क्रमबद्ध सूची है। X को देखते हुए, क्रमबद्ध सूची में x के बराबर एक संख्या खोजें। यहां हम मानते हैं कि एक्स वास्तव में सूची में है। एक ऑरैकल है जो आपके प्रश्न "हां" या "नहीं" का जवाब दे सकता है "क्या x> = y?"। सामान्य द्विआधारी खोज के विपरीत, ऑरैकल को आपके प्रश्न पर एक बार झूठ बोलने की अनुमति है। इस समस्या को हल करने का सबसे बेवकूफ तरीका यह है कि आप प्रत्येक सवाल को ऑरैकल से दो बार पूछते हैं। यदि दो उत्तरों समान हैं, तो आप जानते हैं कि ऑरेल झूठ नहीं बोल रहा है। यह एल्गोरिदम हमें 2log_2 (n) बार की तुलना करने की आवश्यकता है। लेकिन यह सवाल मुझे एक एल्गोरिदम खोजने के लिए कहता है जो केवल लॉग_2 (एन) + ओ (लॉगऑन) तुलना का उपयोग कर एक्स पा सकता है।

मैंने बहुत मेहनत की लेकिन असफल रहा। क्या कोई मुझे इस समस्या को हल करने के बारे में कुछ सलाह दे सकता है? धन्यवाद।

Answer 1

आप जिस अंतराल में हैं, उसका ट्रैक रखें। यदि आपको k प्रश्नों की आवश्यकता है, तो प्रत्येक sqrt(k) चरणों में स्थिरता की जांच करें (चाहे आप अंतराल में हों)। स्थिरता की जांच करते समय आप प्रत्येक प्रश्न को दो बार सुनिश्चित करने के लिए कह सकते हैं। यदि आप असंगतता का पता लगाते हैं, तो sqrt(k) चरणों पर वापस जाएं। आप c*sqrt(k) अतिरिक्त प्रश्नों से अधिक नहीं पूछेंगे।

Answer 2

केवल ओरेकल से सवाल पूछें: "x> = y है?" एक बार अपनी बाइनरी खोज के प्रत्येक पुनरावृत्ति पर। यदि आपको दो बार एक ही जवाब मिलता है, तो आप जानते हैं कि ओरेकल पहली बार झूठ नहीं बोलता था।

उदाहरण के लिए, आप x = 1 की खोज कर रहे हैं, और पहले परीक्षण जो आप y = a के खिलाफ परीक्षण करते हैं, और ऑरैकल x < ए का उत्तर देता है। दूसरे परीक्षण पर आप वाई = बी के खिलाफ परीक्षण करते हैं और ऑरकल जवाब x < बी। चूंकि आप बाइनरी खोज का उपयोग कर रहे हैं, और ऑरैकल ने कहा '<', और सरणी सॉर्ट की गई है, आप जानते हैं कि बी < ए। इसलिए, यदि x < बी, तो आप यह भी जानते हैं कि x < ए, और पहला उत्तर झूठ नहीं था। यदि दूसरा उत्तर झूठ है, और x> b, तो यह अभी भी सत्य है कि x < ए, क्योंकि ऑरैकल केवल एक बार झूठ बोल सकता है।

यह सच है भले ही उत्तर वापस वापस न आएं। उदाहरण के लिए आपको तीन उत्तरों मिलते हैं: x < ए, एक्स> = बी, एक्स < सी, आप जानते हैं कि सी < ए, आपकी द्विआधारी खोज से, और इसलिए यह सच होना चाहिए कि x < ए, और ऑरैकल नहीं था झूठ बोला जब उसने आपको बताया था।

तो क्या होता है जब ऑरैकल झूठ बोलता है? यदि झूठ x < y था, तो सत्य x> = y था। इसलिए, जब आप अपनी बाइनरी खोज जारी रखते हैं, उस बिंदु से, आपके द्वारा चेक की जाने वाली संख्याएं बहुत छोटी होंगी, और उत्तर हमेशा "> =" होगा, जब तक आप बाइनरी खोज के नीचे तक नहीं पहुंच जाते। उस समय, आपको एहसास हुआ कि अगर ऑरैकल झूठ बोला गया, तो उसने आखिरी बार झूठ बोला जब उसने आपको "> =" के अलावा कुछ और बताया। तो आप उस बिंदु पर अपनी बाइनरी खोज को पुनरारंभ करें जहां ऑरैकल ने आपको झूठ बोला और कहा "x < y"।

यह हमेशा < 2 लॉग_2 एन तुलना का उपयोग करेगा, लेकिन अगर खोज की शुरुआत में ऑरकल आपको झूठ बोलता है, तो आपको लगभग log_2 n काम दोहराना होगा, और इसलिए आपको log_2 n + o नहीं मिलता है (लॉग एन) उत्तर आप देख रहे थे। इस प्रकार, आपको एनएम द्वारा सुझाए गए विचार को शामिल करना चाहिए। अगर आपको एक ही जवाब मिलता है, तो पंक्ति में sqrt (लॉग n) बार कहें, तो आपको संदेह है कि ऑरैकल ने आपसे झूठ बोला होगा, और आप तुरंत सवाल पूछेंगे बाइनरी खोज के निचले हिस्से तक इंतजार करने के बजाए जवाब दोहराने शुरू होने से ठीक पहले पूछा गया। इस रणनीति के बाद, आप सबसे खराब मामले में एक प्रश्न लॉग n/sqrt (लॉग n) बार फिर से पूछेंगे, और आप हमेशा अधिकतर sqrt (लॉग n) बर्बाद काम के साथ झूठ पकड़ेंगे, जो चलने वाले समय को प्राप्त करता है खोज रहे हैं

Answer 3

आप इस काम करने के लिए क्लासिक द्विआधारी खोज को बदलने के लिए, कैसे के बारे में कोशिश के बजाय सरणी के 2 अलग अनुक्रमित तुलना करने के लिए प्रत्येक चरण में ओरेकल पूछ सकते हैं सिर्फ 1, कुछ की तरह:

assume Oracle(x,y) returns "x>=y?", assume every division is returning floor integer. 
LyingOracleSearch(A,n,toFind) 
1. if (n==0) return not found 
2. if (A[0]==toFind) return found 
3. if (Oracle(A[n/4],toFind) and Oracle(toFind,A[3n/4]) then 
4.      return LyingOracleSearch(A[(n/4)...(3n/4)],3n/4-n/4,toFind) 
5. if (Oracle(A[n/4],toFind) and !Oracle(toFind,A[3n/4]) then 
6.      return LyingOracleSearch(A[0...(n/4)],n/4,toFind) 
7. if (!Oracle(A[n/4],toFind) and Oracle(toFind,A[3n/4]) then 
8.      return LyingOracleSearch(A[(3n/4)...n],n-3n/4,toFind) 
9. return LyingOracleSearch(A,n,toFind); \\orcale lied! 

मुझे लगता है कि यह नाखून, गलत हो सकता है।

यह जटिलता मूल बी एस के रूप में ही है, लेकिन यह बेहतर ओरेकल दो बार या उससे अधिक पूछ तो है। ध्यान दें कि जब तक ऑर्केकल झूठ न हो, तब तक तत्व को दो बार तुलना नहीं किया जाता है, इसलिए यदि यह एक बार या यहां तक ​​कि के समय भी है जहां k छोटा है (लॉग) तो हम ठीक हैं।

आप अपने पसंदीदा कोडिंग वातावरण के लिए जाना है और इसे कोड करने के लिए कोशिश कर सकते हैं, हर बार एक तुलना की है, यह गिनती। इस और निष्पक्ष दोनों को आज़माएं, और परिणाम की तुलना करें, अगर मुझे गलत नहीं लगता है, तो मूर्खता को दो गुना तुलना करना चाहिए।

सूचना यद्यपि, मैं सूचकांक भी सावधान नहीं था, क्या आप वाकई मैं एक सूचकांक लापता एकदम चमक या नहीं था गलती से एक सूचकांक दोहरा बनाने के लिए कुछ सोच करने की आवश्यकता होगी।

Answer 4

इस तथ्य का प्रयोग करें कि ऑरैकल झूठ बोलने के बाद, बाइनरी खोज गलत तरीके से जाती है, और उस समय से ऑरैकल के जवाब में आपको कोई बदलाव नहीं होता है (हमेशा >= या हमेशा <)। यदि आपको log(log(n)) चरणों के लिए ऑरैकल के उत्तर में कोई बदलाव नहीं मिलता है, तो अंतराल स्थिरता की जांच करें। यदि वर्तमान अंतराल असंगत है, ओरेकल एक बार फिर पूछते हैं, और यदि अभी भी असंगत, वापस log(log(n)) + 1 चरणों जाने के लिए और सामान्य द्विआधारी खोज के साथ जारी है।

इस प्रक्रिया को O(log(log(n))) औसत पर स्थिरता जांच और log(log(n)) अतिरिक्त बाइनरी खोज चरणों की आवश्यकता है।

अतिरिक्त प्रश्नों की औसत संख्या c*log(log(n)) है, अतिरिक्त प्रश्नों की अधिकतम संख्या log(n)/(log(log(n))) + log(log(n)) है।

Answer 5

मुझे लगता है कि 3 * log(n) में इस प्रश्न को हल करना आसान हो सकता है, असमानता प्रश्न प्रत्येक चरण में तीन बार पूछकर, और निर्णय बहुमत है।