Discussion :

[pysnoo]

Bonjour, j'essaye de mettre en place un algorithme me permettant de déterminer le meilleur résultat, donné suivant le nombre de points communs trouvés entre des cartes a jouer.

En fait chaque carte a trois caractéristiques : couleur, valeur et couleur du dos de la carte.

J'ai un ensemble de cartes, et il me faut trouver le meilleur score possible en assemblant les cartes les unes avec les autres, sachant que 3 points communs = 3 points, 2 points communs = 2 pts etc....

J'ai commencé à développer quelque chose en C++, tout d'abord en recherchant toutes les cartes ayant 3 points communs et en les supprimant. Ensuite je prends celles ayant 2 pts communs etc...

Le problème est que si je prend celles ayant 2 pts communs arbitrairement, celà me donne un résultat final faux. Je m'explique par un exemple :

4 cartes :
*1ere : rouge, 8, noir
*2e : rouge, 8, vert
*3e : orange, 2, vert
*4e : rouge, 3, noir

Du coup si je choisit la 1ere et la 2e ensemble, j'aurais un score final de 2pts. Alors que si je choisis la 1ere et 4e puis 2e et 3e, j'obtiens 4pts...

Sachant qu'il faut que ce soit le plus optimal possible car j'ai déjà un gros parcours d'arbre à faire avant ça. Le but de cet algorithme est d'optimiser le nombre de branches de l'arbre à explorer.

Merci.

[pseudocode]

Ça m'a tout l'air d'être un problème de "bin packing", donc surement NP-hard.