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

Question

我有一组实体，我需要将这些实体分组到名为 specie 的组中。定义的所有物种的集合称为 Universe，并且一个实体必须属于一个且仅属于一个物种。为此，我有一个名为 f 的 boolean 不及物函数，如果通过参数传递的两个实体兼容，它会返回。 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并且是 NP 完全的。