असीमित एक आयामी ग्राफ में छेद खोजने के लिए एल्गोरिदम

Question

एक गाय एक अनंत बाड़ के सामने खड़ी है। दूसरी तरफ घास है। गाय इस घास में जाना चाहता है। इस बाड़ के साथ कहीं एक छेद है जिसके माध्यम से गाय दूसरी तरफ जा सकती है। गाय से छेद तक दूरी डी की संभावना संभाव्यता वितरण एफ (डी) से जुड़ी है यानी संभावना है कि छेद गाय से दूर कदम दूर है (एफ) द्वारा दिया जाता है। ध्यान दें कि हम सभी दूरीों को असतत के रूप में सोचते हैं यानी वे हमेशा गाय द्वारा उठाए गए कदमों के संदर्भ में मापा जाता है। गाय नकारात्मक पूर्णांक चरणों के साथ-साथ सकारात्मक पूर्णांक चरणों, यानी क्रमशः बायीं तरफ कदम और दाईं ओर कदम उठा सकती है। साथ ही, हम जानते हैं कि Σ (k = -∞)^∞ | k | ⋅f (k) < ∞। हम एक एल्गोरिदम का वर्णन करना चाहते हैं जो संभावना के साथ छेद पा सकता है 1.

समस्या 1 एल्गोरिदम के लिए संभावित स्थिति के साथ छेद खोजने में सक्षम होने के लिए पर्याप्त स्थिति क्या है? समस्या 2 ऐसे एल्गोरिदम का वर्णन करें।

Answer 1

मुझे ऐसा लगता है कि आपकी समस्या, के रूप में कहा गया है, एक छोटी सी समाधान है: मौजूदा स्थिति में छेद के लिए

• जांच
• आगे की पैदल दूरी 1 कदम है, छेद
• टहलने के लिए जाँच पिछड़े 2 कदम, छेद के लिए जांच
• आगे 3 चरणों तक चलें, छेद
• पिछड़े 4 चरणों पर चलें, छेद की जांच करें ...

यह पैदल दूरी पर बेशक संभावना 1. के साथ सभी रिश्तेदार पूर्णांकों का दौरा करेंगे, क्या आप वास्तव में चाहते हैं चरणों की औसत राशि के लिए अनुकूलन करने के लिए है कि गाय लेने के लिए है, जो search game problem रूप में जाना जाता होगा। समाधान एक 1-आयामी घातीय "सर्पिल" है; आप केवल 1-2-3-4-5 अंकगणितीय अनुक्रम को एक ज्यामितीय के साथ प्रतिस्थापित करते हैं, प्रत्येक बार 2 से गुणा करते हैं।यही कारण है: मौजूदा स्थिति में छेद के लिए

• जांच
• की पैदल दूरी पर आगे 1 कदम, हर कदम पर छेद के लिए जाँच
• की पैदल दूरी पर पिछड़े 2 कदम, हर कदम पर छेद के लिए जाँच
• आगे 4 कदम पैदल दूरी , हर कदम पर छेद के लिए जाँच
• की पैदल दूरी पर पिछड़े 8 कदम, हर कदम पर छेद के लिए जाँच ...

"गाय-पथ समस्या" है, जो के लिए गूगल आपके एन-वेस क्रॉस रोड पर आपके सामान्यीकरण (आपके पास केवल दो, "बाएं" और "दाएं" हैं)

Answer 2

क्या आप यह कर सकते हैं कि छेद किसी दिए गए स्थान पर है या नहीं? यदि ऐसा है, तो ऐसा लगता है कि संभावना कम करने के क्रम में केवल एक ही चीज है। आपको छेद खोजने की गारंटी होगी, लेकिन यह मनमाने ढंग से लंबा समय ले सकता है। (आप गारंटी दे सकते हैं कि आपको खोजों की एक निश्चित संख्या के भीतर एक छेद मिलेगा यदि केवल तभी एफ के पास सीमित समर्थन है - यानी, अगर वहां केवल अंततः कई के लिए f (k)> 0) हैं। यदि छिपे हुए अज्ञात संख्याएं हैं, तो आप केवल यह निर्धारित करने में सक्षम होंगे कि यदि आप सीमित समर्थन रखते हैं तो आप उन्हें सभी को ढूंढ चुके हैं।

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

यदि आप समस्या के संदर्भ का वर्णन कर सकते हैं तो यह सहायक होगा। जैसा कि यह खड़ा है, ग्राफ वास्तव में समीकरण में प्रवेश नहीं करता है - आपके पास सिर्फ कप का एक गुच्छा है, और आप यह पता लगाने की कोशिश कर रहे हैं कि किसके पास एक गेंद है।

Answer 3

बुलेट शॉट बनाएं, वैरिएबल आकार वाली अंतराल वाली दीवारों को बीच में रखें और देखें कि दीवार दीवार पर गोली नहीं दी गई है। वहां से चले जाओ। आपको पता होना चाहिए कि कैसे होल फ़ंक्शन को ग्राफ़ करना है (शायद अनुमान लगाएगा, केवल अंतहीन छेद तक नहीं)।

Answer 4

findHole(S) 
{ 
    k = 0; 
    previous_k = 0; 

    current_f = f(k, S); 
    if (current_f == 1) return (S); 

    previous_f = 0; 
    //While the probability of finding a hole increases, 
    //we increase k and verify if the vertex at k steps is a hole 
    while (current_f >= previous_f) 
    { 
    previous_f = current_f; 
    previous_k = k; 

    //As closer to probability 1 we are, as smaller steps we make 
    k = (1 - current_f) * MAX_STEP_SIZE; 
    current_f = f(k, S); 
    if (current_f == 1) return (S); 
    } 

    //If we overshot our hole and the probability of finding 
    //a hole at k steps distance has started to decrease, we 
    //perform a binary search within the boundaries of the interval 
    //[previous_k, k], with probabilities in [previous_f, current_f], 
    //having a guarantee that our hole is within this interval 
    return binSearch(previous_k, k, S); 
}