समूह टुपल्स जैसे कि समूह में प्रत्येक आइटम अन्य सदस्यों के साथ कोई आम तत्व साझा नहीं करता

Question

तो मैंने इस तरह की वास्तविक दुनिया की समस्या में भाग लिया है: हमारे पास जोड़े की एक सूची है जिसे हमें समूहों में क्रमबद्ध करने की आवश्यकता है। हम समूहों की संख्या को कम करना चाहते हैं, जो कि हमारे पास कुल है, इस समूह के किसी भी सदस्य समूह के किसी अन्य सदस्य के साथ तत्व साझा नहीं कर सकता है।

यहां एक उदाहरण है। टुपल्स की हमारी सूची (ए, बी), (बी, सी), (सी, ए), (डी, ई), (एफ, जी) है। हम [समूह ए, बी), (डी, ई), (एफ, जी)], [(बी, सी)], [(सी, ए)] करके तीन समूहों का निर्माण कर सकते हैं।

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

Answer 1

बताई गई समस्या को edge-coloring problem के रूप में माना जा सकता है: आपके पास एक ग्राफ है जहां प्रत्येक ट्यूपल प्रविष्टि नोड है और किनारों को किनारों द्वारा दिया जाता है। समूहों में tuples क्लस्टरिंग तो किनारों के समूहों को खोजने के अनुरूप है जो एंडपॉइंट्स (मिलान) साझा नहीं करते हैं, जिसे एक किनारे रंग में एक ही रंग असाइन किया जा सकता है। दूसरे शब्दों में, प्रत्येक किनारे रंग आपको क्लस्टरिंग देता है और प्रत्येक क्लस्टरिंग आपको किनारे रंग देता है। दुर्भाग्यवश, यह एनपी -हार्ड सर्वश्रेष्ठ किनारे रंग खोजने के लिए है, इसलिए आपकी समस्या सामान्य में एनपी -हार्ड है। इस समस्या के लिए सन्निकटन एल्गोरिदम हैं जो स्थिर-कारक अनुमानों का उत्पादन करते हैं, लेकिन पी = एनपी कोई सटीक एल्गोरिदम नहीं है।

यदि आप प्रति समस्या को किसी भी प्रकार के तत्वों को अनुमति देने के लिए इस समस्या को सामान्यीकृत करते हैं, तो यह समस्या बहुत कठिन हो जाती है। इस समस्या का सामान्य संस्करण वास्तव में एनपी -हार्ड, और ग्राफ रंग से कमी से अनुमान लगाने के लिए वास्तव में कठिन है। मैं एक विशिष्ट मामले में कमी का एक उदाहरण दिखाऊंगा, लेकिन यह काफी अच्छी तरह से सामान्यीकृत करता है।

इस तरह का ग्राफ को देखते हुए:

A -- B -- C 
| | | 
D -- E -- F 

हम tuples का एक सेट, प्रत्येक नोड, जहां टपल में प्रत्येक प्रविष्टि के उस नोड के लिए आसन्न किनारों का सेट है के लिए वह बना देंगे। उदाहरण के लिए, ऊपर ग्राफ में, हम इन tuples फार्म चाहते हैं:

(AB, AD) 
(AB, BC, BE) 
(CB, CF) 
(AD, DE) 
(BE, DE, EF) 
(CF, EF) 

अब, कल्पना है कि इन tuples के दो ओवरलैप नहीं। इसका मतलब है कि उन tuples से संबंधित दो नोड्स निकट नहीं होना चाहिए, क्योंकि यदि वे थे, तो उनके बीच का किनारा tuples में एक आम तत्व होगा और इसलिए उन्हें क्लस्टर नहीं किया जा सका। दूसरी तरफ, यदि दो नोड आसन्न नहीं हैं, तो उनके टुपल्स को एक ही क्लस्टर में एक साथ समूहीकृत किया जा सकता है, क्योंकि एक टुपल में कोई किनारा दूसरे में मौजूद नहीं होगा।

इस सेटअप को देखते हुए, मूल ग्राफ का कोई भी रंग tuples को क्लस्टर करने का एक तरीका देता है (एक ही रंग को उसी रंग में दिए गए नोड्स के लिए सभी tuples डाल दें; उनमें से कोई भी आसन्न नहीं है, इसलिए वे संघर्ष नहीं करते हैं) और tuples क्लस्टरिंग का कोई भी तरीका एक रंग देता है (एक क्लस्टर में एक ही रंग में प्रत्येक tuple के अनुरूप सभी नोड्स रंग)। इसलिए, क्लस्टर की न्यूनतम संख्या को ढूंढना मूल ग्राफ की रंगीन संख्या को ढूंढने के अनुरूप है, जो एनपी -हार्ड है और किसी भी सन्निकटन एल्गोरिदम को स्वीकार करने के लिए ज्ञात नहीं है जो वास्तविक मूल्य के करीब कहीं भी मिलता है।