एम अनसंक्रनाइज्ड प्रतिकृतियों के एक सेट को देखते हुए, हम दिए गए आकार एन का सबसेट कैसे प्राप्त करते हैं जो विश्वसनीय संदेश मल्टीकास्ट वातावरण में अपने संदेश राज्यों को सिंक्रनाइज़ करने के लिए आवश्यक संदेश पुनर्संरचनाओं की संख्या को कम करता है (यानी - सभी प्रतिकृतियां विश्वसनीय रूप से अन्य सभी प्रतिकृतियां संदेश प्राप्त करती हैं))?एन प्रतिकृतियों को सिंक्रनाइज़ करने के लिए पुन: ट्रांसमिशन की संख्या को कम करने के लिए कैसे?
प्रतिकृतियों के संदेश राज्यों में वे सभी संदेश होते हैं जिनमें वे प्रत्येक एक ही डी स्रोत (डी> = एम) से होते हैं। प्रत्येक स्रोत के लिए, एक प्रतिलिपि में उस स्रोत से सभी संदेश कुछ उच्चतम क्रमिक होते हैं (यानी - फीफो, शून्य से शुरू होने वाले छेद के साथ)। इसलिए, प्रतिलिपि के संदेश स्थिति को स्रोतों के अनुरूप प्रत्येक तत्व के साथ, ordinals के वेक्टर के रूप में दर्शाया जा सकता है। वैकल्पिक रूप से, यदि आप चाहें तो डी-आयामी अंतरिक्ष में एक बिंदु के रूप में आप प्रतिकृति के संदेश स्थिति के बारे में सोच सकते हैं।
मान लें कि सभी एम प्रतिकृतियां पहले से ही अपने संदेश राज्य वैक्टरों का आदान-प्रदान कर चुकी हैं, इसलिए उनमें से सभी के पास उनके सभी संदेश राज्यों के एम पंक्तियों x डी कॉलम का मैट्रिक्स है। तो, यह अब पूरी तरह से एक केंद्रीकृत कम्प्यूटेशनल समस्या है कि मैट्रिक्स दिया गया है।
ब्रूट फोर्स दृष्टिकोण जो इष्टतम उत्तर देता है, सभी (एम चयन एन) सबसेट की जांच करना होगा और उस व्यक्ति को चुनना होगा जिसमें उस सबसेट को सिंक्रनाइज़ करने के लिए आवश्यक न्यूनतम पुनर्वितरण की आवश्यकता होती है। समस्या यह है कि इस दृष्टिकोण में एम
में कम से कम फैक्टरियल एसिम्प्टोटिक जटिलता दिखती है, मैं देखना चाहता हूं कि कोई भी बेहतर एसिगिप्टिक सीमाओं के साथ इष्टतम एल्गोरिदम के बारे में जानता है या सोच सकता है?
मूल रूप से, मैं इसे ग्राफिक्स सिद्धांत समस्या के रूप में निपटने की सोच रहा था, प्रतिकृति के संदेश राज्यों को पूरी तरह से जुड़े ग्राफ में शिखर होने के साथ कहा जाता है, जहां किनारे के वजन दो अंत बिंदुओं के संदेश राज्य वैक्टरों के बीच मैनहट्टन दूरी थे। फिर जहां हम एक बार रोक रस्मी एल्गोरिथ्म Kruskal एल्गोरिथ्म के बाद का उपयोग कर मिनट-लिंक agglomerative श्रेणीबद्ध क्लस्टरिंग की तरह कुछ करने के लिए किसी भी समूह के आकार के बराबर या अधिक है एन
कि (एम^2) समय हे में चला सकते हैं, लेकिन मैं काउंटर का निर्माण कर सकते उदाहरण जहां यह तुरंत इष्टतम उत्तर नहीं देता है। उदाहरण के लिए, सादगी के लिए डी = 1 के साथ, एम = 7 प्रतिकृतियां 'ordinals {0, 2, 4, 14, 15, 16, 1 9} और एन = 5. क्रस्कल का एल्गोरिदम क्लस्टर {14, 15, 16 , 1 9} और {0, 2, 4} और फिर अंतिम चरण में उन दो समूहों में शामिल हों। लेकिन हम जो वास्तविक जवाब चाहते थे वह प्रतियों को {2, 4, 14, 15, 16} राज्यों के साथ सिंक्रनाइज़ करना है। हो सकता है कि हम पहले विलय किए गए क्लस्टर को एन से अधिक कर दें और फिर इसे छीनने का प्रयास करें? लेकिन इस उदाहरण में, हम फिर से मूल प्रश्न पूछने के लिए सही हैं क्योंकि क्लस्टर जिस पर हमने वास्तव में रोक दिया था, सभी एम प्रतिकृतियां शामिल हैं! और, ज़ाहिर है, यह समस्या लगभग सरल नहीं है जब डी> 1, जो हमेशा होता है (डी> = एम)।
उपरोक्त दृष्टिकोण के साथ एक और समस्या यह है कि यदि एल्गोरिदम प्रतिकृतियों के दो समूहों को एक बड़े समूह में सिंक्रनाइज़ करने का विकल्प चुनता है, तो यह न केवल अन्य समूहों और नए विलय वाले समूह (जैसे - सामान्य agglomerative में) के बीच की दूरी को प्रभावित करता है पदानुक्रमित क्लस्टरिंग) लेकिन अन्य सभी समूहों के बीच की दूरी भी है क्योंकि वे सभी किसी भी रिट्रांसमिशन से सुनते हैं और लाभ उठा सकते हैं। इसलिए, सभी क्लस्टर के बीच की सभी दूरीें प्रत्येक विलय चरण के बाद और एक आसान तरीके से बदल सकती हैं यदि आप यहां प्राप्त संदेशों से लाभ प्राप्त करने की अनुमति देते हैं, तो फीफो में नहीं, कोई छेद आदेश नहीं है। उदाहरण के लिए, एक प्रतिकृति ए में स्रोत डी 1 से ऑर्डिनल एक्स के माध्यम से संदेश होते हैं। एल्गोरिदम प्रतिकृतियों के दो समूहों को सिंक्रनाइज़ करने का विकल्प चुनता है, न ही ए सहित, जिसे एक्स +5 के एक्स +5 के स्रोत डी 1 से संदेशों की पुन: प्रेषण की आवश्यकता होती है। एक इष्टतम एल्गोरिदम का एहसास होगा कि इन पुनर्संरचनाओं से संभावित लाभ, भले ही वे अपने फीफो से परे हों, एक्स + 4 के माध्यम से एक्स + 1 के संदेश अंतर के साथ स्रोत डी 1 के लिए नो-होल ऑर्डिनल।
एक अलग तरीके से मैंने इसे संभालने के बारे में सोचा था, यह एक ज्यामितीय समस्या पर विचार करना था जहां एम प्रतिकृतियां 'राज्य डी-आयामी एल 1 अंतरिक्ष में बिंदुओं का प्रतिनिधित्व करते हैं। फिर हम सबसे कम "वॉल्यूम" उत्तल हल ढूंढना चाहते हैं जिसमें कम से कम एन अंक होते हैं। यह वास्तव में एक अच्छा दृष्टिकोण नहीं हो सकता है लेकिन इसके बारे में सोचने से ज्यामितीय रूप से इस विचार को कैप्चर किया जाता है कि सभी प्रतिकृतियां प्रतिकृतियों के सिंक्रनाइज़ेशन के किसी भी दो सेट से लाभान्वित हो सकती हैं। उनकी अधिकांश दूरी को दो सेट 'राज्यों के विलय द्वारा बनाई गई नई वस्तु की सतह (शिखर नहीं!) तक कम कर दिया जाएगा।
संपादित करें - मैंने इसके बारे में सोचा एक और तरीका मैंने जो उदाहरण दिया था, उससे आया था। प्रत्येक स्रोत डीएक्स के लिए एन प्रतिकृतियों का सबसेट मिलता है जिसके लिए उस स्रोत पर सिंक्रनाइज़ करने के लिए न्यूनतम संख्या में पुन: ट्रांसमिशन की आवश्यकता होती है। यह काफी आसान है। तब समस्या यह है कि आपको इन डी सबसेट्स को कवर करने के लिए इन डी सबसेट्स की तुलना और संशोधित करना होगा। यह पूरी तरह से गठित विचार नहीं है क्योंकि प्रत्येक आयाम डीएक्स में न्यूनतम एन वैश्विक अंतरिक्ष में एक स्थानीय न्यूनतम है जो उस क्षेत्र के लिए वैश्विक स्तर पर इष्टतम उत्तर के रूप में गलत क्षेत्र में हो सकता है। वैसे भी, यह सोचने का एक और विचार है।
EDIT2 - प्राइम + क्रस्कल के एल्गोरिदम पर वापस जाना और यह अनदेखा करना कि प्रत्येक विलय सभी समूहों के बीच सापेक्ष दूरी को अपडेट करता है, यह सच है कि जब हम पहले क्लस्टर को खोजते हैं जिसका आकार एन के बराबर या उससे अधिक है, तो इष्टतम उत्तर होना चाहिए उस क्लस्टर के कुछ सबसेट हो? यदि क्लस्टर का आकार एन के बराबर है, तो हम कर रहे हैं। यदि क्लस्टर का आकार एन से अधिक है, तो क्या हम क्लस्टर के सेंट्रॉइड की गणना करने और सेंट्रॉइड के लिए एन निकटतम प्रतिकृतियां चुनने की तरह कुछ कर सकते हैं? क्या यह इष्टतम उत्तर देगा? यह अभी भी सही नहीं लगता है क्योंकि यह Centroid से विभिन्न दूरी की "दिशात्मकता" पर विचार नहीं करता है। यही है, यह दो प्रतिकृतियों के बीच अंतर नहीं करता है जो डी-आयामी अंतरिक्ष में एक-दूसरे के करीब हैं (जिसे इसे पक्षित करना चाहिए) क्योंकि दो प्रतिकृतियों के विपरीत जो केंद्र के संबंध में एक दूसरे से "विपरीत" दिशाओं में हैं। हो सकता है कि हम क्लस्टर में प्रतिकृतियों के न्यूनतम स्पैनिंग पेड़ को देख सकें और किसी भी तरह से कनेक्ट होने वाले न्यूनतम वजन सबसेट को खोजने के लिए कुशलता से इसे छेड़छाड़ कर सकते हैं?
प्रासंगिक एल्गोरिदम के लिए कोई भी विचार या पॉइंटर्स की सराहना की जाएगी!
आप इस समस्या में "संदेश रीट्रान्समिशन" को कैसे परिभाषित कर रहे हैं? "संदेश" में क्या शामिल है? क्या सभी प्रतिकृतियों को एक संदेश प्रेषित करना एक ही प्रतिकृति के समान संचार के समान लागत है? मुझे यह भी समझ में नहीं आता कि क्यों {2, 4, 14, 15, 16} आपके उदाहरण में "वास्तविक उत्तर" है। – mhum
@mhum एक संदेश पुन: प्रेषण तब होता है जब एक संदेश, जो पहले से ही एक या अधिक वर्तमान प्रतिकृतियों के लिए जाना जाता है, उनमें से एक समूह द्वारा मल्टीकास्ट है। यह प्रतिकृतियों की सहायता के लिए किया जाता है जो कि अभी तक यह संदेश नहीं जानते हैं कि सभी प्रतिकृतियां संदेश संदेश सिंक्रनाइज़ होने के करीब हैं (यानी - बराबर)। एक संदेश में डेटा के कुछ बाइट होते हैं। सादगी के लिए, प्रत्येक संदेश को पुन: ट्रांसमिशन पर किसी भी अन्य के रूप में समान रूप से महंगा मानें। हां, सभी प्रसारण मल्टीकास्ट हैं और विश्वसनीय रूप से समूह में सभी तक पहुंचते हैं। – jschultz410
{2, 4, 14, 15, 16} उत्तर है क्योंकि यह आकार एन = 5 का सबसेट है जिसके लिए अपने सभी राज्यों को 16 के बराबर लाने के लिए सबसे कम पुनर्वितरण की आवश्यकता होती है। संदेश 3 से 16 होना चाहिए पुनः प्रेषित, तो 14 संदेश। अन्य लगभग इष्टतम सेट {4, 14, 15, 16, 1 9} होंगे, लेकिन इसके लिए 5 से 1 9 = 15 रिट्रांसमिशन और {0, 2, 4, 14, 15} की आवश्यकता होती है, जिसके लिए 1 से 15 = 15 रिट्रांसमिशन की आवश्यकता होती है। एक आयाम में यह समस्या बहुत आसान है, लेकिन कल्पना करें कि इसके बजाय 7 या 10 आयाम थे और प्रत्येक प्रतिकृति प्रत्येक आयाम के भीतर मनमाने ढंग से स्थितियों पर होगी। – jschultz410