Algorithmus, um die optimale Gruppe von kompatiblen Elementen zu finden

Question

Ich habe eine Reihe von Einheiten und ich muss diese Einheiten in Gruppen mit der Bezeichnung specie gruppieren. Die Menge aller Arten definiert Anrufe Universe und eine Entität muss zu einer einzigen Spezies gehören. Dafür habe ich eine boolesche intransitive Funktion namens f, die zurückgegeben wird, wenn zwei Entitäten, die von Parametern übergeben werden, kompatibel sind. Eine specie ist definiert durch eine Gruppe von Einheiten, die miteinander kompatibel sind, und eine universe wird durch eine Gruppe von Spezies definiert, die nicht vollständig miteinander kompatibel sind, unter der Annahme, dass die Kompatibilität von zwei Arten durch die Kompatibilität aller ihrer Einheiten definiert ist.

Wie kann ich das Universum bestimmen, das die kleinste mögliche Anzahl an Spezies für eine gegebene Menge von Entitäten enthält?

Ich versuchte wie folgt und meine Funktion gibt ein gültiges Universum zurück, aber nicht das mit der kleinsten möglichen Anzahl von Arten.

Answer 1

Betrachten Sie die Entitäten als Scheitelpunkte eines Graphen und fügen Sie Kanten zwischen Scheitelpunkten hinzu, wenn die Entitäten kompatibel sind.

In diesem resultierenden Diagramm entspricht Ihre Definition einer Spezies der Definition eines .

Daher ist das Problem, die minimale Anzahl von Arten zu finden, gleichbedeutend mit der Abdeckung des Graphen mit der kleinsten Anzahl von Cliquen. Dieses Problem ist als minimum clique cover bekannt und ist NP-vollständig.