बाधाओं के साथ मिलान

मस्ती के लिए, मैं एक ऐसा प्रोग्राम तैयार कर रहा हूं जो एक गुप्त सांता उपहार विनिमय के लिए भागीदारों को उत्पन्न करता है। हालांकि, इस सेटअप में, यादृच्छिक रूप से उत्पन्न जोड़े के बजाय, बाधाओं की अनुमति है।

उदाहरण: व्यक्ति ए और व्यक्ति बी एक-दूसरे से नफरत करते हैं, इसलिए न तो ए और बी को दूसरे के लिए उपहार खरीदने के लिए असाइन किया जाना चाहिए।

दूसरा उदाहरण: व्यक्ति सी ने पिछले साल व्यक्ति डी के लिए उपहार खरीदा था। व्यक्ति सी को व्यक्ति डी के लिए उपहार खरीदने के लिए असाइन नहीं किया जाना चाहिए, लेकिन व्यक्ति डी को अभी भी एक उपहार खरीदने की अनुमति दी जानी चाहिए।

आम तौर पर, मैं एक सेट से खुद को एक जैविक कार्य उत्पन्न करना चाहता हूं, लेकिन उस फ़ंक्शन को बाधाओं के प्रति संवेदनशील होना चाहिए। यदि ऐसी कई बाधाएं हैं जैसे समस्या हल नहीं की जा सकती है, तो दिनचर्या को एक त्रुटि या कुछ वापस करना चाहिए।

यह मुझे कुछ प्रकार की ग्राफ समस्या की तरह दिखता है, लेकिन मुझे वास्तव में पता नहीं है कि इसे हल करने के लिए किस दिशा में जाना है। मैं इस समस्या को प्रोग्रामेटिक तरीके से कैसे हल कर सकता हूं? क्या मौजूदा एल्गोरिदम मैं उपयोग/संशोधित कर सकता हूं?

0
@ बुनीप लिखे गए कोड के साथ समस्याओं से संबंधित प्रश्नों से संबंधित प्रश्नों को लिखे गए कोड के साथ समस्याओं से संबंधित प्रश्नों से जुड़ा होना चाहिए। "प्रश्न पूछने के लिए प्रश्न ..." शायद समझ में आएगा, सिवाय इसके कि वह कारण है ... बस गलत (सामान्य रूप से)। आप शायद प्रश्न को कम करने के लिए तर्क दे सकते हैं।
जोड़ा लेखक Dukeling, स्रोत
@ बुनिप: यह एक एल्गोरिदमिक प्रश्न है, एसएससीसीई के पास इस पूरी तरह से अच्छे सवाल से कोई लेना देना नहीं है।
जोड़ा लेखक akappa, स्रोत
@ बुनिप: वह कोड मांग नहीं रही है, वह एक विचार मांग रही है। क्या आपने कभी एल्गोरिदम का एक अमूर्त प्रतिनिधित्व देखा था?
जोड़ा लेखक akappa, स्रोत

2 उत्तर

लगता है जैसे बाधा संतुष्टि समस्या । समस्या के लिए एक ग्राफिकल प्रतिनिधित्व है, जो दिखाता है कि यह कैसे हल किया जाता है। मैंने एआई पर एक कोर्स किया जिसने इसके बारे में बात की। यहां एक व्याख्यान स्लाइड है: व्याख्यान । स्लाइड 15 तस्वीर दिखाता है। स्लाइड्स के माध्यम से पढ़ें, कई एल्गोरिदम हैं जो सीएसपी को हल करते हैं, जिसमें वैरिएबल एलिमिशन (स्लाइड 44) शामिल है।


0
जोड़ा
ऐसी छोटी और मानक समस्या के लिए सीएसपी के सामान्य दृष्टिकोणों का उपयोग करना बहुत अधिक है।
जोड़ा लेखक akappa, स्रोत

अनिवार्य रूप से आपकी समस्या अच्छी तरह से ज्ञात है असाइनमेंट समस्या :

एक द्विपक्षीय ग्राफ पर विचार करें जहां प्रत्येक पक्ष में सभी लोग नोड्स के रूप में होते हैं (हां, प्रत्येक व्यक्ति दो बार दिखाई देगा: एक बार बाईं ओर और एक बार दाईं ओर)। फिर आप बाएं तरफ से दाएं तरफ से व्यक्ति ए से किनारे को जोड़ सकते हैं बी अगर ए को बी को उपहार भेजने की इजाजत है तो आप आवेदन कर सकते हैं, उदाहरण के लिए, हंगेरियन एल्गोरिदम जो अनुमत उपहारों की संख्या को अधिकतम करता है।

बिपार्टाइट ग्राफ

0
जोड़ा
मुझे यकीन नहीं है कि मैं समझता हूं कि "अनुमत उपहारों की संख्या को अधिकतम करने" का क्या मतलब है - क्या आप इसे फिर से लिख सकते हैं? इसके अलावा, क्या मुझे द्विपक्षीय ग्राफ की आवश्यकता है? या क्या मेरे पास एक निर्देशित ग्राफ हो सकता है जहां प्रत्येक व्यक्ति को एक नोड द्वारा दर्शाया जाता है और तीर दर्शाता है कि पहला नोड दूसरे नोड को उपहार दे सकता है। फिर, क्या मैं एक ऐसे पथ की खोज कर सकता हूं जो वैध समाधान खोजने के लिए हर नोड को हिट करता है? क्या यह इस समस्या पर हमला करने का एक वैध तरीका है?
जोड़ा लेखक Michelle, स्रोत
"अनुमत उपहारों की संख्या को अधिकतम करने" का मतलब असाइनमेंट जो जोड़ों की संख्या को अधिकतम करता है। उदाहरण के लिए, क्या 4 व्यक्ति ए, बी, सी, डी और ए सी और डी को उपहार भेज सकते हैं, जबकि बी केवल डी को उपहार भेज सकता है। इसलिए यदि कोई डी को उपहार भेजता है, तो बी किसी के साथ नहीं जुड़ा होगा ।
जोड़ा लेखक Artem Sobolev, स्रोत
@ मिशेल, क्या आपकी दृष्टिकोण काम करेगी जब सभी बाधाओं को संतुष्ट नहीं किया जा सकता है? यह एक होगा। मुझे यकीन नहीं है कि क्या आप सुरक्षित रूप से द्विपक्षीय ग्राफ से छुटकारा पा सकते हैं, यह विशेष एल्गोरिदम पर निर्भर हो सकता है।
जोड़ा लेखक Artem Sobolev, स्रोत
@ मिशेल: व्यवहार्य समाधान होने पर भी वह दृष्टिकोण विफल रहता है। उदाहरण पर विचार करें एक मामला जहां आपके पास ए, बी, सी, डी: ए और बी एक दूसरे को उपहार बना सकते हैं, और सी और डी के लिए भी। इस परिदृश्य में एक समाधान है (ए <-> बी और सी <-> डी), लेकिन इसमें एक यूलेरियन चक्र नहीं है (वास्तव में, ग्राफ में दो डिस्कनेक्ट किए गए घटक हैं)। ऐसा लगता है कि आपको द्विपक्षीय ग्राफ होना चाहिए।
जोड़ा लेखक akappa, स्रोत