एक स्वयं का चयन टीम

Question

100 सदस्यों से युक्त एक टीम को 1000 आवेदकों के पूल से इकट्ठा किया जाना है। प्रत्येक आवेदक को 99 अन्य आवेदकों को चुनना पड़ता है जो वह टीम के साथी के रूप में करना चाहते हैं।

प्रत्येक संभावित टीम को स्कोर मिलता है जो यह मापता है कि यह अपने सदस्यों की टीम साथी प्राथमिकताओं को कितनी अच्छी तरह संतुष्ट करता है। यदि लिसा एक टीम में है और लिसा की इच्छा सूची में 11 लोगों की टीम भी टीम में है, तो टीम को लिसा के लिए 11 अंक मिलते हैं। सभी सदस्यों के लिए अंक जोड़े गए हैं। सैद्धांतिक अधिकतम किसी भी संभावित टीम को 99 * 100 मिल सकता है। न्यूनतम 0.

अब हम उच्चतम स्कोर वाले टीम को ढूंढना चाहते हैं। प्रत्येक संभावित संयोजन (≈ 10^140) के लिए स्कोर की गणना करके इस समस्या को बलपूर्वक बल देने का प्रयास करना एक विकल्प नहीं है।

क्या कोई चालाक एल्गोरिदम है जो सर्वोत्तम उत्तर के लिए एक शॉर्टकट लेगा या किसी को एक एल्गोरिदम के लिए व्यवस्थित करना होगा जो एक अच्छा जवाब पाता है?

Answer 1

आप hill climbing एल्गोरिदम का प्रयास कर सकते हैं। एक ऐसे सदस्य से शुरू करें जो "लोकप्रिय" है (अक्सर अन्य सदस्यों द्वारा चुना जाता है), और लगातार नए सदस्यों को जोड़ता है जो टीम स्कोर को सबसे ज्यादा बढ़ाते हैं। दुर्भाग्य से यह सबसे अच्छा समाधान खोजने की गारंटी नहीं है, लेकिन शायद यह अच्छा लगेगा। अपने समाधान को बेहतर बनाने के लिए आप simulated annealing आज़मा सकते हैं।

Answer 2

मुझे लगता है कि अगर आप इसे कुशलता से हल कर सकते हैं तो आप http://en.wikipedia.org/wiki/Clique_problem को कुशलतापूर्वक हल कर सकते हैं - जहां दो नोड्स के बीच एक लिंक है जो नोड्स की सूची में प्रत्येक नोड डालता है जिसे दूसरे काम करना चाहता है। लेख को देखते हुए, मुझे लगता है कि आपको एक गारंटीकृत अच्छी सन्निकटन भी मिलना मुश्किल लगेगा, जब तक कि आपकी समस्या में कुछ विशेष संरचना न हो।