जब मैं केवल इनपुट डेटा पथ निर्णय (यादृच्छिक क्रम में) पत्ती नोड्स के लिए एक संभावित टॉप डाउन ट्री संरचना बनाने के लिए एक एल्गोरिदम की तलाश में हूं।

पथ निर्णयों को [नोडआईडी]+ के साथ नोट किया जाता है यदि लीफ नोड उस नोड से होकर गुजरा है और [नोडआईडी] - यदि लीफ नोड उस नोड से नहीं गुजरा है। उदाहरण इनपुट:

enter image description here

उपरोक्त उदाहरण इनपुट से एक संभावित वृक्ष संरचना होगी:

enter image description here

आउटपुट नोड्स और नोड संबंधित माता-पिता की एक सूची होनी चाहिए, जैसे:

enter image description here

जैसा कि आप देख सकते हैं कि प्रत्येक लीफ नोड के लिए संभावित स्थिति एक तक सीमित नहीं है, क्योंकि इनपुट डेटा पूर्ण पथ नहीं है। उदाहरण में लीफ1 नोड डी या नोड I का बच्चा हो सकता है।

आपके द्वारा पथ डेटा प्राप्त करने वाले कितने भी पत्ते हो सकते हैं, लेकिन प्रति पत्ती पथ डेटा की केवल एक ही पंक्ति हो सकती है। ऐसे पत्ते हो सकते हैं जिनसे आपको कोई डेटा नहीं मिलता है और आपको पता नहीं है कि पेड़ में कुल कितने पत्ते हैं। पथ डेटा में उल्लिखित सभी नोड्स आउटपुट तालिका में मौजूद होने चाहिए और केवल परिकलित रूट में कोई पैरेंट असाइन नहीं होना चाहिए।

मुझे लगता है कि किसी को किसी तरह प्रत्येक लीफ पथ से तथ्यों को जोड़ना चाहिए, जैसे लीफ 1 से आप जानते हैं: ए और ई समानांतर रेखाओं में नहीं होना चाहिए, और लीफ 2 से आप जानते हैं कि ए और मैं समानांतर रेखाओं में नहीं होना चाहिए, और इसी तरह .. .

पसंदीदा जावास्क्रिप्ट लेकिन अन्य भाषा या छद्म कोड का भी स्वागत है!

1
Plarsen 25 जून 2019, 13:08

1 उत्तर

सबसे बढ़िया उत्तर

चूंकि किसी ने उत्तर नहीं दिया, मैं कुछ आंशिक विचार दूंगा।

आप इसके साथ शुरू करते हैं:

1: [A+, E+, H-]
2: [B-, A+, I+, D-]
3: [K+, G+, E+, C-]
4: [H+, A-, G-]

सबसे पहले, उन नोड्स की खोज करें जो केवल + के साथ दिखाई देते हैं। उन जड़ों को बनाओ। इसे स्कैन करके, हम ऐसा नोड्स E, I, और K के लिए कर सकते हैं। तो हमारा जवाब शुरू होता है:

E
E I
I K

और हमारे पथ डेटा को सरल बनाया गया है:

1: [A+, H-]
2: [B-, A+, D-]
3: [G+, C-]
4: [H+, A-, G-]

और अब हमारे पास एक विभाजन ऑपरेशन है। इसके लिए हम एक ग्राफ बनाते हैं जहां 2 नोड्स जुड़े हुए हैं यदि वे एक साथ + के साथ दिखाई देते हैं। फिर हम जुड़े हुए घटकों द्वारा नोड्स को अलग करते हैं, और पत्तियों को विभाजन में अलग करते हैं जहां एक + होता है (बिना विभाजन के किसी भी पत्ते को पेड़ में वहीं एक पत्ता बनाया जा सकता है और फिर गिरा दिया जा सकता है)। किसी को हटाना - जिसका ध्यान इस अलगाव से होता है। हमारे मामले में यह एक पूरी तरह से डिस्कनेक्ट किया गया ग्राफ है जो प्रत्येक नोड को अपने विभाजन में रखता है और पथ डेटा को 3 समूहों में विभाजित करता है (ध्यान दें, हम सभी नियमों को खो देते हैं जिन्हें विभाजन द्वारा समझाया गया है):

1: [A+]
2: [A+]

3: [G+]

4: [H+]

और अब हम प्रत्येक समस्या का समाधान करते हैं, जिसके अंतिम समाधान पर आते हैं:

E
E I
I K
K A
K B
K C
K D
K G
K H

मेरा मानना ​​है कि यह दृष्टिकोण केवल उस स्थिति में प्रगति करने में विफल होगा जहां कोई पेड़ संभव नहीं है। अगर कोई पेड़ मिल जाए, तो वह मिल जाएगा।

1
btilly 26 जून 2019, 17:29