एक दोस्त ने आज मुझे एक असाइनमेंट समस्या के बारे में एक प्रश्न पूछा। मुझे एक काफी सरल समाधान मिला, लेकिन मुझे लगता है कि इसे सरल और तेज़ बनाया जा सकता है। आपकी मदद की सराहना की जाएगी।प्राथमिकताओं का सम्मान करते समय लोगों को भवनों में निर्दिष्ट करना?
समस्या: मान लिया जाये कि मैं एन लोग है, मैं, प्रत्येक भवन कश्मीर लोग घर कर सकते हैं उन्हें एम भवनों में सौंपने होंगे। सभी लोग एक-दूसरे के साथ रहने के इच्छुक नहीं हैं, इसलिए मेरे पास एन * एन कोशिकाओं का एक मैट्रिक्स है और एक ऐसा व्यक्ति है जो एक दूसरे के साथ रहने के इच्छुक हैं। यदि किसी कक्ष में 1 होता है तो इसका मतलब है कि मैं और जे एक साथ रह सकते हैं। स्पष्ट रूप से मैट्रिक्स मुख्य विकर्ण के चारों ओर सममित है।
int[] Match(int[] people, int[][] pairs, int numBuildings, int buildingsSize)
{
int[] freePeople = findFreePeople(people);
if(freePeople) = 0
{
return people;
}
foreach(int person in freePeople)
{
for(int buildingIndex=0 to numBuildings)
{
if(CheckIfPersonFitsInBuilding(...))
{
int[] tempPeople = people.Copy();
tempPeople[person] = buildingIndex;
int[] result = Match(tempPeople,pairs,numBuildings,buildingsSize);
if(result != null)
{
return result;
}
}
}
}
return null;
}
मैं बस हर संभव प्रत्यावर्तन का उपयोग कर व्यवस्था को कवर:
मेरे समाधान के रूप में निम्नानुसार (छद्म कोड) है। मुझे लगता है कि इसे बहुत अनुकूलित किया जा सकता है, और मैं हेरिस्टिक के बारे में बात नहीं कर रहा हूं लेकिन बहुत कम जटिलता वाला समाधान।
- क्या कोई औपचारिक अच्छी तरह से ज्ञात समस्या है जो इस तरह है?
- क्या कोई बेहतर एल्गोरिदम है?
मुझे लगता है कि यह stable marriage problem से संबंधित हो सकता है, हालांकि मुझे यकीन नहीं है।
मुझे नहीं लगता कि स्थिर विवाह समस्या यहां लागू होती है; यह द्विपक्षीय मिलान समस्या से संबंधित है, और यह समस्या मेल नहीं खाती है। – templatetypedef
@templatetypedef क्या आप कृपया मुझे बता सकते हैं कि नाम के साथ क्या गलत था? यह एक सभ्य "समथिंग समस्या" एक पाठ्यपुस्तक का नाम है ... –
शब्द "समस्या" का प्रयोग अक्सर "सी ++ के साथ समस्या" या "HTML के साथ समस्या" जैसे शीर्षकों में किया जाता है जो वास्तव में समस्या का वर्णन नहीं करता है। मैं आपसे सहमत हूं कि नाम पर प्रतिबंध लगाने के लिए थोड़ा अजीब बात है क्योंकि इससे इस तरह के झूठे सकारात्मक कारण बन सकते हैं। – templatetypedef