Discussion :

[xwz]

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 :)

[tbc92]

Ici, comment arrive-t-on à voir que (p1,p2) est optimal.
p2 est incontournable. Si on ne prend pas p2, on aura au mieux 1 élément (A).
On prend p2. Et de la même manière, généralisons, on prend toutes les qui sont présentes dans au moins 50% des éléments+1.
Ensuite, on complète comment ?
Une démarche, c'est de systématiquement ajouter les propriétés qui sont beaucoup présentes. Et basta. Jusqu'à arriver à la couverture de 50%.
Tu n'as pas la certitude que la solution sera optimale, mais tu devrais t'en approcher.

Tu peux aussi compter ainsi :
A=(p1,p4,p5,p6,p9,p10,p12,p30,p35,p40)
B=(p1,p4,p5,p6,p9,p10,p12,p30,p35,p41)
C=(p1,p4,p5,p6,p9,p10,p12,p30,p35,p42)
D=(p1,p4,p5,p6,p9,p10,p12,p30,p35,p43)
E=(p1,p3,p5,p6,p9,p10,p12,p30,p35,p44,p45)
F=(p1,p3,p4,p6,p9,p10,p12,p30,p35)
G=(p7,p13)
H=(p8,p11,p14)
Et quelques autres éléments, ... on a déjà 40% des éléments qui sont 'couverts', et il nous en manque 1 ou 2. S'il manque encore 3 éléments, p1, p6, p9 etc sont incontournables, il faut forcément les prendre.

Les propriétés p1 ou p4 ou p5 sont présentes dans beaucoup d'éléments (5 ou 6 éléments chacune), mais elles sont présentes dans des éléments difficiles à atteindre, des éléments où il nous manque une dizaine de propriétés.
Alors que p7 ou p8 ou p11 ou p13 ou p14 rapportent immédiatement (ou presque) 1 élément.

Comme p1 a besoin de 9 autres propriétés pour compléter l'élément A, tu peux dire que p1 rapporte 1/10 point pour A, et idem pour les éléments suivants, donc p1 rapporte 4/10+1/11+1/9, pareil pour p6 ou p9 etc, alors que p7 ou p13 rapporte 1/2, et p8 ou p11 ou p14 rapportent 1/3


Une méthode souvent utilisée dans les besoins de ce genre, c'est ce qu'on appelle 'Monte-Carlo'.
Tu fais plein d'essais au hasard. Je prends telle et telle et telle propriétés, jusqu'à couvrir les 50% imposés. Et tu mémorises cette solution.
Et tu répètes ça, disons 1000 fois.
Puis tu analyses. Certaines des solutions ont nécessité 35 propriétés, d'autres en ont nécessité 38, voire 40.
Et là, tu regardes s'il y a des points communs : Sur les 100 solutions qui ont les meilleurs scores, toutes ont au moins 8 propriétés parmi p1,p2, ...p10 ;
Du coup, tu continues des essais au hasard, mais en prenant systématiquement au moins 8 propriétés parmi p1,p2, p10. Et tu affines.

[xwz]

Tout d'abord, merci pour ta réponse.

Je pense avoir saisi l'essentiel de ta première démarche, mais j'ai le sentiment qu'à un moment je pourrais me trouver bloquer si jamais j'ai toutes les combinatoire possible à base de {p1,p2,p3} + 1 et que ça représente moins de 50% je risque de me retrouver avec un nombre d'élément dans p' assez gros non?

Pour la seconde, même avec 1000 répétitions, j'aurais une combinatoire limité par rapport à ce que je pourrais avoir sachant qu'il faudrait que j'essaie 1000 fois avec 2 propriétés, 1000 fois avec 3 propriété (j'imagine que pour ça je dois réutiliser les 1000 d'avant en rajoutant une propriété aléatoirement au autres? ou je refais un aléatoire total?), ... au final c'est un surement plus rapide que ce que j'avais pensais faire mais je cherche vraiment à atteindre le minimum de propriétés et au final le temps de calcul n'est pas une vraie contrainte. Je pense juste qu'il y a une moyen plus optimale de faire les chose. Aujourd'hui il est prévu que j'utilise cet algorithme une à deux fois par mois mais dans le futur ça serait plutôt 1 fois par jours.

[dourouc05]

Ton problème semble être une variante du classique set covering. Le problème standard cherche à couvrir tous les items, pas une fraction d'entre eux, mais ça vaut sûrement la peine de jeter un oeil. Par exemple : https://en.wikipedia.org/wiki/Set_cover_problem et l'heuristique gloutonne (prendre l'ensemble qui couvre un maximum d'éléments pas encore couverts, ce que tu pourrais répéter jusqu'à atteindre la moitié de tes items à couvrir).

Sinon, ton problème spécifique est déjà étudié directement, par exemple https://arxiv.org/abs/1907.04413, mais ça pourrait être un chouia trop complexe à implémenter comme algorithme (d'abord résoudre un relâchement linéaire).

[anapurna]

Salut

je le verrai plus comme un algorythme multicritere
il faut regarde des MCDA dont le monte carlos en fait parti

= Min(Propiete)
= %N(max(Objet))

[mach1974]

https://github.com/fq00/worstCaseDominatingSet

[xwz]

Cool, merci pour tous ces pointeurs! Je me disais bien que je ne pouvais pas être le seul à avoir eu le problème et que des gens plus futés que moi l'avaient déjà résolu! Il ne me manquait que les mots clés pour trouver les solutions.

Je vais regarder tout ça plus en détails, mais je devrais pouvoir trouver mon bonheur dans tout ça.

Je marque donc le thread en résolu