बाइनरी खोज ट्रैवर्सल लागत के साथ कुशल नहीं है। क्या है?

Question

जब मैंने इसे वास्तविक दुनिया में लागू करने का प्रयास किया तो बाइनरी खोज ने मुझे नीचे जाने दिया। परिदृश्य इस प्रकार है।

मुझे रेडियो पर संचार करने वाले डिवाइस की सीमा का परीक्षण करने की आवश्यकता है। संचार को जल्दी से होने की आवश्यकता है, लेकिन धीमी संचरण सहनशील है, एक बिंदु तक (कहें, लगभग 3 मिनट)। मुझे का परीक्षण करने की आवश्यकता है कि 1600 फीट तक विफलता तक 200 मीटर तक प्रसारण सफल रहेगा या नहीं। प्रत्येक 200 फीट एक परीक्षण चलाया जाएगा जिसके लिए 3 मिनट से निष्पादित होना आवश्यक है।

मैं मूर्खता से मानता हूं कि एक बाइनरी खोज विफलता बिंदु खोजने का सबसे प्रभावी तरीका होगा, लेकिन 200 फीट/मिनट की यात्रा गति और 3 मिनट के परीक्षण समय पर विचार करें। यदि 500 ​​फीट पर संचार करने में विफलता होती है, तो बाइनरी खोज विफलता बिंदु खोजने का सबसे प्रभावी माध्यम नहीं है, जैसा कि नीचे दिखाया गया है।

आप के साथ घूमना और हर एक बिंदु का परीक्षण समाधान जल्दी ही पाया होता, केवल 12 मिनट ले रही है, जबकि द्विआधारी खोज & परीक्षण 16 मिनट ले जाएगा।

मेरा प्रश्न: यात्रा के समय यात्रा के दौरान समाधान के सबसे कुशल पथ की गणना कैसे करते हैं? इसे क्या कहा जाता है (उदाहरण के लिए, बाइनरी-यात्रा खोज, आदि)?

Answer 1

बाइनरी खोज वास्तव में O(1) पहुंच समय पर अनुमानित है; एक लिंक्ड सूची खोजने के लिए थोड़ा बिंदु बाइनरी है, उदाहरण के लिए [लेकिन नोट 1 देखें], और यह अनिवार्य रूप से आप क्या कर रहे हैं, क्योंकि आप मानते हैं कि केवल अलग अंतराल परीक्षण के लायक हैं। यदि आप अधिक सटीक उत्तर की तलाश में थे, तो आप पाएंगे कि द्विआधारी खोज परिशुद्धता के एक अतिरिक्त परीक्षण की लागत पर, मनमाने ढंग से सटीकता की अनुमति देती है।

मान लीजिए कि आप यह भी नहीं जानते कि अधिकतम मूल्य क्या हो सकता है। तब आप मध्य में पहली बार परीक्षण नहीं कर सके, क्योंकि आप नहीं जानते कि बीच कहां था। इसके बजाए, आप एक सीमा के लिए घातीय खोज कर सकते हैं (जो कि अंदरूनी बाइनरी खोज है); आप x पर परीक्षण करके शुरू करते हैं, फिर 2x, फिर 4x जब तक आप अधिकतम से अधिक नहीं हो जाते हैं (सिग्नल उस तक नहीं पहुंचता है)। (x आपको सबसे छोटा जवाब मिल रहा है; दूसरे शब्दों में, यदि x पर पहला परीक्षण दिखाता है कि सिग्नल नहीं पहुंचता है, तो आप रुकेंगे।) इस चरण के अंत में, आप 2ix पर होंगे, कुछ के लिए पूर्णांक i, और आपको पता चलेगा कि उत्तर 2i-1x और 2ix के बीच है।

अब आप वास्तव में द्विआधारी खोज कर सकते हैं, 2i-2x से पीछे जाकर शुरू कर सकते हैं। वहां से, आप या तो आगे या पीछे जा सकते हैं, लेकिन आप निश्चित रूप से 2i-3x यात्रा करेंगे, और अगली पुनरावृत्ति आप 2i-4x यात्रा करेंगे, और इसी तरह।

तो पहले चरण में (अधिकतम के लिए खोज), आप 2ix पर गए, और i परीक्षण किए। दूसरे चरण में, बाइनरी परिशोधन, आप कुल (2i-1-1)x पर चलते हैं और i-1 परीक्षण करते हैं। आप d पर किसी बिंदु पर समाप्त हो जाएंगे जो 2i-1 और 2i के बीच है, इसलिए सबसे खराब स्थिति में आप अंतिम बिंदु के 3d चलाएंगे (और सबसे अच्छा, आप 3d/2 पर चले गए होंगे)।आपके द्वारा किए गए परीक्षणों की संख्या 2*ceil(log2(d/x)) - 1 होगी, जो 2*log2(d/x) के एक परीक्षण के भीतर है।

बाइनरी खोज एल्गोरिदम के दौरान आपको किन परिस्थितियों में क्या करना चाहिए? असल में, यह यात्रा के समय और परीक्षण समय, और उत्तर की वांछित परिशुद्धता के अनुपात पर निर्भर करता है। सरल अनुक्रमिक एल्गोरिदम dd/x आकार x और d/x परीक्षणों की चाल के बाद स्थिति d पाता है; उपरोक्त द्विआधारी खोज एल्गोरिदम अधिक 3d पर यात्रा के बाद d स्थिति पाता है लेकिन केवल 2 log(d/x) परीक्षणों के दौरान ही करता है। काफी बोलते हुए, यदि एक परीक्षण आपको d/x यात्रा की लागत से दोगुनी से अधिक खर्च करता है, और अपेक्षित दूरी परिशुद्धता से काफी बड़ी है, तो आपको बाइनरी खोज पसंद करनी चाहिए।

आपके उदाहरण में, आप 200 फीट की सटीकता के साथ परिणाम चाहते हैं; यात्रा का समय 1 मिनट है और परीक्षण का समय 3 मिनट है, जो यात्रा के समय से दोगुना से अधिक है। तो आपको द्विआधारी खोज को प्राथमिकता देना चाहिए, जब तक कि आप उम्मीद न करें कि उत्तर परिशुद्धता के गुणकों की एक छोटी संख्या में पाया जाएगा (जैसा मामला है)। ध्यान दें कि हालांकि बाइनरी एल्गोरिदम चार परीक्षणों और 1000 फीट यात्रा का उपयोग करता है (अनुक्रमिक एल्गोरिदम के लिए तीन परीक्षणों और 600 फीट की तुलना में), 50 फीट की परिशुद्धता में सुधार केवल बाइनरी एल्गोरिदम में चार और परीक्षण और 150 फीट की यात्रा जोड़ देगा, जबकि अनुक्रमिक एल्गोरिदम को 20 परीक्षणों की आवश्यकता होगी।

---

नोट 1: वास्तव में, यह द्विआधारी खोज को समझ में एक लिंक्ड सूची बना सकता है, ठीक ऊपर कलन विधि का उपयोग, अगर परीक्षण की लागत बहुत अधिक है। परीक्षण की लागत मानते हुए सूची में सूचकांक के समान नहीं है, खोज की जटिलता एक रैखिक खोज और द्विआधारी खोज दोनों के लिए O(N) होगी, लेकिन बाइनरी खोज O(log N) परीक्षण और O(N) चरणों को करेगी, जबकि अनुक्रमिक खोज O(N) परीक्षण और O(N) कदम करेंगे। पर्याप्त पर्याप्त एन के लिए, इससे कोई फर्क नहीं पड़ता, लेकिन असली दुनिया के आकार के लिए यह बहुत मायने रखता है।

Answer 2

असल में, बाइनरी खोज यहां लागू की जा सकती है, लेकिन कई बदलावों के साथ। हमें केंद्र को कैल्क नहीं करना चाहिए, बल्कि एक इष्टतम स्थान पर जाना चाहिए।

int length = maxUnchecked - minChecked; 
whereToGo = minChecked + (int)(length * factorIncrease) + stepIncrease; 

क्योंकि हम पहले की स्थिति जहां संचार ऐसा न करने पर, कभी कभी हम वापस जाना चाहिए लगता है की जरूरत है, उसके बाद अन्य रणनीति का उपयोग करने के उपयुक्त हो सकता है

int length = maxUnchecked - minChecked; 
int whereToGo = 0; 
if (increase) 
    whereToGo = minChecked + (int)(length * factorIncrease) + stepIncrease; 
else 
    whereToGo = minChecked + (int)(length * factorDecrease) + stepDecrease; 

तो, हमारे कार्य - इस तरह के इष्टतम factorIncrease यह पता लगाने की , कारक घटाएं, चरणबद्ध करें, चरण घटाएं, एफ (विफलपॉस) की राशि का मान न्यूनतम होगा। कैसे? पूर्ण ब्रूटफोर्स आपकी मदद करेगा यदि एन (कुल लंबाई/200.0 एफ) छोटा है। अन्यथा आप जेनेटिक एल्गोरिदम का उपयोग करने या सरल smth का उपयोग कर सकते हैं।

चरण सटीक = 1, चरण सीमा = [0, एन)। फैक्टर ईपीएस - 1/(4 * एन), कारक सीमा - [0,1)।

अब, सरल कोड (ग #) इस demonstate रहे हैं:

class Program 
{ 
    static double factorIncrease; 
    static int stepIncrease; 
    static double factorDecrease; 
    static int stepDecrease; 
    static bool debug = false; 

    static int f(int lastPosition, int minChecked, int maxUnchecked, int last, int failPos, bool increase = true, int depth = 0) 
    { 

     if (depth == 100) 
      throw new Exception(); 

     if (maxUnchecked - minChecked <= 0) { 
      if (debug) 
       Console.WriteLine("left: {0} right: {1}", minChecked, maxUnchecked); 

      return 0; 
     } 

     int length = maxUnchecked - minChecked; 
     int whereToGo = 0; 
     if (increase) 
      whereToGo = minChecked + (int)(length * factorIncrease) + stepIncrease; 
     else 
      whereToGo = minChecked + (int)(length * factorDecrease) + stepDecrease; 


     if (whereToGo <= minChecked) 
      whereToGo = minChecked + 1; 

     if (whereToGo >= maxUnchecked) 
      whereToGo = maxUnchecked; 

     int cur = Math.Abs(whereToGo - lastPosition) + 3; 

     if (debug) { 
      Console.WriteLine("left: {2} right: {3} whereToGo:{0} cur: {1}", whereToGo, cur, minChecked, maxUnchecked); 
     } 

     if (failPos == whereToGo || whereToGo == maxUnchecked) 
      return cur + f(whereToGo, minChecked, whereToGo - 1, last, failPos, true & increase, depth + 1); 
     else if (failPos < whereToGo) 
      return cur + f(whereToGo, minChecked, whereToGo, last, failPos, true & increase, depth + 1); 
     else 
      return cur + f(whereToGo, whereToGo, maxUnchecked, last, failPos, false, depth + 1); 


    } 

    static void Main(string[] args) 
    { 
     int n = 20; 

     int minSum = int.MaxValue; 
     var minFactorIncrease = 0.0; 
     var minStepIncrease = 0; 
     var minFactorDecrease = 0.0; 
     var minStepDecrease = 0; 

     var eps = 1/(4.00 * (double)n); 

     for (factorDecrease = 0.0; factorDecrease < 1; factorDecrease += eps) 
      for (stepDecrease = 0; stepDecrease < n; stepDecrease++) 
       for (factorIncrease = 0.0; factorIncrease < 1; factorIncrease += eps) 
        for (stepIncrease = 0; stepIncrease < n; stepIncrease++) { 
         int cur = 0; 
         for (int i = 0; i < n; i++) { 
          try { 
           cur += f(0, -1, n - 1, n - 1, i); 
          } 
          catch { 
           Console.WriteLine("fail {0} {1} {2} {3} {4}", factorIncrease, stepIncrease, factorDecrease, stepDecrease, i); 
           return; 
          } 
         } 
         if (cur < minSum) { 
          minSum = cur; 
          minFactorIncrease = factorIncrease; 
          minStepIncrease = stepIncrease; 

          minFactorDecrease = factorDecrease; 
          minStepDecrease = stepDecrease; 
         } 
        } 

     Console.WriteLine("best - mathmin={4}, f++:{0} s++:{1} f--:{2} s--:{3}", minFactorIncrease, minStepIncrease, minFactorDecrease, minStepDecrease, minSum); 

     factorIncrease = minFactorIncrease; 
     factorDecrease = minFactorDecrease; 

     stepIncrease = minStepIncrease; 
     stepDecrease = minStepDecrease; 


     //debug =true; 
     for (int i = 0; i < n; i++) 
      Console.WriteLine("{0} {1}", 3 + i * 4, f(0, -1, n - 1, n - 1, i)); 

     debug = true; 
     Console.WriteLine(f(0, -1, n - 1, n - 1, n - 1)); 

    } 
} 

तो, कुछ मूल्यों (च ++ - factorIncrease, रों ++ - stepIncrease, f-- - factorDecrease):

n = 9 mathmin = 144, f++: 0,1(1) s++: 1 f--: 0,2(2) s--: 1 
n = 20 mathmin = 562, f++: 0,1125 s++: 2 f--: 0,25 s--: 1 

Answer 3

निर्भर करता है जो आप वास्तव में अनुकूलित करना चाहते हैं, उस पर एक इष्टतम खोज पैटर्न तैयार करने का एक तरीका हो सकता है।मुझे लगता है कि आप सबसे खराब केस समय को अनुकूलित नहीं करना चाहते हैं, क्योंकि कई खोज रणनीतियों के लिए सबसे धीमा मामला तब होगा जब ब्रेक बहुत अंत में होगा, और बाइनरी खोज वास्तव में यहां बहुत अच्छी है - आप दिशा बदलने के बिना अंत तक चलते हैं , और आप बहुत सारे स्टॉप नहीं करते हैं।

आप विभिन्न बाइनरी पेड़ों पर विचार कर सकते हैं, और संभवतः एक पत्ते पर जाने के लिए औसत समय निकाल सकते हैं। बाइनरी सर्च एक प्रकार का पेड़ है, और इसलिए चलने के साथ-साथ चल रहा है - एक बहुत ही असंतुलित पेड़ जिसमें प्रत्येक नोड में कम से कम एक पत्ता होता है।

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

यह आपको कुछ गतिशील प्रोग्रामिंग का उपयोग करके हमला कर सकता है। मान लें कि आपने एन सेगमेंट तक की लंबाई के लिए समस्या हल कर दी है, ताकि आप इन लंबाई के इष्टतम समाधान के लिए लागत जान सकें। अब आप एन + 1 सेगमेंट के इष्टतम समाधान का काम कर सकते हैं। एन + 1 सेगमेंट को एन + 1 संभावित तरीकों से दो टुकड़ों में तोड़ने पर विचार करें। इस तरह के लिए, अपने निर्णय बिंदु पर जाने और माप लेने की लागत का काम करें और फिर निर्णय बिंदु के दोनों तरफ सेगमेंट के दो हिस्सों के लिए सर्वोत्तम संभव समाधान की लागत को जोड़ें, संभवतः खाते के लिए भारित उन वर्गों में समाप्त होने की संभावना। उन एन + 1 संभावित तरीकों पर विचार करके, आप एन + 1 खंडों और इसकी लागत को विभाजित करने का सबसे अच्छा तरीका काम कर सकते हैं, और तब तक जारी रहेंगे जब तक कि आप वास्तव में उन अनुभागों की संख्या के लिए सबसे अच्छा समाधान नहीं करते हैं।