संघर्ष-मुक्त सेट निर्धारित करें?

Question

मान लें कि आपके पास सेट का एक समूह है, जबकि प्रत्येक सेट में कुछ सबसेट हैं।

SET1 = {(केला, अनानास, नारंगी), (सेब, गोभी, खीरा), (प्याज, लहसुन)}

SET2 = {(केला, ककड़ी, लहसुन), (एवोकैडो, टमाटर)}

...

SetN = {...}

लक्ष्य अब, प्रत्येक सेट से एक उपसमूह चुनने के लिए है, जबकि प्रत्येक सबसेट किसी अन्य चयनित सबसेट के साथ संघर्ष मुक्त होना चाहिए। इस खिलौने के आकार के उदाहरण के लिए, एक संभावित समाधान (केला, अनानस, नारंगी) (सेट 1 से) और (एवोकैडो, टमाटर) (सेट 2 से) का चयन करना होगा।

एक संघर्ष होगा, यदि कोई सेट 1 और सेट 2 का पहला सबसेट चुनता है क्योंकि केले दोनों सबसेट्स में निहित होगा (जो संभव नहीं है क्योंकि यह केवल एक बार मौजूद है)।

हालांकि कई एल्गोरिदम हैं, मैं एक उपयुक्त एल्गोरिदम चुनने में असमर्थ था। मैं किसी भी तरह से अटक गया हूं और निम्नलिखित प्रश्नों को लक्षित करने वाले उत्तरों की सराहना करता हूं:

1) उपयुक्त एल्गोरिदम कैसे ढूंढें और इस समस्या का प्रतिनिधित्व इस तरह से करें कि इसे एल्गोरिदम द्वारा संसाधित किया जा सके?

2) इस खिलौना के आकार के उदाहरण के लिए एक संभावित समाधान कैसा दिख सकता है (कोई भी भाषा ठीक है, मैं सिर्फ विचार प्राप्त करना चाहता हूं)।

संपादित 1: मैं नकली एनीलिंग के बारे में भी सोच रहा था, (एक संभावित समाधान लौटाएं)। यह कम करने के लिए ब्याज का हो सकता है, उदाहरण के लिए, सेट का चयन करने की समग्र लागत। हालांकि, मैं यह समझ नहीं पाया कि उचित समस्या का वर्णन कैसे किया जाए जो 'संघर्ष' को ध्यान में रखे।

Answer 1

यह समस्या generalized exact cover problem के रूप में तैयार की जा सकती है।

सेट (SET1, SET2, आदि) के प्रत्येक सेट के लिए एक नया परमाणु बनाएं और इतने की तरह एक उदाहरण में अपने इनपुट बारी: Set* परमाणुओं प्राथमिक (ठीक एक बार कवर) और बनाने

{Set1, banana, pineapple, orange} 
{Set1, apple, kale, cucumber} 
{Set1, onion, garlic} 
{Set2, banana, cucumber, garlic} 
{Set2, avocado, tomato} 
... 

अन्य परमाणु माध्यमिक (सबसे अधिक बार कवर)। फिर आप इसे Knuth के एल्गोरिदम एक्स के सामान्यीकरण के साथ हल कर सकते हैं।

Answer 2

सेट की सूची को देखते हुए, मेरे पास एकाधिक प्रवेश द्वारों के साथ एक भूलभुलैया की छवि थी। यह कार्य शीर्ष से नीचे के पथों का पता लगाने जैसा है जो सबसेट-चौराहे से मुक्त हैं। हास्केल में उदाहरण सभी प्रवेश द्वार चुनता है, और सफल होने वाले लोगों को लौटाने, प्रत्येक पथ की कोशिश करता है।

कैसे कोड काम करता है (एल्गोरिथ्म) की मेरी समझ:

पहले सेट में प्रत्येक सबसेट के लिए, अगले सेट में प्रत्येक सबसेट लेने जहां संचित परिणाम में सबसेट से प्रत्येक के साथ कि सबसेट के चौराहे है शून्य। यदि मानदंडों से मेल खाने वाले कोई सबसेट नहीं हैं, तो लूप के उस तनाव को तोड़ दें। यदि से चुनने के लिए कोई सेट नहीं छोड़ा गया है, तो उस परिणाम को वापस कर दें। सभी चुने हुए सबसेट (और संबंधित संचय-परिणाम) के लिए फ़ंक्शन को दोबारा कॉल करें।

import Data.List (intersect) 
import Control.Monad (guard) 

sets = [[["banana", "pineapple", "orange"], ["apple", "kale", "cucumber"], ["onion", "garlic"]] 
     ,[["banana", "cucumber", "garlic"], ["avocado", "tomato"]]] 

solve sets = solve' sets [] where 
    solve' []   result = [result] 
    solve' (set:rest) result = do 
    subset <- set 
    guard (all null (map (intersect subset) result)) 
    solve' rest (result ++ [subset]) 

उत्पादन:

*Main> solve sets 
[[["banana","pineapple","orange"],["avocado","tomato"]] 
,[["apple","kale","cucumber"],["avocado","tomato"]] 
,[["onion","garlic"],["avocado","tomato"]]]