एक असंगत संबंध से कुल या आंशिक आदेश का उत्पादन करना
कल्पना कीजिए कि मैं तत्वों के एक सेट से कुल ऑर्डर बनाना चाहता हूं, $E$, लेकिन तुलनात्मक फ़ंक्शन गैर-नियतात्मक हैं परिणाम उत्पन्न करता है। मैं तुलनात्मक फ़ंक्शन के दोहराया आवेदन के माध्यम से तत्व जोड़े (ई, ई) की एक सूची का उत्पादन करता हूं, जैसे कि सेट में प्रत्येक तत्व को कम से कम एक बार दर्शाया गया है।
कुल आदेश देने के लिए मैं इस इनपुट का उपयोग कैसे कर सकता हूं? एल्गोरिदम की वह कौन सी श्रेणी है जिसे यहाँ लागू किया जा सकता है?
अधिक स्पष्टता के लिए, मैं एक ठोस उदाहरण प्रदान करता हूँ।
सबसे अच्छा पिज्जा टॉपिंग क्या हैं?
मेरे तत्वों का सेट $E$ कुछ लोकप्रिय पिज्जा टॉपिंग शामिल हैं: पेपरोनी, पनीर, मशरूम, अनानास, बेलपाइपर, जैतून।
तब मेरे प्रत्येक दोस्त के लिए, मैं टॉपिंग के बेतरतीब ढंग से आकार के सबसेट उठाता हूं और अपने दोस्त को सबसे अच्छे से बुरे क्रम में रखने के लिए कहता हूं। मेरे दोस्त उत्तर देते हैं, और मेरे एल्गोरिथ्म के लिए इनपुट बनाते हैं:
- पनीर, पेपरोनी, जैतून
- पनीर, अनानास, मशरूम, जैतून
- बेलपाइपर, मशरूम, जैतून
- पेपरोनी, पनीर, जैतून
- पनीर, बेलपत्र
यहाँ एक फजी आदेश प्रतीत होता है (सभी सहमत हैं कि जैतून सबसे खराब हैं) लेकिन मेरे दोस्त इस बारे में आम सहमति पर नहीं पहुंचे हैं कि कौन बेहतर पिज्जा टॉपिंग है: पनीर या पेपरोनी। यह देखते हुए कि इनपुट्स में आइटम कहां होते हैं, और वे कितनी बार होते हैं, मैं शायद इस तरह से एक ऑर्डर का उत्पादन करूंगा।
- पनीर> पेपरोनी> बेलपेपर> अनानास> मशरूम> जैतून
मुझे यकीन नहीं है कि इसे औपचारिक रूप देने के बारे में कैसे जाना जाए और यह बहुत बड़े आदानों के लिए काम कर रहा है।
मुझे लगता है कि समाधान में संभवतः ग्राफ़ और भारित किनारों शामिल हैं, लेकिन मुझे यह समझने के लिए ग्राफ़ एल्गोरिदम के साथ पर्याप्त परिचितता की कमी है कि क्या यह अध्ययन का एक नामित क्षेत्र है। मैं पहले से ही "टोपोलॉजिकल सॉर्टिंग" पर आया था, लेकिन यह केवल निर्देशित चक्रीय रेखांकन के लिए काम करता है , और मैं विशेष रूप से उन इनपुट्स में दिलचस्पी रखता हूं जो डीएजी का उत्पादन नहीं कर सकते।
मैंने यह भी देखा कि यह समस्या निर्वाचित प्रतिनिधियों के लिए मतदान के समान है। क्या वास्तव में, समस्या का एक ही वर्ग है?
जवाब
अधिक संदर्भ और अधिक मॉडलिंग के बिना यह कहना मुश्किल है। यह तुलनात्मक कार्य के परिणामों से संबंधित (छिपे हुए) वांछित कुल आदेश से संबंधित कुछ मान्यताओं की आवश्यकता होगी।
यह संभव है कि आप ब्रैडली-टेरी-लूस मॉडल चाहते हों । यदि हां, तो कई मानक एल्गोरिदम हैं। यह सभी देखेंhttps://cs.stackexchange.com/a/85204/755।
यह संभव है कि आप कुछ रैंकिंग प्रणाली चाहते हों, जैसे एलो, आदि।
यह संभव है कि आप एक रैंक की गई वोटिंग प्रणाली चाहते हों , जैसे कि IRV, कोंडोरसेट विधि, बोरदा गिनती या कई अन्य। उन सभी में विभिन्न दोष और व्यापार हैं। इस बात का एक प्रमाण है कि किसी भी प्रणाली में वे सभी गुण नहीं होंगे जो हम चाहते हैं - देखें, उदाहरण के लिए, एरो की प्रमेय और गैर-ट्रांज़िटिविटी की समस्या (भले ही आपके मित्र की प्रत्येक व्यक्तिगत प्राथमिकताएं सकर्मक हों, यानी कुल आदेश, तब इस बात की कोई गारंटी नहीं है कि वैश्विक कुल ऑर्डर मौजूद है जो उन सभी के अनुरूप है)।