Thuật toán để tìm nhóm tối ưu các thành phần tương thích

Question

Tôi có một nhóm đối tượng và tôi cần nhóm các thực thể này thành các nhóm có tên là specie. Các thiết lập của tất cả các loài được xác định cuộc gọi Universe và một thực thể phải thuộc về một và chỉ có một specie. Đối với điều này tôi có một hàm boolean intransitive gọi là f trả về nếu hai thực thể, thông qua các tham số, tương thích. Một số specie được xác định bởi một nhóm các thực thể tương thích với nhau và universe được định nghĩa bởi một nhóm các loài không hoàn toàn tương thích với nhau, giả định rằng khả năng tương thích của hai loài được xác định bởi tính tương thích của tất cả các thực thể của nó.

Làm cách nào để xác định vũ trụ chứa số lượng loài nhỏ nhất có thể cho một nhóm thực thể nhất định?

Tôi đã thử như sau và hàm của tôi trả về một vũ trụ hợp lệ nhưng không phải là vũ trụ có số lượng loài nhỏ nhất có thể.

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

Xem xét các thực thể dưới dạng đỉnh của biểu đồ và thêm cạnh giữa các đỉnh nếu các đối tượng tương thích.

Trong biểu đồ kết quả này, định nghĩa của bạn về một loài tương ứng với định nghĩa của clique.

Do đó, vấn đề tìm số lượng tối thiểu của các loài tương đương với việc bao phủ đồ thị có số lượng nhỏ nhất của các dòng. Vấn đề này được gọi là minimum clique cover và hoàn thành NP.