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