चयनित चोटी के न्यूनतम स्पैनिंग पेड़ को खोजने के लिए एल्गोरिदम

Question

कोई प्राइम के एल्गोरिदम या क्रस्कल के एल्गोरिदम का उपयोग कर सकते हैं ताकि न्यूनतम स्पैनिंग पेड़/शिखर/नोड्स और किनारों/लिंक के संग्रह के ग्राफ को प्राप्त किया जा सके। हालांकि मैं क्या चाहता हूं, एक एल्गोरिदम है जो इस संग्रह के न्यूनतम फैलाव ग्राफ को पाता है, लेकिन परिणामी ग्राफ को सभी नोड्स के बजाय केवल मनमाने ढंग से चुने गए नोड्स को शामिल करने की आवश्यकता होती है। यह ठीक है अगर परिणामी ग्राफ में केवल आवश्यकतानुसार अधिक नोड्स शामिल हैं।

क्या ऐसा कोई एल्गोरिदम मौजूद है? शायद केवल आवश्यक नोड्स को शामिल करने के लिए ग्राफ़ को संशोधित करने के बाद प्राइम (या क्रस्कल) एल्गोरिदम का उपयोग कर सकता है? लेकिन, मुझे यकीन नहीं है कि इसके कनेक्टिविटी को बनाए रखते हुए ऐसा करने के लिए ग्राफ़ को कैसे संशोधित किया जाए।

उदाहरण के लिए, कहते हैं कि हम एक हीरे के आकार प्रारंभिक ग्राफ (कोष्ठक में लिंक की लागत के साथ) है: अब

A 
(2)/ \(1) 
    B C 
(2)\ /(5) 
    D 

, हम मनमाने ढंग से तय करते हैं कि केवल एक नोड और डी की जरूरत है। अगर हम ए से शुरू करते हैं, तो हम अभी भी बाएं पथ को लेना चाहते हैं, क्योंकि ((2 + 2) < (1 + 5))।

A 
(2)/ \(1) (2) 
    B C ------E 
(2)\ /(5) 
    D 

अगर हम तय करते हैं कि केवल ए, डी नोड्स, और ई की जरूरत है, हम महसूस करते हैं कि कम से कम लागत के साथ पथ जरूरी न्यूनतम के साथ एक नहीं है:

हम ग्राफ थोड़ा सा संशोधन कहो लिंक। ए - बी - डी और ए - सी - ई लागत 7, लेकिन ए - सी - डी और सी - ई लागत 8.

Answer 1

जो आप खोजना चाहते हैं वह एक अलग Steiner tree है। जब ग्राफ में सभी शिखर अनिवार्य नहीं होते हैं लेकिन पेड़ को वैकल्पिक शिखर पर विभाजित करने की अनुमति दी जाती है, तो समस्या एनपी-हार्ड होती है।

विकिपीडिया इस समस्या के ऊपर (ऊपर लिंक) कहता है: ऐसा माना जाता है कि मनमाने ढंग से अच्छा अनुमान अनुपात आमतौर पर बहुपद समय में हासिल नहीं किया जा सकता है। एक बहुपद-समय एल्गोरिदम है जो कम से कम स्टीनर पेड़ का एक कारक 1.3 9 अनुमान लगाता है।