找到最佳的兼容元素组的算法

我有一组实体，我需要将这些实体分组，称为specie。所有物种的集合定义为调用Universe，并且一个实体必须属于一个且只有一个种类。为此，我有一个名为f的布尔型不灵敏函数，如果通过参数传递的两个实体是兼容的，则返回该函数。 A specie由一组实体相互定义，并且由一组物种定义，这些物种彼此不完全相容，假设两个物种的兼容性由其所有实体的兼容性定义。找到最佳的兼容元素组的算法

如何确定包含给定实体集可能的最小物种数的宇宙？

我尝试如下，我的函数返回一个有效的宇宙，但不是最小的物种数量可能。

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); 
    } 
}

来源

2015-11-04 Lucas Cleto

btw：物种的单数是物种。硬币是一个完全不同的词。 – ciamej

不幸的是，你的解决方案是'O（n^3）'而我的是'O（n^4）'。如果性能对您来说是一个问题，我可能会想到一个更快的计算方法。 – ciamej

你能提供什么是输入和什么是输出。而复杂性应该是什么。 – codebusta

考虑实体作为图的顶点，如果实体兼容，则在顶点之间添加边。

在此结果图中，您定义的物种对应于clique的定义。

因此，找到最小物种数的问题等同于覆盖具有最小派系数量的图。这个问题被称为minimum clique cover并且是NP-complete。

来源

2015-11-04 19:29:51

如果将每条边都变为非边，那么它也等同于图着色，反之亦然。（我提到这个以防有人想找到求解器的实现......） –

找到最佳的兼容元素组的算法

回答

相关问题