पेड़

Question

मैं पेड़ों के लिए एक विभाजन & जीत एल्गोरिथ्म लिखने के लिए कोशिश कर रहा हूँ के लिए विभाजित-और विजय एल्गोरिथ्म। विभाजन कदम के लिए मैं एक एल्गोरिथ्म है कि विभाजित कर दिए गए अनिर्दिष्ट ग्राफ़ जी = (वी, ई) n नोड्स और मीटर के साथ एक नोड को हटाने के द्वारा उप पेड़ों में किनारों की जरूरत है। सभी सबग्राफ में संपत्ति होनी चाहिए जिसमें n/2 नोड्स (पेड़ को जितना संभव हो उतना बराबर विभाजित किया जाना चाहिए) में शामिल होना चाहिए। सबसे पहले मैंने अंतिम शेष नोड को खोजने के लिए पेड़ से सभी पत्तियों को दोबारा हटाने की कोशिश की, फिर मैंने जी में सबसे लंबा रास्ता खोजने की कोशिश की और इसके मध्य नोड को हटा दिया। नीचे दिए गए ग्राफ से पता चलता है कि दोनों दृष्टिकोण से काम नहीं करते:

वहाँ कुछ काम कर रहा एल्गोरिथ्म है कि क्या मैं चाहता हूँ (उपरोक्त मामले में नोड एच रिटर्न) है। (यदि पेड़ निहित नहीं है, किसी भी नोड लेने) जड़ में

प्रारंभ:

Answer 1

मुझे लगता है कि आप इस तरह से एक एल्गोरिथ्म के साथ यह कर सकता है।
प्रत्येक चरण में, चाइल्ड नोड सबसे बड़ा सबट्री (नोड्स की संख्या "नीचे" यह सबसे बड़ी है) है कि में उतर करने का प्रयास करें।
यदि ऐसा करने से एन/2 से बड़ा "ऊपर" नोड्स की संख्या हो, तो रोकें, अन्यथा उस बच्चे के साथ जारी रखें।

इस एल्गोरिथ्म हे (लॉग एन) पेड़ यथोचित संतुलित है और हम प्रत्येक नोड के लिए precomputed subtrees का आकार है, तो होना चाहिए। यदि उन स्थितियों में से कोई एक लागू नहीं होता है, तो यह ओ (एन) होगा।

Answer 2

एक सटीक एल्गोरिथ्म, इस रूप में है

लीफ़्स से प्रारंभ और संबंध तोड़ना रेखांकन बनाने के (वास्तव में सभी के 1 को कर रहे हैं), प्रत्येक चरण में इस लीफ़्स की मूल मिल जाए, और उन्हें नए पेड़ में विलय, प्रत्येक चरण में यदि नोड xr ज्ञात बच्चा है और नोड की डिग्री j ऐसी है कि j = r+1 है, बस एक नोड जो x की चाइल्ड नोड में नहीं है इस मामले में वर्तमान नोड के माता पिता हम कह नोड xnice है, और, कुछ बच्चे ऐसे देखते हैं है उन संबंधित रूटेड उप-निर्माण का निर्माण नहीं किया गया है, इस मामले में हम कहते हैं कि नोड xbad है।

तो प्रत्येक चरण में उनसे संबंधित माता पिता को nice नोड्स कनेक्ट, और यह स्पष्ट है हर कदम हर कदम में भी sum of {degree of parent nice nodes} लेता है आप कम से कम एक अच्छा नोड (कारण आप पत्ती से शुरू) है, तो एल्गोरिथ्म हे है (एन) , और यह पूरी तरह से किया जाएगा, लेकिन नोड को खोजने के लिए जिसे हटाया जाना चाहिए, वास्तव में प्रत्येक चरण में एक डिजॉइंट सूची (उप-सूची सूचियों) के आकार की जांच करने की आवश्यकता होती है, यह निर्माण में ओ (1) में किया जा सकता है, भले ही सूची का आकार n/2 से बराबर या बड़ा है, फिर संबंधित अच्छा नोड का चयन करें। (वास्तव में न्यूनतम सूची में अच्छा नोड ढूंढें जो इस स्थिति को संतुष्ट करता है)।

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

ध्यान दें: मैं नहीं जानता कि इस तरह के हैं कि यह आकार के कुछ हिस्सों n/2 की तुलना में छोटे में एक नोड को हटाने के द्वारा यह विभाजन करना असंभव है एक पेड़ के लिए संभव है।

Answer 3

यह समस्या एक वस्तु का center of mass पाने के लिए समान लगता है। मान लें कि आपके प्रत्येक नोड बराबर द्रव्यमान (वजन) का बिंदु द्रव्यमान है और इसकी स्थिति ग्राफ में स्थिति द्वारा दी गई है। आपका एल्गोरिदम द्रव्यमान का केंद्र खोजने की कोशिश करता है, यानी नोड जिसमें सभी जुड़े उप-पेड़ों में नोड्स का एक समान संचित वजन होता है।

आप प्रत्येक नोड के लिए सभी उप-पेड़ों पर संचित भार की गणना कर सकते हैं। फिर सबसे संतुलित है कि एक चुनें, एसटी। कोई उप-पेड़ n/2 से अधिक वजन का होता है। शायद यह कुछ गतिशील प्रोग्रामिंग के लिए एक काम है।