plus grand ensemble (propriété non transitive)

[destroyer-duck]

Bonjour,

J'ai un problème à résoudre mais je n'arrive pas à le faire en un temps raisonnable lorsque le nombre d'élément est grand alors j'espère pouvoir obtenir de l'aide.

J'ai un ensemble d'éléments mathématiques. entre ces éléments il existe une relation binaire qui permet de dire si deux éléments sont liés. Il est important de préciser que cette propriété n'est pas transitive. On note ~ l'opération de relation. Si a~b et b~c sont vrais alors on ne peut rien dire sur le résultat de a~c.

Mon but est de trouver le cardinal du plus grand ensemble noté (E) tel que
pour tout (x,y) € E² x~y.

Pour le moment l'algorithme le plus rapide que j'ai trouvé était de tester toutes les combinaisons d’éléments (j'évite les doublons en associant à chaque objet un identifiant unique entier et en ne considérant que les ensemble d'identifiants décroissants). Cependant à partir de 45 éléments le temps de calcul est déjà trop conséquent.

Je suis débutant en algorithmique, peut être existe-til un algorithme standard pour faire ça mais je n'ai pas trouvé sur internet.

Merci beaucoup de votre aide.

[pseudocode]

D'après ce que je comprend de ton problème, il s'agit de trouver la plus grande clique dans un graphe.

"maximum clique problem"

[destroyer-duck]

Merci beaucoup,

je vais lire ça et je retourne vous dire si c'est ce que je cherchais.

[destroyer-duck]

C'est exactement cela. Merci beaucoup. Mon problème peut se ramener à un graphe à n où il y a entre 0 et n-1 liens par sommets. Il semble que dans çe cas les algorithme sont difficilement implémentables

[pseudocode]

Envoyé par destroyer-duck

C'est exactement cela. Merci beaucoup. Mon problème peut se ramener à un graphe à n où il y a entre 0 et n-1 liens par sommets. Il semble que dans çe cas les algorithme sont difficilement implémentables

C'est un problème NP-Hard pour lequel les algos de résolution existant sont exponentiels en temps.

Pour autant, ces algos sont peut-être suffisants pour satisfaire tes contraintes: nmb d'élements, nmb de liaisons, ressources CPU/Mem disponibles, délai maximum, ...

[destroyer-duck]

il y a 500 sommets dans mon graphe.
Entre 0 et 499 liaisons par sommet.
et le tout doit être exécuté en T<0.1s

J'ai essayé de regarder les publications mais je pense que si j'essaie de comprendre ça : lien. Je pense que je ferais mieux d'abstraire différemment le problème.

[pseudocode]

Envoyé par destroyer-duck

il y a 500 sommets dans mon graphe.
Entre 0 et 499 liaisons par sommet.
et le tout doit être exécuté en T<0.1s

Whoo. Ca parait difficilement atteignable. Par exemple, dans le papier "An improved bit parallel exact maximum clique algorithm", ce genre de temps n'est atteignable que pour 100/150 sommets.

Je pense que je ferais mieux d'abstraire différemment le problème.

Effectivement. Tu peux toujours nous décrire le problème de départ si tu y es autorisé.