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

我有一組實體，我需要將這些實體分組，稱爲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

如果將每條邊都變爲非邊，那麼它也等同於圖着色，反之亦然。（我提到這個以防有人想找到求解器的實現......） –

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

回答

相關問題