Trouver l'ensemble maximal

Question

J'ai une base de données avec 4 tables.

Trois de ces tables contiennent des informations sur des entités spécifiques (instances, commandes et agents). La quatrième table (essai) contient des données sur une combinaison de ces trois et quelques données supplémentaires.

Je voudrais trouver un ensemble d'essais tels que chaque instance utilisée soit exécutée sur la même commande et le travailleur, je voudrais trouver le plus grand ensemble disponible. Par exemple:

Si chaque instance (environ 150) s'exécutait sur le travail 1, la commande 1 - ce serait un ensemble complet. Mais un très petit ensemble complet comme leur serait seulement 1 instance/commande/ensemble de travailleurs.

serait mieux d'être loin:

trouver 50 cas qui ont travaillé sur 10 machines/paires de commande - les instances restantes sont ignorées.

Mes tailles de table ne sont pas grandes, environ 150 instances, 5 commandes et 30 travailleurs. Jusqu'à présent, 8 000 essais ont été effectués pour ces données.

Je peux penser à une approche force brute:

Pour chaque cas de comptage de paires travailleur/commande uniques, trouver le plus grand nombre puis sélectionnez tous les essais avec cette paire travailleur/commande. Si je l'ai fait pour le plus grand nombre de paires travailleur/commande, je peux être en mesure de les combiner, mais cela semble une solution laineuse.

Quelles sont mes autres options de langue n'est pas un problème, mais je préfère (dans l'ordre de préférence) R, MySQL, PHP, Java, C, autre.

Answer 1

Il semble que vous ayez un graphe bipartite, où les sommets dans une partie correspondent à des instances, les sommets dans l'autre partie correspondent à des paires command/worker, et les bords correspondent à des essais. Vous voudriez trouver des sous-ensembles d'instances et des paires command/worker induisant un biclique maximisant un paramètre de taille; peut-être le nombre d'arêtes? Malheureusement, il est probable que, quel que soit votre objectif, le problème sera NP-difficile.

Néanmoins, un algorithm to enumerate all maximal bicliques peut valoir la peine d'essayer.