Algorithme de regroupement minimal

Question

J'ai un ensemble de valeurs, chaque valeur a un groupe possible. La valeur peut être répétée mais dans un groupe différent.

Quel sera un algorithme optimal pour obtenir le nombre minimum de groupes

Un ensemble d'échantillons: (12, groupe b) (38, groupe a) (12, groupe a)

Souhaité résultat: (38, groupe a) (12, groupe a)

(un seul groupe est utilisé)

- edit: J'ai besoin d'un algorithme pour trouver le nombre minimum de groupes d'un ensemble comme l'exemple ci-dessus. Si j'aurais un mauvais algorithme, il choisira (12, groupe b) (38, groupe a) Ceci est 2 groupes pour les mêmes valeurs au lieu d'utiliser un, pas ce que je veux

Answer 1

Si je comprends la question correctement, c'est la Set cover problem

L'algorithme glouton comme décrit dans le lien commence par le groupe a, puis se termine, car cela couvre déjà tous.

Notez qu'en général, il ne donne qu'une approximation de la solution optimale.