8
मैं दिए गए निर्देशित असीमित ग्राफ पर एक स्थलीय सॉर्टिंग करने का एक तरीका ढूंढ रहा हूं, जिसमें चक्र होते हैं। नतीजे में न केवल शिखर के क्रम को शामिल करना चाहिए, बल्कि किनारों का सेट भी होना चाहिए, जो दिए गए आदेश द्वारा उल्लंघन किए जाते हैं। किनारों का यह सेट न्यूनतम होगा।न्यूनतम संख्या में उल्लंघन किए गए किनारों के साथ चक्रीय ग्राफ का टॉपोलॉजिकल प्रकार
जैसा कि मेरा इनपुट ग्राफ संभावित रूप से बड़ा है, मैं घातीय समय एल्गोरिदम का उपयोग नहीं कर सकता। यदि बहुपद समय में इष्टतम समाधान की गणना करना असंभव है, तो दी गई समस्या के लिए क्या ह्युरिस्टिक उचित होगा?
क्या यह [प्रतिक्रिया आर्क सेट] नहीं है (http://en.wikipedia.org/wiki/Feedback_arc_set)? आप अवशिष्ट डीएजी को टोपोलॉजिकल क्रमबद्ध करके ऑर्डर प्राप्त कर सकते हैं। –
क्या आप भी एक न्यूनतम समाधान चाहते हैं (प्रत्येक और हटाई गई चाप डीएजी में एक चक्र पूरा करेगी) या न्यूनतम समाधान (जितना संभव हो उतना आर्क हटा दिया जाएगा)? –
@ डेविडइसेनस्टैट वास्तव में मुझे बहुत ज्यादा परवाह नहीं है अगर यह एक चाप कम या ज्यादा है, तो मुझे बस उन्हें अलग से संभालना होगा। अगर कुछ एल्गोरिदम रनटाइम में दो बार लेता है और केवल कुछ आर्कों के साथ एक समाधान पाता है, तो यह आर्थिक नहीं होगा। समस्या फीडबैक आर्क सेट प्रतीत होती है, लेकिन इस मामले में एनपी मुश्किल है, इसलिए हमें एक अनुमान की आवश्यकता होगी। – orsg