संगत तत्वों के इष्टतम समूह को खोजने के लिए एल्गोरिदम

Question

मेरे पास इकाइयों का एक समूह है और मुझे specie नामक समूहों में इस संस्था को समूहित करने की आवश्यकता है। परिभाषित सभी प्रजातियों का सेट Universe पर कॉल करता है और एक इकाई एक और केवल एक specie से संबंधित होना चाहिए। इसके लिए मेरे पास f नामक एक बुलियन इंट्रानेटिव फ़ंक्शन है जो पैरामीटर द्वारा पारित दो इकाइयों को संगत करता है। एक specie को एक दूसरे के साथ इकाइयों के एक समूह द्वारा परिभाषित किया गया है और universe उन प्रजातियों के समूह द्वारा परिभाषित किया गया है जो पूरी तरह से एक-दूसरे के साथ संगत नहीं हैं, यह मानते हुए कि दो प्रजातियों की संगतता इसकी सभी इकाइयों की संगतता द्वारा परिभाषित की गई है।

मैं उस ब्रह्मांड को कैसे निर्धारित कर सकता हूं जिसमें इकाइयों के दिए गए सेट के लिए संभवतः छोटी संख्या में प्रजातियां संभव हों?

मैंने निम्नानुसार प्रयास किया और मेरा फ़ंक्शन एक वैध ब्रह्मांड देता है, लेकिन सबसे छोटी प्रजातियों के साथ संभव नहीं है।

public class Specie { 
    private List<Entity> individuals; 

    public Specie() { 
     this.individuals = new ArrayList<>(); 
    } 

    public boolean matches(Entity e) { 
     for (Entity s : this.individuals) { 
      if (!f(s, e)) { 
       return false; 
      } 
     } 
     return true; 
    } 

    public void add(Entity i) { 
     this.individuals.add(i); 
    } 
} 

private static int numberOfSpeciesRecursive(List<Entity> entities, List<Specie> universe) { 
    if (entities.size() == 0) { 
     return 0; 
    } else { 
     List<Entity> remains = new ArrayList<>(); 
     Specie specie = new Specie(); 
     for (Entity e : entities) { 
      if (specie.matches(e)) { 
       specie.add(e); 
      } else { 
       remains.add(e); 
      } 
     } 
     universe.add(specie); 
     return 1 + numberOfSpeciesRecursive(remains, universe); 
    } 
} 

Answer 1

इकाइयों को ग्राफ के शीर्षकों के रूप में देखें, और इकाइयों के अनुकूल होने पर शिखर के बीच किनारों को जोड़ें।

इस परिणामी ग्राफ में, प्रजातियों की आपकी परिभाषा clique की परिभाषा से मेल खाती है।

इसलिए प्रजातियों की न्यूनतम संख्या को खोजने की समस्या ग्राफ की छोटी संख्या के साथ ग्राफ को कवर करने के बराबर है। इस समस्या को minimum clique cover के रूप में जाना जाता है और यह एनपी-पूर्ण है।