मैं इस समस्या से आया - एक अप्रत्यक्ष ग्राफ में प्रत्येक नोड और किनारे का वजन होता है। सभी वजन गैर-नकारात्मक हैं। एक मान एस को देखते हुए, न्यूनतम योग के वजन के साथ जुड़े सबग्राफ को ढूंढें, जैसे कि नोड वजन का योग कम से कम एसन्यूनतम किनारे के वजन और नोड वजन के साथ सबग्राफ> = वैल
सबसे स्पष्ट समाधान सभी संभव उपग्राफों पर विचार करने वाला एक बलपूर्वक बल दृष्टिकोण है। लेकिन समय जटिलता घातीय है। क्या इसके लिए कोई बेहतर एल्गोरिदम है? मेरा अंतर्ज्ञान यह है कि हम नोड वजन को किनारों के वजन में परिवर्तित कर सकते हैं और फिर स्पैनिंग पेड़ एल्गोरिदम लागू कर सकते हैं। लेकिन मैं इसे स्पष्ट रूप से हल नहीं कर सका। इस समस्या को हल कैसे करें?
संपादित करें: ऐसा लगता है कि मैं सबग्राफ के विवरण के बारे में पर्याप्त स्पष्ट नहीं था। चयनित सबग्राफ एक एकल, कनेक्टेड घटक होना चाहिए। मुझे आशा है कि यह अभी स्पष्ट है।
वजन कमजोर हैं (उदा। सभी गैर-नकारात्मक)? यदि सभी वजन गैर-ऋणात्मक हैं, तो समस्या छोटी हो जाती है - शायद आप केवल उप-अनुच्छेदों को किनारों के एक सेट द्वारा प्रेरित किए गए उप-अनुच्छेदों को बाधित करना चाहते हैं? –
सभी वजन गैर-नकारात्मक हैं और सभी किनारों पर विचार किया जा सकता है। हम समस्या को कैसे हल कर सकते हैं? – Sashank
उन बाधाओं के साथ समाधान छोटा है: सभी नोड्स और किनारों में से कोई भी चुनें। एज वजन 0, नोड वजन निश्चित रूप से एस से ऊपर है जब तक यह असंभव नहीं है। –