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

Forum AtoutFox : Re: 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.

jeu. 04 novembre 2010, 08h25
OlivierH
atoutfox.public.association

Re: Récursivité et stack space à nouveau

Pourquoi passes tu par un DO et non pas un objet VCX ?

monCalcul = NewObject("Calcul","Class.vcx")
Boucle
* tes tests
monCalcul.Test()
Fin boucle
monCalcul = null

Olivier

Le 03/11/10 20:53, luc Gilot a écrit :
> 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=0000004324
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