Discussion :

[supierre]

Bonjour à tous,

J'ai un problème qui m'arrache les cheveux depuis un moment

Je simplifie mon problème lorsque je l'expose à vos yeux:

J'ai 6 étudiants
qui ont chacun des notes différentes (note sur 21... c'est pas commun)
et je dois distribuer 14 points supplémentaires pour ces 6 étudiants.

Les contraintes sont les suivantes:
-Pas plus de 6 point pour un même étudiant
-Ne pas Obtenir une note supérieure à 21

Je cherche à obtenir un algorithme me donnant toutes les répartitions possibles

Ex:
Si initialement:
Alain : 8
Romain : 14
Michel : 18
Fabienne : 12
Aurélie : 6
Luca : 15

j'aimerais avoir tout les résultats envisageables:

Ex:
Alain : 14,14,...
Romain : 20,20,...
Michel : 20,19,...
Fabienne : 12,13,...
Aurélie : 6, 6,...
Luca : 15,15,...


Mon sentiment est d'utiliser une formule mathématique pour compter les possibilités puis de boucler avec un For en suivant l'algorithme... que je cherche toujours.

J'apprécierais toute aide ou critique quelle qu'elle soit.

Merci

[sologne]

Bonjour,

voici une piste que j'ai commencé à explorer avec Prolog :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
chiffre(0).
chiffre(1).
chiffre(2).
chiffre(3).
chiffre(4).
chiffre(5).
chiffre(6).
chiffre(7).
chiffre(8).
chiffre(9).
 
 
solution([A,B,C,D,E,F]) :-
      chiffre(A),chiffre(B),chiffre(C),chiffre(D),chiffre(E),chiffre(F),
	  A=<6,B=<6,C=<6,D=<6,E=<6,F=<6,
	  A+B+C+D+E+F =:= 14.

et dans l’interpréteur tu saisies solution([A,B,C,D,E,F]). Puis le classique ; pour avoir les autres possibilité et de proche en proche tu as toutes les combinaisons possibles.

Tu peux faire évoluer ce bout de code si tu as les notes de départ, cela permettra de réduire le nb de solutions

[supierre]

Bonsoir, j'ai tenté d'utiliser Prolog... mais je n'y comprend pas grand chose.

j'ai donc réalisé une génération aléatoire de solution correspondant aux critères, avec une génération de 150000 solutions (sa m'a pris 45 min avec un code pas forcément optimisé) j'ai trouvé environ 143000 doublons, donc j'estime avoir obtenu toutes les réponses dont j'avais besoin. avec ces 6892 (précisément) lignes

dans le doute j'ai réalisé une autre salve de 10000 solutions, mais que des doublons sont sortis.

merci quand même de t'être intéréssé a mon problème

[sologne]

Bonjour,

J'ai vu que tu as mis résolu, mais cette nuit j'ai eu une idée et j'ai voulu la codée ce matin. Voici l'algo que tu pourras facilement adapté dans le langage de ton choix. (J'ai utilisé Windev)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
xNote_1, xNote_2, xNote_3, xNote_4, xNote_5, xNote_6 sont des numériques;
xNote_1_new, xNote_2_new, xNote_3_new, xNote_4_new, xNote_5_new, xNote_6_new sont des numériques;
i,j,k,l,m,n sont des entiers;
xNote_1 = 8; xNote_2 = 14; xNote_3 = 18; xNote_4 = 12; xNote_5 = 6; xNote_6 = 15;
 
TableSupprimeTout(TABLE_les_notes);
TableAjouteLigne(TABLE_les_notes,xNote_1,xNote_2,xNote_3,xNote_4,xNote_5,xNote_6);
 
POUR i = 0 _A_ 6
	POUR j = 0 _A_ 6
		POUR k = 0 _A_ 6
			POUR l = 0 _A_ 6
				POUR m = 0 _A_ 6
					POUR n = 0 _A_ 6
						SI ((i+j+k+l+m+n) = 14) ALORS
							xNote_1_new = xNote_1+i;
							xNote_2_new = xNote_2+j;
							xNote_3_new = xNote_3+k;
							xNote_4_new = xNote_4+l;
							xNote_5_new = xNote_5+m;
							xNote_6_new = xNote_5+n;
							SI (xNote_1_new<=21 ET xNote_2_new<=21 ET xNote_3_new<=21 ET xNote_4_new<=21 ET xNote_5_new<=21 ET xNote_6_new<=21) ALORS
								TableAjouteLigne(TABLE_les_notes,xNote_1_new,xNote_2_new,xNote_3_new,xNote_4_new,xNote_5_new,xNote_6_new);
							FIN
						FIN
					FIN
				FIN
			FIN
		FIN
	FIN	
FIN

De plus je te met en pièce jointe le fichier excel que cela à généré avec les 4956 solutions trouvées.

J'espère que cela pourra t'aider, Bon courage.

[supierre]

Fécilitation pour l'idée que tu as trouvée, elle est bien plus performante que la mienne, je prend avec plaisir

EDIT: pour les mêmes paramètres j'avais trouvé 4955 solutions.... donc au moins tu me prouve qu'il me manquait quelque chose... le problème de la génération aléatoire... c'est que c'est aléatoire.

[nono_31]

Bonjour à tous les deux,

@sologne
Tu peux encore optimiser ton code en ajoutant des tests sur la somme des bonus à partir de la boucle k.

Sinon, vous pouvez résoudre ce problème en quelques lignes de code grâce à la Programmation Par Contraintes.
Voici un fichier source pour le solveur Choco (Java).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
import static choco.Choco.*;
import choco.Options;
import choco.cp.model.CPModel;
import choco.cp.solver.CPSolver;
import choco.kernel.common.logging.ChocoLogging;
import choco.kernel.model.Model;
import choco.kernel.model.variables.integer.IntegerVariable;
import choco.kernel.solver.Solver;
 
public class RepartitionNotes {
 
 
	public static void main(String[] args) {
		Model m= new CPModel();
		int[] notes = {8, 14, 18, 12, 6, 15};
		IntegerVariable[] bonus = makeIntVarArray("B",6, 0, 6,Options.V_BOUND);
		for (int i = 0; i < notes.length; i++) {
			m.addConstraint(
					leq(plus(notes[i], bonus[i]),21)
					);
		}
		m.addConstraint(eq(sum(bonus),14));
		Solver s = new CPSolver();
		s.read(m);
		ChocoLogging.toDefault();
		s.solveAll();
		ChocoLogging.flushLogs();
	}
}

Vous devriez reproduire le programme très facilement avec n'importe quel solveur de contraintes.
Voici le résultat de l'exécution:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
** CHOCO : Constraint Programming Solver
** CHOCO v2.1.6 (November, 2012), Copyleft (c) 1999-2012
- Search completed
  Solutions: 4955
  Time (ms): 169
  Nodes: 6245
  Backtracks: 6244
  Restarts: 0

[sologne]

Bonjour,

En effet une programmation par contrainte est plus rapide pour ce type de Problème. D’ailleurs j'ai proposé un début de solution dans cette direction avec mon premier message, avec l'utilisation de prolog.

Par contre je ne connaissait pas choco en Java et je vais le regarder de plus pret.

Quant à l'optimisation des boucles je suis également OK, avec toi, mais pour être honnête, j'ai codé cela en dix minutes et j'avais pas trop envie de chercher le code optimum au risque de louper des solutions, mais dans l'absolu tu as raison :-)

[nono_31]

Oui, les solutions proposées étaient tout aussi fonctionnel.
Normalement, la programmation par contraintes doit mieux gérer les contraintes arithmétiques que la programmation logique.

L'intérêt est que tu n'as plus à optimiser les boucles toi-même