Reduction maximum d'ensemble.

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.

Il y la méthode brutale qui consiste à explorer toutes les solutions possibles. Mais bon, c'est en O(2^n), donc irréalisable au delà de quelques pièces/personnes.

Sinon, je trouve que ce problème a une sale tête de problème NP complet, donc il n'existe peut-être pas d'algorithme polynomial pour le résoudre...

Est ce que tu veux absolument LA meilleure solution, ou une solution pas trop mauvaise te suffirait ?

Je cherche effectivement la meilleure solution.

Le programme tournera sur des ensembles pouvant aller sur 10000 pieces - 10000 personnes

J'apprecierais cependant de toujours avoir LA meilleure solution. ^_^

mmmm ça ressemble fortement au problème traité dans ce fil :

http://www.developpez.net/forums/sho...d.php?t=292604

ici-même... (je ne connaissais pas le terme, mais "problème de la célébrité"..)

La représentation des données y ressemble un peu, mais il me semble que la complexité algorithmique de ce problème est bien supérieure !

Et vu la quantité de données, j'aurais presque envie de dire que c'est peine perdue. Le seul algo que je vois est l'algo brutal, qui demanderait un nb de calculs de l'ordre de 2^10000, soit environ 10^3000 opérations...

Et si quelqu'un confirme que c'est bien un pb NP complet, faudra s'orienter vers une résolution approchée.

Pour voir si c'est un problème NP, on peut modéliser ce problème comme un graphe bipartie entre les personnes et les pièces, les arcs montrant quelles personnes peuvent monter quelles pièces. Résoudre ce problème reviendrait donc à trouver (dsl, je ne me souviens plus des termes exacts) le plus petit ensemble de sommets-personnes tels que tous les sommets-pièces soient atteints par au moins un arc.

Sinon, ça a de fortes similitudes avec ce pb NP :
http://fr.wikipedia.org/wiki/Probl%C...verture_exacte

Je ne connais pas tous les problèmes listés ici, mais ça peut ptet dire quelque chose à quelqu'un :
http://fr.wikipedia.org/wiki/21_prob...mplets_de_Karp

Bon, bref... perso, la solution exacte me semble mal barrée, quelle que soit la puissance de calcul dont tu disposes...

Mais j'espère pour toi que je me trompe !

En attendant l'arrivée des ordinateurs quantique, faudra ptet se contenter d'une solution approchée.

Citation:

---

Envoyé par fumidu

Pour voir si c'est un problème NP, on peut modéliser ce problème comme un graphe bipartie entre les personnes et les pièces, les arcs montrant quelles personnes peuvent monter quelles pièces. Résoudre ce problème reviendrait donc à trouver (dsl, je ne me souviens plus des termes exacts) le plus petit ensemble de sommets-personnes tels que tous les sommets-pièces soient atteints par au moins un arc.

---

On peut aussi le voir comme le probleme du voyageur de commerce avec une contrainte sur les tournées possibles.

enfin bon, si tu preferes les graphes biparties... :P

Bonjour,

Je suis pas sur, mais il me semble que cela peut-être cela pourrait être résolu par l'algorithme hongrois.

Citation:

---

Envoyé par Graffito

Bonjour,

Je suis pas sur, mais il me semble que cela peut-être cela pourrait être résolu par l'algorithme hongrois.

---

Hum... j'ai un doute. Dans l'algo hongrois, les coefficients de la matrice des couts sont indépendants.

Ici, les couts sont variables. Si tu elis (p1.z0), alors les couts de (p1.z1) (p1.z2) et (p2.z6) deviennent nuls.

Effectivement, l'algo hongrois te donnera une solution, mais je doute que ce soit la meilleure.

Salut
Je te propose une méthode qui vaut ce qu'elle vaut, je l'ai testée, sur ton exemple, elle me donne une solution minimale mais il faudrait voir sur plus de pieces et de bonhommes.

J'effectue une boucle.
A chaque tour de boucle

1. je selectionne la pièce qui est posée par le moins de personne
2. Je selectionne dans la liste des personnes de la pièce selectionnée celle qui pose le plus de pièces
3. j'enlève cette personne et je mets à jour les pièces posées par les autres personnes en leur enlevant celles qui sont déjà posées

La boucle s'arrête évidemment quand il n'y a plus de pièce à sélectionner.

C'est un problème de couverture d'hypergraphe de poids minimum (proche en effet du problème de couverture exacte). C'est un problème célèbre en optimisation combinatoire.
Tu peux faire une recherche sur Google avec les termes "Set covering problem" pour plus d'informations en anglais.

Citation:

---

Envoyé par lannel

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

---

C'est marrant comme ca ressemble a la problematique du download des chunk sur un réseau P2P... :roll:

@Trap D: J'en ai un autre

1. Je choisis la personne qui a le plus de pieces
2. Je pose ces pieces sur la table
3. Je supprime ces pieces chez toutes les personnes
4. je boucle au 1, tant qu'il reste des personnes avec des pieces