सबसे तेजी से कम से कम फैले पेड़ एल्गोरिथ्म

Question

http://en.wikipedia.org/wiki/Minimum_spanning_tree

मैं बेंचमार्क करने के लिए देख रहा हूँ मेरी न्यूनतम सर्वश्रेष्ठ में से सबसे अच्छा के खिलाफ पेड़ एल्गोरिथ्म फैले। क्या कोई जानता है कि मुझे इन एल्गोरिदम का सी ++ कार्यान्वयन कहां मिल सकता है? मैं binged और googled और कुछ भी नहीं मिला। यदि ये एल्गोरिदम सर्वोत्तम हैं, तो निश्चित रूप से कहीं सी ++ कार्यान्वयन होना चाहिए?

सबसे तेजी से कम से कम फैले पेड़ तारीख को एल्गोरिथ्म डेविड कार्गर, फिलिप क्लेन, और रॉबर्ट Tarjan, जो एक रेखीय समय Borůvka एल्गोरिथ्म और रिवर्स की एक संयोजन के आधार पर यादृच्छिक एल्गोरिथ्म पाया द्वारा विकसित किया गया था -डिलीट एल्गोरिदम। [2] [3] बर्नार्ड चाज़ेल द्वारा सबसे तेज़ गैर-यादृच्छिक एल्गोरिदम, , मुलायम ढेर पर आधारित है, अनुमानित प्राथमिकता कतार। [4] [5] इसका चलने का समय ओ (एम α (एम, एन)) है, जहां एम किनारों की संख्या है, n अक्षरों की संख्या है और α एकरमेन फ़ंक्शन के शास्त्रीय कार्यात्मक उलटा है। फ़ंक्शन α बहुत धीरे-धीरे बढ़ता है, इसलिए कि सभी व्यावहारिक उद्देश्यों के लिए यह को 4 से अधिक स्थिर नहीं माना जा सकता है; इस प्रकार Chazelle के एल्गोरिदम रैखिक समय के बहुत करीब लेता है। यदि किनारे के वजन बाध्य बिट लंबाई के साथ पूर्णांक हैं, तो निर्धारक एल्गोरिदम रैखिक चलने वाले समय के साथ जाने जाते हैं। [6] चाहे रैखिक सामान्य वजन के लिए चलने का समय अभी भी एक खुला प्रश्न है, के साथ एक निर्धारक एल्गोरिदम मौजूद है। हालांकि, सेठ पेटी और विजया रामचंद्रन के पास एक सिद्ध इष्टतम निर्धारिती न्यूनतम स्पैनिंग पेड़ एल्गोरिदम पाया गया है, कम्प्यूटेशनल जटिलता जिसमें अज्ञात है। [7]

मैं पहले ही बूस्ट सी ++ के ग्राफ एल्गोरिदम के खिलाफ परीक्षण करता हूं।

Answer 1

जब विकिपीडिया पृष्ठ "सबसे तेज़ न्यूनतम स्पैनिंग पेड़ एल्गोरिदम" कहता है, तो उनका मतलब यह है कि सबसे कम एसिम्प्टोटिक सीमाओं वाला एल्गोरिदम है - इस मामले में, ओ (एम α (एम, एन)), एम, एन के साथ , और α परिभाषित उद्धरण के रूप में परिभाषित किया गया है। बस रखें, इसका मतलब है कि बहुत बड़े इनपुट मानों के लिए, सी के कुछ मूल्य के लिए हमेशा लिया गया समय सी * एम * α (एम, एन) द्वारा बाध्य किया जाएगा, लेकिन ध्यान दें कि सी बहुत बड़ा हो सकता है - यानी , छोटे इनपुट मानों पर लागू होने पर यह एल्गोरिदम दूसरों की तुलना में धीमी हो सकती है, भले ही यह बहुत बड़े इनपुट मानों के लिए दूसरों की तुलना में तेज़ हो।

दो एल्गोरिदम की एसिम्प्टोटिक सीमाओं की तुलना करते समय, यह देखने के लिए कोई "परीक्षण" नहीं है कि आप कौन सा तेज़ है - आप केवल प्रत्येक एल्गोरिदम की एसिम्प्टोटिक सीमाएं साबित करते हैं, और देखें कि कौन सा निचला है। ("Asymptotic" के रूप में इनपुट आकार अनंत को जाता है व्यवहार को दर्शाता है - और यह अनंत आकार इनपुट मूल्यों के साथ परीक्षण चलाने के लिए मुश्किल है।)

लेकिन ध्यान दें कि ऐसी स्थितियां आप नहीं asymptotically का उपयोग करना चाहिए हैं कि सबसे तेज़ एल्गोरिदम। यदि "सी" बहुत बड़ा है, तो आप छोटे डेटा मानों के लिए एक सरल एल्गोरिदम का उपयोग करना बेहतर हो सकते हैं।

मेरा अनुमान है कि आपका एल्गोरिदम सी पर सुधार कर सकता है, लेकिन एसिम्प्टोटिक सीमाओं पर नहीं। लेकिन अगर मैं उस पर गलत हूं, तो आपको इसे एसीएम में जमा करना चाहिए!

अधिक जानकारी के लिए, देखें: http://en.wikipedia.org/wiki/Big_O_notation

Answer 2

www.dcc.uchile.cl/~raparede/publ/09algorIQS.pdf "छंटाई, ढेर, और न्यूनतम स्पैनिंग पेड़ पर", गोंजालो नवारो और रोड्रिगो पेरेडेस

कुछ "सर्वोत्तम सर्वश्रेष्ठ" और कोर स्मृति माप प्रस्तुत करता है, और पुराने कार्यान्वयन के संदर्भ देता है।

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