Votre question

Algorithme sur les Ensembles

Tags :
  • Logiciels
  • Programmation
Dernière réponse : dans Programmation
17 Avril 2005 14:07:58

Bonjour,

Je suis entrain de coder un logiciel et je bloque sur un algorithme, voici mon problème :
(Je n’utilise pas à certains endroits les termes mathématiques précis cependant j’espère que mon post reste compréhensible)

On a 3 ensembles : A(0;1;2;3;4) ; B(0;4;5;8;9) et C(1;2;3;5;10)

On doit rassembler ces 3 ensembles en 2 ensembles qui contiennent chacun le minimum de nombres possibles.
Si on forme un ensemble avec A et B on obtiendra : (0;1;2;3;4;5;8;9)
Si on forme un ensemble avec A et c on obtiendra : (0;1;2;3;4;5;10)
Si on forme un ensemble avec B et C on obtiendra : (0;1;2;3;4;5;8;9;10)

On voit que l'ensemble formé par A et C contient moins de nombre que les deux autres par conséquent les deux ensembles formées seront telles que :
L'ensemble N°1 sera formé de A et C
L'ensemble N°2 sera formé de B

Résoudre ce problème de tête est relativement simple mais lorsqu’il s’agit de traiter le même problème avec des milliers d’ensemble cela se corse un peu =)
Voila ce que doit faire mon programme :

Objectif :

On a 2048 ensembles contenant chacun 25 entiers naturels allant de 0 à 255.
Le but est de regrouper ces 2048 ensembles en seulement 256 ensembles.
Avec pour condition que chacun des nouveaux ensembles formés contiennent le minimum d'entiers naturels différents.

J’ai deux idées pour traiter ce problème cependant une demande trop de temps de calcul et l’autre me parait pas suffisamment performante, je poste donc ici dans l’espoir que quelqu’un indique une autre façon de traiter ce problème.

Idée 1 :

1) On analyse les nombres qui sont les plus fréquents
2) On choisit les 256 ensembles (A,F,G,H...etc) qui contiennent le plus de ces nombres redondants
3) On compare à A tous les autres ensembles et on détermine quel est l'ensemble B qui a le moins de différence avec A
4) On forme un nouvel ensemble C composé de A et de B
5) On compare C a tous les autres ensembles (sauf A et B) et on détermine quel est l'ensemble D qui a le moins de différence avec C
6) On forme un nouvel ensemble E composé de C et de D

Et on refait cela (2048/256) 8 fois puis ensuite on choisit effectue à nouveau cette étape avec l'ensemble F puis avec l'ensemble G... etc

A la fin on devrait obtenir 256 ensembles qui contiennent chacun le minimum de nombres possibles.

Cependant cette opération nécessite un certain nombre de boucles et vu le nombre d'ensembles de bases (2048) sa risque de prendre un certain temps de calcul.


Idée 2 :

Voici une autre solution qui n'est pas très rigoureuses et ne donne pas de très bon résultat mais est beaucoup plus rapide :

1) On analyse les nombres qui sont les plus fréquents
2) On choisit les 256 ensembles (A,F,G,H...etc) qui contiennent le plus de ces nombres redondants
3) On compare à l'ensemble A tous les autres ensembles et on détermine les 8 qui ont le moins de différence avec A.
4) On forme un ensemble B avec les 8 ensembles trouvés.

Et on effectue cela encore 255 fois avec les autres sous ensembles F puis G, puis H...etc

Je vous remercie à l’avance pour votre aide ainsi que d’avoir lu ce message.

Autres pages sur : algorithme ensembles

17 Avril 2005 14:22:39

Moi je ferais plus simple !

Je fais en 2 etapes :

1ere partie : Recolte d'information dans un tableau : Je compare l'ensemble A avec tout les autres ensembles et je mets le nombre d'element commun dans un tableau! ensuite je compare B avec tout les autres ensemble.. et je mets dans le tableau ... et ainsi de suite .. donc très simple , boucle imbriquée.
Tu auras qqch comme ceci

|A|B|7|
|A|C|3|
|A|D|6|
|B|C|8|
|B|D|1|
|C|D|6|

2eme partie : selon la troisième colonne, tu crée les nouvelles ensembles...

Et tu relance ton processus avec tes nouvelles ensembles ! Donc tu boucle encor tout simplement!

Finalement ta pas bcp de codes mais des boucles !

Critique de ton idée 1 point 3: tu compare A avec tous les ensembles et tu le fusionne avec celui qui a le plus de nbr commun.. disons l'ensemble D
Donc l'ensemble A + D donne le nouvel ensemble F disons avec 9element !

MAIS qui te dis pas que la fusion de D avec X t'aurais peut etre donné un ensemble de 3element !

Donc en gros en faisant comme tu le décris, tu prend pas en compte toutes les fusions ! et tu passes peut etre a coté de la fusion d'ensemble qui serait plus optimal .

Donc
1) A et H donne 10 et D et X donne 3.
pourrait etre mieux que
2) A et D donne 9 et H et J donne 7.


Dis moi ce que tu penses de tt ce que j'ai ecrit ;-)

Tom's guide dans le monde
  • Allemagne
  • Italie
  • Irlande
  • Royaume Uni
  • Etats Unis
Suivre Tom's Guide
Inscrivez-vous à la Newsletter
  • ajouter à twitter
  • ajouter à facebook
  • ajouter un flux RSS