मेट्रिक स्पेस में कुशल न्यूनतम स्पैनिंग पेड़

Question

मेरे पास कुछ मीट्रिक स्पेस (Jaccard Distance से सुसज्जित) में अंक का एक बड़ा सेट (संख्या> 10000 संख्या) है। मैं किनारों पर वजन के रूप में मीट्रिक का उपयोग करके, उन्हें एक न्यूनतम स्पैनिंग पेड़ से जोड़ना चाहता हूं।

• वहाँ एक एल्गोरिथ्म है कि O (n) समय की तुलना में कम में चलाता है?
• यदि नहीं, तो क्या कोई एल्गोरिदम है जो ओ (एन) से कम समय में चलता है) औसत समय (संभवतः यादृच्छिकरण का उपयोग करके)?
• यदि नहीं, तो क्या कोई एल्गोरिदम है जो ओ (एन) से कम समय में चलता है और न्यूनतम स्पैनिंग पेड़ का अच्छा अनुमान देता है?
• यदि नहीं, तो क्या ऐसा कोई कारण है कि ऐसा एल्गोरिदम मौजूद नहीं हो सकता है?

अग्रिम धन्यवाद!

नीचे पोस्टर के लिए संपादित करें: न्यूनतम स्पैनिंग पेड़ खोजने के लिए शास्त्रीय एल्गोरिदम यहां काम नहीं करते हैं। उनके चलने वाले समय में उनके पास एक ई कारक है, लेकिन मेरे मामले में ई = एन क्योंकि मैं वास्तव में पूरा ग्राफ मानता हूं। मेरे पास सभी 4 9 99 5000 संभव किनारों को स्टोर करने के लिए पर्याप्त स्मृति नहीं है।

Answer 1

जाहिर है, इस के अनुसार: Estimating the weight of metric minimum spanning trees in sublinear time कोई निर्धारिती ओ (एन^2) नहीं है (नोट: छोटा ओह, जो शायद ओ (एन^2), मुझे लगता है) एल्गोरिदम से कम है। वह पेपर मेट्रिक न्यूनतम वजन फैलाने वाले पेड़ के लिए एक उप-रैखिक यादृच्छिक एल्गोरिदम भी प्रदान करता है।

यह भी देखें इस पेपर को देखें: An optimal minimum spanning tree algorithm जो एक इष्टतम एल्गोरिदम प्रदान करता है। पेपर यह भी दावा करता है कि इष्टतम एल्गोरिदम की जटिलता अभी तक ज्ञात नहीं है!

पहले पेपर में संदर्भ उपयोगी होना चाहिए और यह कि पेपर शायद आपके प्रश्न के लिए सबसे प्रासंगिक है।

उम्मीद है कि मदद करता है।

Answer 2

जब मैं 3-4 साल पहले एक बहुत ही समान समस्या को देख रहा था, तो मुझे साहित्य में एक आदर्श समाधान नहीं मिला।

मुझे लगता है कि चाल "संभावित अच्छे" किनारों का "छोटा" सबसेट ढूंढना है, जिसे आप सादे पुराने क्रस्कल पर चला सकते हैं। आम तौर पर, यह संभावना है कि कई एमएसटी किनारों को किनारों के सेट में पाया जा सकता है जो प्रत्येक चरम पर के निकटतम पड़ोसियों में शामिल होते हैं, कुछ छोटे के के लिए। ये किनारों ग्राफ को फैला नहीं सकते हैं, लेकिन जब वे नहीं करते हैं, तो प्रत्येक घटक को एक कशेरुक (यादृच्छिक रूप से चुना गया) में ध्वस्त किया जा सकता है और प्रक्रिया दोहराई जाती है। (बेहतर सटीकता के लिए, एक नया प्रतिनिधि "सुपरवरटेक्स" बनने के बजाय, कुछ छोटे नंबर आर प्रतिनिधियों के लिए चुनें और अगले दौर में सभी आर^2 सुपरवर्टिस के बीच 2 दूरी, न्यूनतम चुनने की जांच करें।)

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

अन्यथा, आप क्लस्टरिंग उपयोगी दृष्टिकोण हो सकते हैं: Clustering large datasets in arbitrary metric spaces कुछ कागजात मैंने पाया कि स्पष्ट रूप से वस्तुओं जरूरी है कि एक इयूक्लिडियन स्थान में परिमित आयामी वैक्टर नहीं हैं के साथ सौदों में से एक है, और जो computationally महंगा करने की संभावना पर विचार कर देता है दूरी कार्यों।