Discussion :

[lannel]

Bonjour a tous,

je vous soumets un problème pour lequel je n'arrive pas a trouver l'algorithme.

Je le présente par l'exemple :

Soit un puzzle (Z) de 10 pièces numérotées de 0 a 9.
Il y a 10 personnes qui savent positionner 1 ou plusieurs pièces suivant ces règles :
- p1 : z0,z1,z2,z6 (personne 1 sait positionner pièces 0,1,2 et 6)
- p2 : z0,z1,z3,z7
- p3 : z0,z2,z3,z9
- p4 : z1,z2,z3,z5
- p5 : z4,z5
- p6 : z3,z4,z5
- p7 : z0,z6,z7,z9
- p8 : z1,z6,z7,z9
- p9 : z7,z8
- p10 : z2,z6,z9

évidemment si je prends les 10 personnes j'aurais mon puzzle.
Cependant elles coutent cher, donc je voudrais en prendre le minimum.

Il semblerait que 3 personnes suffisent : P2,P4 et P7.

Voila, entre autre, j'aimerais trouver l'algorithme qui sait réduire au max un tel ensemble suivant des règles de ce style.

Merci beaucoup.

[the-gtm]

Il n'y a que 2^10 - 1 ensembles donc une recherche exhaustive devrait aller vite

[lannel]

Merci pour le conseil, mais le puzzle ne fait pas 10 pieces ....

Le programme traitera un ensemble pouvant aller jusqu'a 10000.
Le recherche exhaustive n'est pas viable.

Cet exercice me semble tres "scolaire" mais je n'arrive pas a lui coller un algo dessus.

[the-gtm]

La taille du problème dépend surtout du nombre de personnes, pas trop du nombre de pièces dans le puzzle.

Sinon tu peux partir d'un ensemble contenant toutes les personnes et les enlever une à une jusqu'à ce qu'il en manque, ou bien faire l'inverse : partir d'un ensemble vide et ajouter des personnes jusqu'à ce que ça suffise.

La difficulté c'est que dans les deux cas, à chaque étape il faut faire plusieurs "branches" pour chaque personne qui n'est pas encore ajoutée (ou pas encore enlevée). Chacune des branches a elle même des sous branches et ainsi de suite jusqu'à arriver à un ensemble minimal.

[lannel]

Premierement merci de t'interesser a mon probleme.

pour te donner toutes les informations, le nombre de personnes (au debut) est egal au nombre de pieces : 10z-10p, 100z-100p, 10000z-10000p etc.

Comme tu peux l'imaginer l'ensemble de recherche grossi exponentiellement.

Voila ou j'en suis :

-tri des ensembles de chaque personne selon un ordre numerique :
dans notre cas
- p1 : z0,z1,z2,z6
- p2 : z0,z1,z3,z7
- p3 : z0,z2,z3,z9
- p7 : z0,z6,z7,z9
- p4 : z1,z2,z3,z5
- p8 : z1,z6,z7,z9
- p10 : z2,z6,z9
- p6 : z3,z4,z5
- p5 : z4,z5
- p9 : z7,z8

- pour chaque element s'il n'apporte rien (redondance par rapport a un autre) il degage sinon je le garde et passe au suivant.

l'algo marche mais :
-si je pars du bas il reste 3 personnes (p6,p8 et p3) -> le je suis content
-si je pars du bas il reste 4 personnes (p7,p8,p10 et p6) -> le je suis content aussi car j'ai bien reduit l'ensemble mais je ne suis pas au minimum.

Ce que je n'arrive pas a trouver c'est l'infomation de comment debuter pour arriver au minimum ? que me manque t'il dans ma reflexion ?

merci

[JMLLB]

Je pars du principe que tu recherches LA meilleure solution et non pas une solution pas trop mauvaise mais que tu peux calculer rapidement.
C'est donc bien une exploration systématique que tu souhaites faire et non pas implémenter une heuristique.

Je te conseille dans ce cas de voir l'algo sous la forme d'un arbre de recherche.

A chaque noeud tu rajoutes une personne que tu ne posèdes pas encore.
A la racine tu as n branches (n étant tes n personnes).
Chacune de ces n branches à n-1 sous branches et ainsi de suite sur une profondeur de n pour un total de n! branches.

A chaque noeud il faut que tu calcule le "poids" de ton noeud.
Ce score te permet de savoir si tu as atteinds ton but ou si tu doit continuer (et si tu réalisais une heuristique ça te permettrais de faire des choix sur les noeuds à développer...).
Dans ton cas le poid peut être le nombre de pièce qui te manquent.

Pour supprimer les doublons (deux branches présentant les mêmes personnes mais dans un ordre différent) il intéressant d'introduire la notion de signature.
Pour chaque noeud calcule sa signature.
Si tu possèdes déjà un noeud de même signature tu ne le traites pas sinon tu développe la branche.
Une signature valide est la suivante: pour chaque personne représentée dans ton noeud calcule 2^i avec i l'indice de la personne. Tu sommes l'ensemble de ces termes et tu as la signature du noeud.

A noter que tu peux utiliser une formule du même genre pour le poid et juste faire une comparaison avec le résultat de la formule pour l'ensemble des pièces. Ca t'évite de fastidueuses vérifications sur les pièces en doublons si tu implémentes un petit OU logique.

J'espère que ça peut t'aider! C'est plus facile à expliquer avec des graphes et des formules mais j'ai un peu la flemme.

[JMLLB]

l'algo marche mais :
-si je pars du bas il reste 3 personnes (p6,p8 et p3) -> le je suis content
-si je pars du bas il reste 4 personnes (p7,p8,p10 et p6) -> le je suis content
merci

Je suis désolé de faire les rabat-joie mais tu ne peux pas être content dans les 2 cas!

Je ne sais pas si la connaissance de n-1 pièces suffit à placer n pièces mais si c'est la cas:
3 personnes->soit content
4 personnes->ne soit pas content, tu n'as pas trouver la meilleur combinaison

Dans le cas il faut connaitre n pièces pour placer n pièces:
3 personnes->ne soit pas content, ta combinaison n'est pas solution
4 personnes->soit content, tu as trouvé une des meilleurs combinaisons

En tout état de cause il important de savoir dans quel cas tu te trouves!

Dernière chose pour optimiser ta recherche (limiter le nombre de noeud explorés) il est intéressant de trier tes personnes selon leur intérêt:

-indispensable: seul à connaitre l'emplacement d'une pièce (p9)
-doublon: une autre personne connait exactement les même emplacements
-touriste: une autre personne connait tout les emplacements qu'il connait plus au minimum une autre (p5)
-quidam: n'appartient à aucune des catégories précédantes

Tu sors les indispensables du jeu ainsi que les pièces qu'ils connaissent.
Tu sors les touristes, ils ne font pas partie de la meilleur combinaison
Tu ne gardes qu'un doublon de chaque type
Tu développes ensuite en priorité les personnes qui te font découvrir le plus de pièces que tu connaissais pas au niveau de ton noeud.

Pour ces optimisations je suis parti du principe qu'il faut connaitre n pièces pour en placer n et que tu choisis une exploration de ton arbre en largeur plutôt qu'en profondeur.

De plus, suivant les données que tu vas devoir traiter il peut tout à fait être plus judicieux d'avoir un traitement indistinct.
Le tri des personnes n'est pas gratuit et peut très bien avoir un coût prohibitif par rapport au gain.

Le mieux c'est d'avoir un bon critère de choix (traitement en priorité des personnes qui te font découvrir le plus de pièces) qui te mette de côté les touristes et les doublons sans avoir de prétraitement pour autant.
De toute manières le moment où les indispensables sont pris en compte n'est pas primordial.