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

Question

我有一组实体，我需要将这些实体分组到名为 specie 的组中。所有物种定义的集合调用 Universe 并且一个实体必须属于一个且仅属于一个物种。为此，我有一个名为 f 的布尔不及物函数，如果通过参数传递的两个实体兼容，则 returns 是兼容的。 specie 由一组彼此相容的实体定义，universe 由一组彼此不完全相容的物种定义，假设两个物种的相容性定义为它所有实体的兼容性。

对于给定的一组实体，我如何确定包含最少物种的宇宙？

我尝试如下，我的函数 returns 是一个有效的宇宙，但不是物种数量最少的宇宙。

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 并且是 NP 完全问题。

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

Algorithm to find the optimal group of compatible elements

java

algorithm

grouping

combinations

combinatorics