तत्वों को एक दूसरे के साथ कई रिश्ते होने पर सेट को सॉर्ट करने के लिए कैसे करें

Question

मैं किसी प्रकार का विस्तारित सरणी सॉर्टिंग करने के लिए एक एल्गोरिदम खोज रहा हूं जब तत्वों के बीच संबंध एक दूसरे के विरोधाभास कर सकते हैं।

तो हम एक सेट मैं (आइटम) n आइटम i1 से मिलकर है ...

में वहाँ एक सेट आर (संबंध) मीटर से मिलकर रिश्तों के बीच में परिभाषित किया गया है में आइटम I

संबंध एक-दूसरे से विरोधाभास कर सकते हैं ताकि, एक रिश्ते कहता है कि A>B और दूसरा वें A<B पर।

उदा।

r1:i1<i35 

r2:i100<i4 

... 

rm:i45>i3 

आम तौर पर, आर और मीटर (सेट के आकार) किसी भी धनात्मक पूर्णांक हो सकता है।

कार्य सॉर्ट करने के लिए मैं तो आइटम इस तरह से कि अधिमानतः नीचे आ (संबंधों के आधार पर) उच्च लोगों से पहले जाना में जाना ...

मैं एक एल्गोरिथ्म के लिए देख रहा हूँ है जो सेट को सॉर्ट करेगा ताकि यह संभवतः "इष्टतम" ऑर्डर के करीब हो। मुझे लगता है कि इस तरह की समस्याओं को हल करने के लिए एक प्रसिद्ध एल्गोरिदम होना चाहिए।

धन्यवाद!

Answer 1

मुझे लगता है कि किसी विशेष आदेश की गुणवत्ता को मापने का सबसे समझदार तरीका यह है कि वह दिए गए रिश्तों की संख्या है। यदि आप इस उपाय का उपयोग करने का निर्णय लेते हैं, तो समस्या (Minimum) Feedback Arc Set के बराबर है। दुर्भाग्यवश, यह समस्या एनपी-हार्ड है, इसलिए कोई कुशल (बहुपद-समय) एल्गोरिदम मौजूद होने की संभावना नहीं है।

फीडबैक आर्क सेट समस्या में, आपको एक निर्देशित ग्राफ दिया जाता है, और न्यूनतम आकार के किनारों को सेट करने के लिए कहा जाता है, यदि हटा दिया जाता है, तो ग्राफ में सभी चक्र नष्ट हो जाएंगे।

यह देखने के लिए कि यह आपकी समस्या से कैसे मेल खाता है, यह देखते हुए कि हम प्रत्येक आइटम को ग्राफ में वर्टेक्स के रूप में प्रस्तुत कर सकते हैं, और प्रत्येक रिश्ते को दो शीर्षकों के बीच निर्देशित किनारे के रूप में दर्शाया जा सकता है (इंगित करना, छोटा कहना)। यदि कोई ग्राफ है तो केवल एक और संघर्ष है यदि इस ग्राफ में चक्र है - यानी, यदि 2 या अधिक विशिष्ट शीर्षकों v_1, v_2, ..., v_k की ऑर्डर की गई सूची है, तो v_i < v_ (i +1) सभी के लिए मैं < के, और v_k < v_1। कम से कम एक बाधा का उल्लंघन किये बिना इन के शिखर आदेशों को ऑर्डर करना असंभव है। इसके विपरीत, यदि कोई चक्र मौजूद नहीं है - यानी, यदि ग्राफ directed acyclic graph है - तो topological sort जल्दी (रैखिक समय में) एक वैध आदेश ढूंढ सकता है जो किसी भी बाधा का उल्लंघन नहीं करता है। इस प्रकार फीडबैक आर्क सेट का आकार किनारों की सबसे छोटी संख्या है जिसे आपको किसी भी बाधा का उल्लंघन किए बिना आदेश दिया जा सकता है - या समकक्ष, किनारों की सबसे छोटी संख्या में उल्लंघन की जानी चाहिए कोई ऑर्डरिंग।