जांचें कि निर्देशित विश्वकोश ग्राफ में दो शीर्षकों के बीच कोई पथ मौजूद है - प्रश्न

Question

इस प्रश्न को प्रति प्रश्न O (n + m) में आसानी से हल किया जा सकता है, हालांकि यह बेहतर है कि बेहतर जटिलता में ऐसे प्रश्नों का उत्तर दें, (एन²)?

पेड़ में इसे पूर्व-आदेश और क्रम में काम करके आसानी से किया जा सकता है। मैंने डीएजी में कुछ ऐसा करने की कोशिश की लेकिन इसका कोई मतलब नहीं है।

मैंने डीएजी समस्या में एलसीए में इस समस्या को बदलने की भी कोशिश की, लेकिन डीएजी में एलसीए खोजने के लिए पर्याप्त तेज़ी से हल नहीं किया जा सकता है।

---

बाधाओं के साथ सटीक होना मान लें:

n - कोने की संख्या, 10^5

मीटर - किनारों की संख्या, अप करने के लिए 10^5

क्ष - प्रश्नों की संख्या, 10^5

Answer 1

दिलचस्प सवाल। मेरा अंतर्ज्ञान कहता है "नहीं"। मैंने हालांकि इसे नहीं सोचा है।

हालांकि (यह प्रश्न मानना ​​सैद्धांतिक नहीं है) व्यावहारिक प्रयोजनों के लिए, आप Bloom filter का उपयोग कर सकते हैं।

ब्लूम फ़िल्टर का उपयोग करके आपकी समस्या का एक संभावित समाधान पहले ग्राफ के के विभिन्न ऑर्डर उत्पन्न करेगा, और प्रत्येक के लिए, मैपिंग को उस क्रम में नोड से इसकी अनुक्रमणिका में स्टोर करें। फिर, एन 1 से एन 2 तक "पहुंचने योग्यता" का परीक्षण करने के लिए, यदि आप इंडेक्स-ऑफ-एन 1 इंडेक्स-एन-एन 2 से कम है तो यह जांच (foreach ऑर्डर) (यह चेक ओ (1) है)। यदि यह सभी ऑर्डर के लिए है, तो यह बहुत अच्छी संभावना (assuming K is big enough) के साथ पहुंच योग्य है। (आपके वास्तविक विश्व उपयोग के मामले के आधार पर, कभी-कभी ऐसे झूठे सकारात्मक तत्वों को भूगर्भित करने के लिए भी ठीक हो सकता है, या फिर आप विश्वसनीय ओ (एन + एम) चेक चला सकते हैं)। अन्यथा, यह निश्चित रूप से नहीं है।

Answer 2

मुझे एहसास है कि निम्नलिखित पंक्तियों के साथ समाधान हो सकता है, लेकिन इसका कोई पूर्ण समाधान नहीं है।

एस को शिखर का उप-समूह बनने दें। ग्राफ़ में प्रत्येक vertex V के लिए, सेट D_S (V) पर विचार करें, जिसे मैं निम्नानुसार परिभाषित करता हूं: D_S (V) = {V} यदि एस में वी है, और अन्यथा, D_S (V) {V} का संघ है वी के सभी प्रत्यक्ष वंशजों के लिए डीएस (डब्ल्यू) सेट करता है। (यानी, यह "वी के सभी अंतिम वंशज हैं, लेकिन जब भी आप वी के तत्व को दबाते हैं तो रिकर्सन को रोकें।) सवाल यह है: क्या हम एक सेट पा सकते हैं एस जैसे कि एस का आकार ओ (एफ (एन)) है और डीसी (वी) सभी वी के लिए आकार ओ (जी (एन)) का है, और जहां एफ और जी असम्बद्ध रूप से उपनिवेश हैं? (शायद हम दोनों के लिए sqrt प्राप्त कर सकते हैं, उदाहरण के लिए।)

यदि हम इसे पा सकते हैं, तो मैं निम्नलिखित रणनीति का सुझाव देता हूं। प्रीप्रोकैसिंग के लिए, एस में प्रत्येक यू के लिए एक हैश तालिका बनाएं जिसमें अंततः सभी यूके से पहुंच योग्य हो। यह ओ (एफ (एन) * एम) में प्राप्त किया जा सकता है; यह ओ (एन^2) से जरूरी नहीं है, लेकिन कम से कम ओ (एम * क्यू) से बेहतर है।

अब एक प्रश्न का उत्तर देने के लिए "क्या यू वी से पहुंच योग्य है?", अगर एस में वी है तो यह मामूली है, अन्यथा, हम जांचते हैं कि वी = यू, इस मामले में यह भी मामूली है। आखिरकार, हम वी के सभी वंशजों को वही प्रक्रिया लागू करते हैं, जो कि "हां" लौटते हैं, यदि उत्तर उपरोक्त दो मामलों में से किसी एक के माध्यम से "हां" है, लेकिन "नहीं" केवल तभी होता है जब हम कभी नहीं पाते हैं। यह रिकर्सन ओ (जी (एन)) कदम।

प्रश्न यह है कि एस को चुनने का तरीका यह है कि मुझे लगता है कि ग्राफ कुछ प्रक्रिया से उत्पन्न होता है, जहां आउट-डिग्री एक पावर लॉ का पालन करती है, कोई भी उच्चतम आउट-डिग्री के साथ वर्ग (एन) शिखर ले सकता है।लेकिन उदाहरण के लिए यदि हमारे पास एन = 2 * के शिखर (i, 0) और (i, 1) पर ग्राफ है, तो के^2 किनारों के साथ: प्रत्येक (i, 0) से प्रत्येक (जे, 1); तो वहां कोई उपयुक्त सबसेट एस नहीं है। लेकिन शायद ऐसे ग्राफ जिनके पास उपयुक्त एस नहीं है, वे एक समानता की डिग्री चाहते हैं जिसका हम फायदा उठा सकते हैं ... या शायद नहीं। मुझे नहीं पता। कोई विचार, मुझे बताओ!