jeu. 04 novembre 2010, 18h54
Gregory Adam
atoutfox.public.association
Re: Récursivité et stack space à nouveau
Luc,
Pour voir si je comprends bien
Il y a dix instructeurs (ou prof) - math, sport, histoire, ...
Chaque instructeur a un local qu'il occupe pendant toute une semaine - c'est
pour simplifier le probleme
Une journee d'un instructeur comprends quatre seances
Un instructeur a donc 4 * 5 seances dans la semaine
Un instructeur est disponible toute la semaine
Il y 10 locaux - ou classes
Une séance a max 10 eleves
Le probleme est de savoir ou et quand mettre les eleves, sachant que
- un eleve peut rencontrer l'instructeur max 1 fois/jour
- autres contraintes specifiques a un eleve: donc un eleve a un objectif de
seances a suivre par semaine. exemple 3 math, 5 francais, 4 anglais, ... =
20
(1) As-tu besoin de toutes les possibilites ? - parce que cela risque de
prendre du temps - ou
(2) Est-tu content avec une 'meilleure' solution ou te faut-il toutes les
meilleures solutions ?
Gregory
__
"luc Gilot" wrote in message news:iasek1$nc0$1@news.niouzes.net...
Ma question a suscité un certain intérêt (et je remercie les répondeurs et
en particulier Gregory pour sa contribution, dans laquelle je n'ai
malheureusement pas vraiement trouvé mon bonheur).
Je dois donc m'expliquer un peu plus clairement : désolé si c'est un peu
long.
Le problème : dans un contxte éducatif avec prise en charge individuelle, il
s'agit de répartir des élèves dans des séances d'activité. Chaque journée
est divisée en quatre plages horaires. Sur chaque plage sont prépositionnées
des séances d'activité (maths, sport, ..., une dizaine environ). Le jeu est
de dire quels élèves participeront à chaque séance, sachant que :
* l'emploi du temps de chaque élève doit être plein (pas de plage horaire où
on ne l'a mis nulle part)
* chaque séance a une capacité limitée (disons, 10 élèves pour simplifier)
* chaque élève a des objectifs dans chaque discipline (certains font plus de
maths que d'autres, certains ne peuvent pas faire de sport, ...)
* certains élèves sont incompatiles entre eux (cause baston ou papouiles, ou
autres)
* un élève ne peut pas avoir plus d'une séance de la même discipline le même
jour (mais en réalité, toutes les séances n'ont pas la même durée :
certaines occupent plusieurs plages horaires) ;
* etc.
Il y a environ 100 élèves, 20 plages horaires, 10 possibilités sur chaque
plage. Le nombre de "solutions" possibles est considérable (je ne suis pas
très fort en dénombrements, mais ca ressemble à 100 * 11 puissance 20 (11
car il faut envisager qu'on ne trouve pas de séance pour l'élève sur un
créneau donné)).
J'ai un algorithme de calcul (un peu complexe et je ne le détaille pas ici),
qui essaie de trouver la "meilleure solution". Evidemment, les contraintes
de mon client sont trop fortes et il n'y a pas de "bonne" solution. Ce que
je souhaite, c'est de parcourir TOUTES les solutions possibles pour bien
montrer qu'aucune n'est (beaucoup) plus satisfaisante que celle de mon
calcul (ou au contraire, de me faire revoir ma copie et de reprendre
l'algorithme).
Bref, parcourir toutes les solutions revient à parcourir un arbre binaire.
Pour un élève et une séance, il n'y a que deux possibilités : soit l'élève
participe à la séance, soit non.
Je dispose donc d'une table des élèves-séances dont la structure minimale
est la suivante :
iId_Eleve I
iId_Séance I
lParticipe L
lExclusDuCalcul L
Cette table a 20 * 10 * 100 = 20000 lignes.
Voici l'algo récursif pour parcourir l'arbre :
Début UnParcours
Chercher le premier élève-séance possible (ne participe pas, et la
participation ne heurterait pas les contraintes indiquées ci-dessus) et non
exclus
Si pas trouvé
Le calcul est fini : mémoriser son résultat
Sortir
Fin Si
Mettre lParticipe à .T.
Faire UnParcours (parcourt toutes les branches de l'arbre dans
lesquelles l'élève participe à la séance)
Mettre lParticipe à .F.
Mettre lExclusDuCalcul à .T.
Faire UnParcours (parcourt toutes les branches de l'arbre dans
lesquelles l'élève NE participe PAS à la séance)
Mettre lExclusDuCalcul à .F.
Fin UnParcours
Ca fonctionne parfaitement bien pour 10 élèves, mais pour 100 élèves on
dépasse le nombre de DO imbriqués (stack space)...
Finalement, je n'ai pas réussi à mettre au point correctement la duplication
du code qui était censée résoudre le problème de stack space (on parcourt
plusieurs fois chaque branche). Comme je n'ai aucune idée de comment
implanter ca en itératif, je suis sec...
Ce problème n'est pas crucial pour moi puisque le parcours exhaustif de
l'arbre n'est pas une solution opérationnelle (il faudra plusieurs semaines
pour que la bécane mouline ce calcul), mais intellectuellement ca me
pique...
Merci de votre attention et à plus
Luc
Permalink : http://www.atoutfox.org/nntp.asp?ID=0000004327