एक चक्र के लिए अधिकतम वजन स्वतंत्र सेट समस्या (पथ ग्राफ संशोधन)
समस्या: एक ग्राफ जी = (वी, ई) कोने पर गैर-नकारात्मक भार के साथ। वांछित आउटपुट: एन सीरीज़ v1 के साथ एक चक्र सी में अधिकतम कुल वजन के कोने (गैर-आसन्न) का एक स्वतंत्र सेट। । । vn (प्रत्येक i <n के लिए, vi vi + 1 से जुड़ा है, vn v1 से जुड़ा है और C में ये एकमात्र किनारे हैं)।
यह समस्या इस समस्या का एक संशोधन है: पथ ग्राफ़ के लिए अधिकतम-भार स्वतंत्र सेट समस्या
मुझे पता है कि मूल समस्या के लिए पथ ग्राफ जिसमें कोई चक्र नहीं है, समाधान है
a[i] = max(a[i - 1], a[i - 2] + w[i])
ऐसा इसलिए है क्योंकि IS या तो एक हो सकता है जिसमें vn या एक होता है जो नहीं करता है, और चलने का समय O (n) सबसे खराब स्थिति है क्योंकि प्रत्येक उपप्रोग्राम केवल n का एक भाग ले रहा है और इसे कम कर रहा है क्योंकि यह विभाजित और जीतता है।
चक्र संशोधन के लिए, यह मेरा दृष्टिकोण है:
- IS में v1 है, लेकिन vn नहीं है,
- IS में vn नहीं बल्कि v1 है,
- IS में न तो v1 है और न ही vn है।
मुझे यकीन नहीं है कि यदि समीकरण चक्र संशोधन के लिए पथ ग्राफ (ऊपर दिखाया गया है) के समान हो रहा है और सुनिश्चित नहीं है कि इसे कैसे लिखना है, और मुझे यकीन नहीं है कि यदि चल रहा समय अभी भी वैसा ही होगा कुंआ। कृपया मदद करे।
जवाब
हमें मामलों को ओवरलैप करने की आवश्यकता नहीं है। अगर हम v1 को बाहर करने वाले समाधानों का अधिकतम पता लगाते हैं, और vn को बाहर करने वाले समाधानों का अधिकतम पता लगाते हैं, तो समग्र अधिकतम को इन दो उम्मीदवार समाधानों में से एक से मिलान करना होगा, क्योंकि किसी भी समाधान में v1 और vn दोनों शामिल नहीं हैं। इन उपप्रकारों के लिए, डीपी पथ महान काम करता है।