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

Question

我有一组实体,我需要将这些实体分组调用specie.所有物种定义的呼叫集合Universe和实体必须属于一个且仅属于一个物种.为此,我有一个布尔不及物函数调用f,如果两个实体通过参数传递兼容,则返回.A specie由一组彼此兼容的实体universe定义,并且a 由一组彼此不完全兼容的物种定义,假设两个物种的相容性由其所有实体的兼容性定义.

如何确定包含给定实体集可能的最小物种数的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

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

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

因此，找到最少物种数的问题相当于用最少的派系覆盖图。这个问题被称为最小集团覆盖，并且是 NP 完全问题。