Génération emploi du temps à partir de faits

**narcis60floyjo** · 29/04/2011, 15h05

Bonjour à tous, chers amis codeurs,

voilà, je fais appel à vous car j'ai besoin de votre aide. En effet, à partir d'un ensemble de faits, je dois générer un emploi du temps possible qui soit correct, sans conflits.

Actuellement, je me trouve avec les faits suivants :

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
33
34
35
36
37
38
 
creneau('9h_11h').
creneau('14h_16h').
 
jour(mercredi).
jour(vendredi).
 
typeEnseignement(competition).
typeEnseignement(entrainement).
typeEnseignement(match).
 
prof(prof1).
prof(prof2).
 
moduleEns(football,entrainement).
moduleEns(football,match).
moduleEns(natation,entrainement).
moduleEns(natation,competition).
 
salles(stade,entrainement).
salles(stade,match).
salles(bassin,entrainement).
salles(bassin,competition).
 
profDispo(prof1,mercredi,'14h_16h').
profDispo(prof1,vendredi,'9h_11h').
profDispo(prof2,mercredi,'9h_11h').
profDispo(prof2,vendredi,'14h_16h').
 
profNonDispo(prof2,vendredi,'9h_11h')
 
salleDispo(stade,mercredi,'14h_16h').
salleDispo(stade,vendredi,'9h_11h').
salleDispo(bassin,mercredi,'9h_11h').
salleDispo(bassin,vendredi,'14h_16h').
 
salleNonDispo(bassin,vendredi,'9h_11h').
salleNonDispo(stade,mercredi,'9h_11h').

Je précise qu'il n'y a pas d'indications sur ce que peut faire un prof, ni où doit se faire un enseignement. Donc on peut très bien se retrouver à faire un entrainement de natation dans le stade. Et tous les profs peuvent enseigner n'importe quel cours.

J'ai essayé de faire ça :

Code :

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

1
2
3
4
5
6
 
emploiDuTemps(Salle,Prof,Jour,Creneau,Cours,Ens):-
   salleDispo(Salle,Jour,Creneau),
   profDispo(Prof,Jour,Creneau),
   salles(Salle,Cours),
   moduleEns(Ens,Cours).

Mais cela me retourne, en gros, tous les cas possibles (j'ai pas vérifié en détail, mais à peu près ça).

Extrait du résultat de cette commande :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Salle = stade,
Prof = prof1,
Jour = mercredi,
Creneau = '14h_16h',
Cours = entrainement,
Ens = football ;
 
Salle = stade,
Prof = prof1,
Jour = mercredi,
Creneau = '14h_16h',
Cours = entrainement,
Ens = natation ;

Rien que là, on se trouve en situation de conflits car deux enseignements (football et natation) vont se dérouler au même endroit, à la même heure, le même jour, avec le même prof.

Donc comment je pourrais faire pour générer un emploi du temps correct, sans conflits ? J'ai pensé à utiliser des listes, du genre listes de créneaux possibles, d'enseignements, de salles, pour une journée, et dès que quelque chose est utilisé, je l'enlève d'une des listes, et je vais piocher dans la liste à chaque fois. Mais je ne sais pas si c'est la bonne piste à exploiter, et si c'est une bonne idée, je ne sais pas comment la réaliser.

Merci de votre aide, j'en ai grandement besoin. (je dois finir tout ça avant Dimanche soir).

**narcis60floyjo** · 30/04/2011, 00h26

Personne ne peut m'aider ?

J'ai réussi à retourner une liste des propositions possibles :

Code :

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

1
2
3
4
5
6
7
8
9
 
emploiDuTemps(Salle,Prof,Jour,Creneau,Cours,Ens,Edt) :-  
  findall((Salle,Prof,Jour,Creneau,Cours,Ens), 
           (salleDispo(Salle,Jour,Creneau),
            profDispo(Prof,Jour,Creneau),
            salles(Salle,Cours),
            moduleEns(Ens,Cours)),
           Edt),
  afficher(Edt).

Voici le résultat de cette "fonction" :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
stade,prof1,mercredi,14h_16h,entrainement,football
stade,prof1,mercredi,14h_16h,entrainement,natation
stade,prof1,mercredi,14h_16h,match,football
stade,prof1,vendredi,9h_11h,entrainement,football
stade,prof1,vendredi,9h_11h,entrainement,natation
stade,prof1,vendredi,9h_11h,match,football
bassin,prof2,mercredi,9h_11h,entrainement,football
bassin,prof2,mercredi,9h_11h,entrainement,natation
bassin,prof2,mercredi,9h_11h,competition,natation
bassin,prof2,vendredi,14h_16h,entrainement,football
bassin,prof2,vendredi,14h_16h,entrainement,natation
bassin,prof2,vendredi,14h_16h,competition,natation

On remarque bien les conflits : un prof ne peut pas donner deux cours le même jour à la même heure. Une salle ne peut pas être réservée le même jour à la même heure par deux profs différents (dans cet exemple, il n'y a qu'un prof pour une salle, mais dans les autres fichiers prolog, plus fournis, il y aura certainement ce cas là à gérer).

Comment pourrais-je filtrer cette liste, en enlevant les conflits ?

Merci à tous !

**Trap D** · 30/04/2011, 11h29

L'idée d'utiliser une liste pour chaque type de faits est une bonne idée.
La recherche est obligatoirement longue.
le problème des emplois du temps est connu et je pense qu'une recherche sur les méthodes de résolution sur Internet devrait vous donner des pistes.

**narcis60floyjo** · 30/04/2011, 15h47

Ca ne m'aide pas vraiment tout ça.

Mais je pense être sur une bonne piste. Je vais essayer de la faire marcher. De toute façon, j'ai pas le choix. Faut que ca soit terminé ce soir.... Allez, courage !!!!

**Trap D** · 30/04/2011, 16h11

Tu t'y prends peut-être un peu tard

**narcis60floyjo** · 30/04/2011, 16h43

Je voudrais tester si un élément fait partie d'une liste à 2 dimensions.

Code :

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

1
2
3
4
5
6
 
estDansListe(Elem,[Tete_Liste|Queue_Liste]) :- 
  (memberchk(Elem,Tete_Liste) -> 
     true ; 
     memberchk(Elem,Queue_Liste)
  ).

Est-ce que c'est possible de faire ça ? J'aimerais faire en sorte que si Elem fait partie de la liste Tete_Liste (à la base, j'ai une liste 2D), alors je m'arrete en renvoyant true, sinon je parcours la liste de départ et je reteste. En gros, je voudrais arrêter la récursivité si l'élément est trouvé.

Est-ce possible ?

**Trap D** · 30/04/2011, 17h01

Oui.

**narcis60floyjo** · 30/04/2011, 17h12

Ok, et pour tester qu'un triplet de valeurs est présent dans une ligne de liste ?

Finalement, ma liste Edt peut être représentée ainsi :
Edt =
Edt[0]=[stade,prof1,mercredi,'14h_16h',entrainement,football]
Edt[1]=[stade,prof1,mercredi,'14h_16h',entrainement,natation]
Edt[2]=[stade,prof1,mercredi,'14h_16h',match,football]
Edt[3]=[stade,prof1,vendredi,'9h_11h',entrainement,football]

Donc j'aimerais tester si le triplet (prof1,mercredi,'14h_16h') est déjà présent dans une ligne de la liste Edt.

Comment pourrais-je faire ce test ?

**narcis60floyjo** · 30/04/2011, 17h41

Je viens de faire ça :

Code :

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

1
2
 
estDansListe(Elem1,Elem2,Elem3,[Tete_Liste|Queue_Liste]) :- (memberchk(Elem1,Tete_Liste),memberchk(Elem2,Tete_Liste),memberchk(Elem3,Tete_Liste) -> true ; estDansListe(Elem1,Elem2,Elem3,Queue_Liste)).

Ca a l'air de marcher.... Mais la fonction appelant ne fonctionne pas comme ca devrait....Arrrgghhh !!

**narcis60floyjo** · 30/04/2011, 19h23

Arf,

j'y suis presque...mais pendant l'exécution de ma fonction de vidage de conflits, ca retourne false, et je ne sais pas pourquoi....

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
 
 
afficher([]).
afficher([T|Q]) :-
    write(T),nl,
    afficher(Q).
 
estDansListe(Elem1,Elem2,Elem3,[Tete_Liste|Queue_Liste]) :- (memberchk(Elem1,Tete_Liste),memberchk(Elem2,Tete_Liste),memberchk(Elem3,Tete_Liste)
												-> true
												; estDansListe(Elem1,Elem2,Elem3,Queue_Liste)).
 
 
vidage([Tete_Liste|Queue_Liste],Prof,Jour,Creneau,Edt_new) :- nl,write('Affichage de Edt_new :'),nl,(length(Edt_new,Taille),Taille>0->afficher(Edt_new);write('vide'),nl),
									write('Tete_Liste à tester : '),write(Tete_Liste),nl,
									write('avant les nth0'),nl,
									nth0(1,Tete_Liste,Prof),nth0(2,Tete_Liste,Jour),nth0(3,Tete_Liste,Creneau),
									write('après les nth0'),nl,
									write('Prof = '),write(Prof),write(' ; '),write('Jour = '),write(Jour),write(' ; '),write('Creneau = '),write(Creneau),nl,
											(estDansListe(Prof,Jour,Creneau,Edt_new)
											-> write('estDansListe ! '),write(Tete_Liste),nl,vidage(Queue_Liste,Prof,Jour,Creneau,Edt_new)
											; ajouter(Tete_Liste,Edt_new,LL),write('Tete_Liste ajoutée : '),write(Tete_Liste),nl,vidage(Queue_Liste,Prof,Jour,Creneau,LL)).
 
 
 
 
emploiDuTemps(Salle,Prof,Jour,Creneau,Cours,Ens,Edt) :- findall([Salle,Prof,Jour,Creneau,Cours,Ens],(salleDispo(Salle,Jour,Creneau),profDispo(Prof,Jour,Creneau),salles(Salle,Cours),moduleEns(Ens,Cours)),Edt),vidage(Edt,Prof,Jour,Creneau,[]).

Et voilà le résultat quand j'appelle emploiDuTemps(...) :

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
 
254 ?- emploiDuTemps(Salle,Prof,Jour,Creneau,Cours,Ens,Edt).
 
Affichage de Edt_new :
vide
Tete_Liste à tester : [stade,prof1,mercredi,14h_16h,entrainement,football]
avant les nth0
après les nth0
Prof = prof1 ; Jour = mercredi ; Creneau = 14h_16h
Tete_Liste ajoutée : [stade,prof1,mercredi,14h_16h,entrainement,football]
 
Affichage de Edt_new :
[stade,prof1,mercredi,14h_16h,entrainement,football]
Tete_Liste à tester : [stade,prof1,mercredi,14h_16h,entrainement,natation]
avant les nth0
après les nth0
Prof = prof1 ; Jour = mercredi ; Creneau = 14h_16h
estDansListe ! [stade,prof1,mercredi,14h_16h,entrainement,natation]
 
Affichage de Edt_new :
[stade,prof1,mercredi,14h_16h,entrainement,football]
Tete_Liste à tester : [stade,prof1,mercredi,14h_16h,match,football]
avant les nth0
après les nth0
Prof = prof1 ; Jour = mercredi ; Creneau = 14h_16h
estDansListe ! [stade,prof1,mercredi,14h_16h,match,football]
 
Affichage de Edt_new :
[stade,prof1,mercredi,14h_16h,entrainement,football]
Tete_Liste à tester : [stade,prof1,vendredi,9h_11h,entrainement,football]
avant les nth0
false.

Et je rappelle le contenu des lignes de Edt :

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
 
stade,prof1,mercredi,14h_16h,entrainement,football
stade,prof1,mercredi,14h_16h,entrainement,natation
stade,prof1,mercredi,14h_16h,match,football
 
stade,prof1,vendredi,9h_11h,entrainement,football
stade,prof1,vendredi,9h_11h,entrainement,natation
stade,prof1,vendredi,9h_11h,match,football
 
bassin,prof2,mercredi,9h_11h,entrainement,football
bassin,prof2,mercredi,9h_11h,entrainement,natation
bassin,prof2,mercredi,9h_11h,competition,natation
 
bassin,prof2,vendredi,14h_16h,entrainement,football
bassin,prof2,vendredi,14h_16h,entrainement,natation
bassin,prof2,vendredi,14h_16h,competition,natation

On voit bien que la fonction de vidage passe bien sur les 3 premières lignes, elle arrive sur la 4ème et là...paf !, ca veut pas récupérer le prof, le jour et le créneau (avec les nth0(...)), et ca me retourne false.

Pourquoi false est-il retourné ?

**narcis60floyjo** · 01/05/2011, 01h27

Bon j'ai réussi à résoudre le problème du nth0.

Voici le code :

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
 
vidage([Tete_Liste|Queue_Liste],Edt_new) :- 
   nl,write('Affichage de Edt_new :'),nl,
  (length(Edt_new,Taille),
   Taille>0->afficher(Edt_new);write('vide'),nl),
   write('Tete_Liste à tester : '),
   write(Tete_Liste),nl,
   write('avant les nth0'),nl,
   nth0(1,Tete_Liste,Prof),
   nth0(2,Tete_Liste,Jour),
   th0(3,Tete_Liste,Creneau),	
   write('après les nth0'),nl,
   write('Prof = '),write(Prof),
   write(' ; '),write('Jour = '),
   write(Jour),write(' ; '),
   write('Creneau = '),
   write(Creneau),nl,
  (estDansListe(Prof,Jour,Creneau,Edt_new) -> 
    write('estDansListe !),
    write(Tete_Liste),nl,
    vidage(Queue_Liste,Edt_new) ;
    ajouter(Tete_Liste,Edt_new,LL),
    write('Tete_Liste ajoutée : '),
    write(Tete_Liste),nl,
    vidage(Queue_Liste,LL)).

Génération emploi du temps à partir de faits

Prolog

Discussions similaires

Partager

Partager