ATOUTFOX
COMMUNAUTÉ FRANCOPHONE DES PROFESSIONNELS FOXPRO
Visual FoxPro : le développement durable

Forum AtoutFox : Récursivité et stack space à nouveau   

Sujet

rss Flux RSS des derniers messages

Vous devez vous identifier pour pouvoir poser une question ou répondre.

mer. 03 novembre 2010, 20h53
luc Gilot
atoutfox.public.association

Récursivité et stack space à nouveau

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=0000004321
20 286 messages dans le forum • Liste complète des messages

www.atoutfox.org - Site de la Communauté Francophone des Professionnels FoxPro - v3.4.0 - © 2004-2026.
Cette page est générée par un composant COM+ développé en Visual FoxPro 9.0-SP2-HF3