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.

mer. 10 novembre 2010, 21h42
Gregory Adam
atoutfox.public.association

Re: Récursivité et stack space à nouveau


Luc,

A mon avis - la programmation linéaire est le moyen le plus rapide pour y arriver. J’ignore combien de temps cela prendra avec 100 eleves.
Sache que le temps max de recherche est 2^31 ms ou 2^31/1000/86400 ou 24.86 jours – apres le prog se termine et tu as une solution non-optimale

Un avantage de cette programmation linéaire est que peux ajouter des contraintes – style – Prof Jean veut avoir mercredi apres-midi libre

Le probleme que tu avais pour transformer ton recursif en iteratif est la taille de l’etat (state)
Quand on traverse un arbre binaire la taille de l’etat (state) qu’on met sur le stack n’est pas enorme – juste la position actuelle dans l’arbre (et dans un cas la direction)

Dans ton cas, la taille de d’etat (state) est confortable ( 1 tableau par eleve (seances planifiees) + 1 tableau par eleves (seances a planifier) + 1 tableau par instructeur (plages + nombre d’eleves par plage)

J’y ai reflechi – et je crois que c’est faisable. Mais le nombre d’etats (state) est tellement immense qu’on devra les mettre sur disque (= pas garder en memoire). J’ignore si le nombre records possible dans un curseur sera suffisant

Si tu veux le resoudre en regardant toutes les solutions et d’une maniere iterative tu entres dans le domaine de l’intelligence artificielle (mais tu ne fais que entrouvrir la porte)

Une possibilite est d’essayer d’utiliser les cpu presents (j’ai 8 cores)

Un jour – si j;ai le temps et l’envie – j’essayerai – peut-etre


ps: Si tu veux eviter les api – il y a moyen (je crois) de mettre le probleme dans un fichier texte, le resoudre avec glpsol.exe – mais apres faut décortiquer le resultat de glpsol




Gregory

"luc" <luc.gilot@limoog.net> wrote in message news:ibep45$2vpo$1@news.niouzes.net...
Bon, j'ai mis du temps à répondre mais je suis impressionné et je n'osais pas rentrer dedans

Depuis des années qu'il me manquait un point d'entrée pour la programmation linéaire (et que je n'avais pas le courage de m'y mettre), là je n'ai plus d'excuses.

Bref, c'est pas mon anniversaire mais je te remercie Grégory. Il va me falloir du temps pour décortiquer ca et y mettre mes vraies contraintes mais la base est là.

A dans quelques mois pour la conclusion...

Luc
"Gregory Adam" <GregoryAdam@NoWhere.com> a écrit dans le message de news: ib3rl9$1thd$1@news.niouzes.net...
Luc,


------------------------------------------------------------------------------

Intro

Si tu commences a replir – en supposant qu’il y a 100 eleves et 10 activites, tu dois choisir 10 eleves des 100 pour la premiere seance
Nombres de possibilites
= Comb(100, 10)
= 100! / ( 10! * (100-10)!)
= 100 * 99 * 98 * 97 * 96 * 95 * 94 * 93 * 92 * 91 / ( 1* 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 )
= 17,310,309,456,440

Et la, tu n’a que commence

Meme si tu peux remplir le tout en une minute – cela prendra beaucoup de temps – 1 ou 2 mois ne suffiront pas a mon avis
Meme si tu prends un langage compile (C#, C++) qui va au moins 10 fois plus vite que foxpro

------------------------------------------------------------------------------
J’ai pris une autre approche – celle de la programmation lineaire

Je mets tout dans un model. S’il y a une solution optimale on le voit, si pas de solution optimale il remplit le max possible

Un avantage de cette approche est que tu peux modifier les contraintes ( relaxer 1 séance de la meme dicipline par jour a eg 2)

9 secondes pour 2 eleves
11 min pour 6 eleves
40 min pour 10 eleves

------------------------------------------------------------------------------
Je joins quelque programmes

(1) SchemaProblem qui cree les curseurs (Pupil, Activity, et PupilSchema = Activites demandees pour les eleves)
Tu peux modifier GetPupilCursor() qui cree les eleves
et aussi GetActivityCursor() et GetPupilSchemaCursor()

(2) SchemaSolver lp (prototype). Qui contient la classe pour mettre le tout dans un model lineaire et afficher le result par apres
un exemple : = SchemaSolver lp Example(.t.)

(3) GlpkProblem + GlpkProblem.h
que j’avais deja et que j’ai du modifier
ceci ulilise GLPK http://www.gnu.org/software/glpk/

(4) glpk.dll – tu mettras ou tu veux – faut modifier GlpkProblem : InstallDir = 'd:\tmp\glpk'
les api de glpk.dll tu trouveras ici http://www.mai.liu.se/~kahol/kurser/all/glpk.pdf Regarde pages 13 et 14

(5) libtddl3.dll – a mettre dans le repertoire d’ou tu execute ton prog ( = curdir())

(6) zlib1.dll - idem libtddl3.dll



Gregory

"Gregory Adam" <GregoryAdam@NoWhere.com> a écrit dans le message de news: ib3rl9$1thd$1@news.niouzes.net...
Luc,


------------------------------------------------------------------------------

Intro

Si tu commences a replir – en supposant qu’il y a 100 eleves et 10 activites, tu dois choisir 10 eleves des 100 pour la premiere seance
Nombres de possibilites
= Comb(100, 10)
= 100! / ( 10! * (100-10)!)
= 100 * 99 * 98 * 97 * 96 * 95 * 94 * 93 * 92 * 91 / ( 1* 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 )
= 17,310,309,456,440

Et la, tu n’a que commence

Meme si tu peux remplir le tout en une minute – cela prendra beaucoup de temps – 1 ou 2 mois ne suffiront pas a mon avis
Meme si tu prends un langage compile (C#, C++) qui va au moins 10 fois plus vite que foxpro

------------------------------------------------------------------------------
J’ai pris une autre approche – celle de la programmation lineaire

Je mets tout dans un model. S’il y a une solution optimale on le voit, si pas de solution optimale il remplit le max possible

Un avantage de cette approche est que tu peux modifier les contraintes ( relaxer 1 séance de la meme dicipline par jour a eg 2)

9 secondes pour 2 eleves
11 min pour 6 eleves
40 min pour 10 eleves

------------------------------------------------------------------------------
Je joins quelque programmes

(1) SchemaProblem qui cree les curseurs (Pupil, Activity, et PupilSchema = Activites demandees pour les eleves)
Tu peux modifier GetPupilCursor() qui cree les eleves
et aussi GetActivityCursor() et GetPupilSchemaCursor()

(2) SchemaSolver lp (prototype). Qui contient la classe pour mettre le tout dans un model lineaire et afficher le result par apres
un exemple : = SchemaSolver lp Example(.t.)

(3) GlpkProblem + GlpkProblem.h
que j’avais deja et que j’ai du modifier
ceci ulilise GLPK http://www.gnu.org/software/glpk/

(4) glpk.dll – tu mettras ou tu veux – faut modifier GlpkProblem : InstallDir = 'd:\tmp\glpk'
les api de glpk.dll tu trouveras ici http://www.mai.liu.se/~kahol/kurser/all/glpk.pdf Regarde pages 13 et 14

(5) libtddl3.dll – a mettre dans le repertoire d’ou tu execute ton prog ( = curdir())

(6) zlib1.dll - idem libtddl3.dll



Gregory

Permalink : http://www.atoutfox.org/nntp.asp?ID=0000004350
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