कैसे तय करने के लिए दो व्यक्तियों

Question

जुड़े हुए हैं कि क्या यहाँ समस्या है:

दो व्यक्तियों को संभालने एक सामाजिक नेटवर्किंग वेबसाइट, कैसे तय करने के लिए कि क्या वे या नहीं जुड़े हुए हैं में पंजीकृत हैं?

मेरा विश्लेषण (और पढ़ने के बाद): असल में, सवाल एक ग्राफ में ए से बी का सबसे छोटा रास्ता ढूंढ रहा है। मुझे लगता है कि बीएफएस और डिजस्ट्रा के एल्गोरिदम दोनों यहां काम करते हैं और समय जटिलता बिल्कुल वही है (ओ (वी + ई)) क्योंकि यह एक असीमित ग्राफ है, इसलिए हम प्राथमिकता कतार का लाभ नहीं उठा सकते हैं। तो, एक साधारण कतार समस्या को हल कर सकती है। लेकिन, उनमें से दोनों समस्या को हल नहीं करते हैं: उनके बीच पथ खोजें।

इस बिंदु पर बिडड्रोलोल बेहतर समाधान होना चाहिए।

Answer 1

नोट: उत्तर संपादित किया गया।

कोई भी विधि बहुत धीमी हो सकती है। यदि आपको बार-बार ऐसा करने की ज़रूरत है, तो ग्राफ के कनेक्टेड घटकों को ढूंढना सबसे अच्छा है, जिसके बाद कार्य एक छोटा ओ (1) ऑपरेशन बन जाता है: यदि दो लोग एक ही घटक में हैं, तो वे जुड़े हुए हैं।

ध्यान दें कि पहली बार कनेक्टेड घटकों को ढूंढना धीमा हो सकता है, लेकिन ग्राफ में जोड़े गए नए किनारों/नोड्स के रूप में उन्हें अद्यतन रखने के लिए तेज़ है।

कनेक्टेड घटकों को खोजने के लिए कई विधियां हैं।

एक विधि ग्राफ के लैपलासीन का निर्माण करना है, और इसके eigenvalues ​​/ eigenvectors को देखना है। शून्य eigenvalues ​​की संख्या आपको जुड़े घटकों की संख्या देता है। संबंधित eigenvectors के गैर-शून्य तत्व संबंधित घटकों से संबंधित नोड्स देता है।

एक और तरीका है निम्नलिखित लाइनों के साथ है:

1. नोड्स के एक परिवर्तन तालिका बनाएं। सरणी के तत्व n में नोड की अनुक्रमणिका होती है जो नोड n में बदल जाती है। ग्राफ में सभी किनारों (i,j) (i और j के बीच एक कनेक्शन को संकेतित) के माध्यम से

2. लूप:

   • कंप्यूट रिकर्सिवली जो नोड कर i और j वर्तमान तालिका के आधार पर करने के लिए बदलना। आइए परिणामों को k और l द्वारा इंगित करें। को l में बदलने के लिए प्रविष्टिअपडेट करें। l पर इंगित करने के लिए प्रविष्टियां i और j अपडेट करें।

3. तालिका के माध्यम से फिर से लूप, और सीधे बात करने के लिए नोड यह रिकर्सिवली को बदल देती है लिए प्रत्येक प्रविष्टि अद्यतन करें।

अब उसी कनेक्टेड घटक में नोड्स में परिवर्तन तालिका में एक ही प्रविष्टि होगी। तो यह जांचने के लिए कि क्या दो नोड जुड़े हुए हैं, बस जांचें कि क्या वे एक ही मान में बदल जाते हैं।

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

Answer 2

दोनों के बीच एक रास्ता खोजने के लिए, आपको पहली बार चौड़ाई वाली खोज शुरू करनी चाहिए। सबसे पहले A के सभी पड़ोसियों को ढूंढें, फिर A आदि के सभी पड़ोसियों के सभी पड़ोसियों को ढूंढें। एक बार B मारा जाता है, न केवल आपके पास A से B तक कोई पथ है, लेकिन आपके पास भी कम से कम ऐसा पथ है।

Dijkstra's algorithm चट्टानों, और आप दोनों अंत से काम करके इसे गति देने में सक्षम हो सकते हैं, यानी A के पड़ोसियों और B के पड़ोसियों को ढूंढें, और तुलना करें।

यदि आप पहली बार गहराई से खोज करते हैं, तो आप एक समय में एक पथ का अनुसरण कर रहे हैं। यह बहुत धीमा होगा।

Answer 3

मुझे लगता है कि सही मानदंड है: ए और बी के बीच कम से कम एन पथ हैं तो के, या ए और बी मरने से जुड़े हुए हैं। मैं के = 3 और एन के पास 5 के पास जाऊंगा, यानी 5 आम दोस्त हैं।

Answer 4

एक तरह से संघ का उपयोग का पता लगाएं, सभी लिंक union(from,to) जोड़ने के लिए है, और अगर find(A) is find(B) तो यह सच है है A और B जुड़े हुए हैं। यह रिकर्सिव खोज से बचाता है लेकिन यह वास्तव में सभी जोड़ों की कनेक्टिविटी की गणना करता है और आपको A और B से कनेक्ट करने वाले पथ नहीं देता है।

Answer 5

यदि आप सोशल नेटवर्क पर दो लोग जुड़े हैं या नहीं, तो यह बहुत लंबा लगेगा!

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

तुम भी विकिपीडिया से A* search. उपयोग करने में सक्षम हो सकता है: "एक * एक सबसे पहले खोज का उपयोग करता है और एक लक्ष्य नोड के लिए (एक या अधिक संभव लक्ष्यों में से) किसी प्रारंभिक नोड से कम से कम लागत वाली पथ पाता है। "

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