Алгоритм для поиска оптимальной группы совместимых элементов

Question

У меня есть набор объектов, и мне нужно сгруппировать эти объекты в группах с именем specie. Набор всех видов определяет вызовы Universe, и сущность должна принадлежать одному и только одному экземпляру. Для этого у меня есть логическая непереходная функция, называемая f, которая возвращает, если два объекта, переданные параметрами, совместимы. A 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-полная.