寻找最优兼容元素组的算法

Question

寻找最优兼容元素组的算法

javaalgorithmgroupingcombinationscombinatorics

5

我有一组实体需要分组，这些组称为“物种”。定义所有物种的集合称为“宇宙”，一个实体必须属于一个且仅属于一个物种。为此，我有一个名为“f”的布尔不传递函数，该函数返回传递的两个实体是否兼容。与彼此兼容的实体组成的组定义了一个“物种”，而被认为相互不完全兼容的物种组成了一个“宇宙”，假设两个物种的兼容性由所有实体的兼容性定义。

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

我尝试过以下方法，我的函数返回一个有效的宇宙，但不是可能具有最小物种数的宇宙。

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

- Lucas Cleto

顺便提一下：species的单数形式仍然是species，而specie则是一个完全不同的词。 - ciamej

很遗憾，你的解决方案是 O(n^3)，而我的是 O(n^4)。如果性能对你来说是个问题，我可以考虑一种更快的计算方法。 - ciamej

你能提供输入和输出是什么，还有复杂度应该是多少吗？ - codebusta

1

很遗憾，我的解决方案是错误的。看来这个问题比我想象的要难。我认为它是NP难问题，因此唯一可能的精确算法将是指数级别的... - ciamej

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter de Rivaz · Accepted Answer

考虑将实体视为图的顶点，并在顶点之间添加边，如果实体是兼容的，则它们之间存在一条边。

因此，在这个产生的图中，你对物种的定义对应于团的定义。因此，找到最小数量的物种的问题等同于用最少数量的团覆盖图。这个问题被称为最小团覆盖问题，并且是NP完全问题。