2016-11-23 6 views
5

मेरे समस्या निम्नलिखित है:केंद्र नोड (दूरी भावना की एक न्यूनतम राशि में)

को देखते हुए एक पेड़ (वी, ई), केंद्र नोड वी लगता है ऐसा है कि योग {वी में w} [ dist (v, w)] न्यूनतम है, जहां dist (v, w) v से w से सबसे कम पथ में किनारों की संख्या है। एल्गोरिदम ओ (एन) समय में चलना चाहिए (एन पेड़ में नोड्स की संख्या होने के नाते)।

प्रश्न here और here भी केंद्र नोड के लिए पूछते हैं लेकिन इसे अलग-अलग परिभाषित करते हैं।

मैंने कठोर कदमों से गुजरना नहीं है लेकिन मुझे वास्तव में लगता है कि मेरी समस्या का समाधान this problem के समाधान के समान होना चाहिए।

हालांकि, मैंने फैसला किया कि मुझे अपनी समस्या को समुदाय के साथ साझा करना चाहिए क्योंकि मुझे the link पर नेविगेट करने में कुछ समय लगा, हालांकि यह सीधे सवाल का जवाब नहीं देता है।

+0

@maraca - मुझे लगता है कि आप जो कह रहे हैं वह थोड़ा गलत हो सकता है। ऐसे मामले के बारे में सोचें जहां परिणामी पेड़ की ऊंचाई एक पेड़ से एक और है जो आपको _one_ शाखा के कारण मिलती है, लेकिन दूरी की कुल राशि कम होती है। मुझे पूरी तरह से यकीन नहीं है कि यह काउंटर उदाहरण वास्तव में अस्तित्व में हो सकता है, मैं केवल यह सुझाव दे रहा हूं कि इसकी जांच की जानी चाहिए ... –

+0

@maraca हां, मैं एक इष्टतम रूट खोजना चाहता हूं। मेरे पास इसके बारे में है और मैं आपको एक काउंटर-उदाहरण दे सकता हूं जहां समाधान समान नहीं हैं। एक पेड़ की कल्पना करें जहां रूट में कई पड़ोसियों हैं, एम कहें, जिनमें से प्रत्येक छुट्टी है, और लंबाई की एक 'पूंछ' 3 कहती है (जिसमें 3 शिखर होते हैं)। फिर सबसे कम गहराई से खोजा गया रूट वर्टेक्स कई पड़ोसियों के साथ नहीं होगा (यह पूंछ पर पहला चरम होगा, जो हर दूसरे कशेरुक के लिए न्यूनतम दूरी 2 का परिणाम देगा), और मेरी समस्या का समाधान एक होगा कई पड़ोसियों के साथ। – MindaugasK

+0

@MindaugasK मेरी गलती क्षमा करें, आप रूट के लिए रकम की दूरी को कम करना चाहते हैं और सभी नोड्स के बीच नहीं ... – maraca

उत्तर

2

मैं इस समाधान के साथ आया था। इस पेड़ में प्रत्येक subtree के लिए, एक subtree में नोड्स की संख्या की गणना (पत्तियां एकल नोड-पेड़ हैं)।

एक उदाहरण के रूप में इस पेड़

  1 
     /| \ 
     2 3 4 
    /\  \ 
    5 6  7 
     /\ 
     8 9  

के लिए परिणाम होगा

  9 
     /| \ 
     5 1 2 
    /\  \ 
    1 3  1 
     /\ 
     1 1  

2) इस चुना जड़ के लिए दूरी की राशि की गणना। उदाहरण के लिए, यदि आप एक रूट के रूप में शीर्ष 1 चुनते हैं, दूरी का योग 0 + 1 + 1 + 1 + 2 + 2 + 2 + 3 + 3 = 15

3) एक depth-first-search में पेड़ Traverse है तौर तरीका। उदाहरण के लिए, वर्टेक्स 1 से शुरू होने पर, हम वर्टेक्स 4 पर जाते हैं। हम देखते हैं कि 7 नोड्स (1,2,3,5,6,8,9) के लिए, हम 1 से आगे बढ़ रहे हैं (7 = 9-2 जोड़ें स्कोर), अन्य 2 (4,7) के लिए, हम 1 के करीब आ रहे हैं (2 घटाएं)। यह 15+ (9-2) -2 = 20.

के बराबर दूरी की दूरी देता है मान लीजिए कि हम 4 से 7 तक आगे बढ़ते हैं। अब हमें 20+ (9 -1) -1 = 27 के बराबर दूरी मिलती है (8 शिखर से आगे बढ़ना, और 1 चरम के करीब होना)।

एक और उदाहरण के रूप में यदि हम 1 से 2 तक ट्रैवर्स करते हैं, तो हमें 15+ (9-5) -5 = 14 के बराबर दूरी मिलती है। 14. वर्टेक्स 2 वास्तव में इस उदाहरण का समाधान है।

यह मेरा एल्गोरिदम होगा।

0

प्रत्येक बढ़त ई = {a, b} निम्नलिखित गुण है:

  • a_count = (सहित एक)
  • b_count = नोड्स की संख्या पक्ष ख के लिए (ख सहित एक तरफ करने के लिए नोड्स की संख्या)
  • a_sum = अपने सबट्री नोड्स के लिए

a_count को ख से सबट्री नोड्स के लिए एक

  • b_sum = दूरी की राशि से दूरी का योग नोड ई = {a, b} निम्नलिखित के रूप में मूल्यांकन किया जा सकता: * सहित नहीं ई एक के सभी किनारे, मिलता है, योग उनके a_count * राशि में 1 जोड़

    नोड ई के लिए a_sum = {a, b} निम्नलिखित के रूप में मूल्यांकन किया जा सकता: *, * जोड़ने a_count सहित नहीं ई एक के सभी किनारे, मिल योग उनके a_sum (यह एक के लिए प्रत्येक प्रगणित बढ़त के +1 और +1 भी शामिल है)

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

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

    एक नोड के लिए एक अंतिम उपाय नोड से जुड़े सभी किनारों के सभी B_count + B_sum का योग है। नोड्स पर इस मूल्यांकन का एक रन करें और न्यूनतम मूल्य के साथ नोड का चयन करें।

    1) एक रूट आर के रूप में एक मनमाना नोड चुनें, एक पेड़ के रूप में:

  • +0

    a_count और a_sum स्पष्ट हैं, सहमत हैं कि आप ओ (एन) में ऐसा कर सकते हैं एकल किनारे के लिए समय, लेकिन आप सभी किनारों के लिए ओ (एन) में यह कैसे करते हैं? – MindaugasK

    संबंधित मुद्दे