Bonjour,
Le titre est je pense pas très clair, mais je vais essayer d'élaborer ça le plus clairement possible.
Ce que je cherche est fort probablement présent dans la théorie des ensembles... qu'on a presque tous vu à l'école mais ça commence à dater pour moi :).
Mon problème est le suivant:
Contexte: j'ai un ensemble fini de propriétés (p1, p2, p3, ...) il y en a disons 50. Accoter de ça, j'ai des objets qui sont représentés par ces propriétés, il peuvent avoir de 1 à 50 propriétés.
Besoin: je voudrais s'avoir comment trouver p' avec un cardinal minimum nécessaires pour pouvoir représenter un minimum de x% des objets présents. Le nombre de propriété nécessaire dois être minimum.
Voici un exemple pour représenter mon problème:
Propriétés:
p={p1,p2,p3,p4}
Objets:
A={p1}
B={p2,p3}
C={p2,p4}
D={p1,p2}
E={p2}
A partir de ces objets, je voudrais trouver les propriétés nécessaires pour représenter au minimum 50% des objets existant. Ici, la solution qui serait attendu est: p'={p1,p2} car je pourrais alors représenter A, D et E.
J'ai bien une idée d'algorithme qui pourrait bien fonctionner, mais qui pourrait prendre un temps fou pour traiter mes milliers d'objets existant. En gros ça serait de faire tous les couples de deux propriétés possible, puis de trois et etc. pour ensuite réduire les possibilités ... mais ça me semble complètement inefficace et je me dis qu'il n'est pas possible que personne n'ait déjà pensé à un tel problème avant moi!
Merci d'avance pour votre aide :)
Partager