Combinaisons avec contrainte

**myred** · 17/11/2015, 10h09

Bonjour à tous,

J'essaie de réaliser un algorithme qui permet de choisir 11 joueurs parmi une liste de joueurs avec plusieurs contraintes.

Il ne peut y avoir que 1 Gardien, 3 Défenseurs, 3 Milieux, 2 Attaquants et 2 Joueurs de n'importe quel poste dans une équipe.
Chaque joueurs à un prix et un score, le but est de sélectionner la meilleur équipe pour un budget donné. Un joueur est considéré meilleur qu'un autre s'il a un score plus élevé.

Variable global :
List<Joueur> listeDesJoueursTotals
Equipe equipeParfaite

Objet :
Joueur : Nom, Score, Prix, Poste
Equipe : Budget Disponible, List<Joueur>

J'ai déjà créée une algorithme qui test toutes les possibilités, sauf que c'est beaucoup trop long car la liste totale des joueurs est de 200... Donc plusieurs milliard de milliard de possibilités ...
Il y a donc moyen de prendre en compte le prix et le score de chaque joueurs pour réduire le nombre de possibilités, sauf que je n'y arrive pas ...

Des idées ?

**dourouc05** · 17/11/2015, 10h29

Si tu veux un algorithme spécifique, tu peux regarder du côté de la programmation dynamique, ça devrait bien s'appliquer ici (la difficulté devant être les différents types de joueurs…).

**myred** · 17/11/2015, 10h59

Effectivement sans la contrainte "type de joueur" le problème est le même que celui du sac à dos. Je vais chercher dans cette voie merci !

**Trap D** · 19/11/2015, 08h49

Tu peux regarder du côté de Prolog et des bibliothèques de programmation par contraintes (clpfd pour SWI-Prolog), i y a des options qui permettent d'élaguer les branches inutiles et de gagner un temps considérable.

**myred** · 20/11/2015, 14h47

Je n'ai pas réussi à pondre faire un algorithme utilisant la programmation dynamique car finalement le problème est trop différent du sac à dos. Je ne peux pas vraiment le décomposer en sous problème.

Tu peux regarder du côté de Prolog et des bibliothèques de programmation par contraintes (clpfd pour SWI-Prolog), i y a des options qui permettent d'élaguer les branches inutiles et de gagner un temps considérable.

Le problème est que je dois greffer cette partie dans une application lourde en C#. Utiliser un autre langage me forcerait à faire des liens compliqués entre les deux parties ...

**Trap D** · 20/11/2015, 15h38

Dommage, je te fournis quand même le lien qui permet de voir les liaisons SWI-prolog et C#.

**BufferBob** · 20/11/2015, 17h32

salut,

je me plante peut-être mais si j'ai bien compris, l'équipe parfaite n'est finalement déterminée que par une quantité maximum de points

dans ce cas un algorithme possible consisterait simplement à trier la liste des joueurs par leur nombre de points et composer son équipe avec les premiers de la liste (qui correspondent au poste voulu évidemment) en prenant juste soin de sélectionner les 2 joueurs de n'importe quel poste à la fin, non ?

Edit: au temps pour moi c'est la fatigue, j'ai oublié de lire qu'il fallait prendre le budget en ligne de compte

**dourouc05** · 21/11/2015, 15h42

Sinon, tu peux implémenter toi-même un moteur de programmation par contraintes rudimentaire, ça ira déjà beaucoup plus vite que l'exploration brutale.

**myred** · 23/11/2015, 10h21

J'ai finalement réussi à gagner beaucoup de temps d’exécution avec un moteur de programmation par contrainte (MSF).
Je ne connaissais pas ce type de programmation, ça m'a permis d'éclaircir énormément le code tout en gagnant en performance.

Merci

**dourouc05** · 24/11/2015, 09h30

Quoi, il y a de la programmation par contraintes là-dedans ? Je n'y ai jamais vu que de la programmation mathématique (qui, certes, aurait bien fonctionné dans ton cas, mais probablement moins naturellement que le CP).