Bonjour,
est-ce possible en ocaml, dans une fonction récursive, de travailler sur l'ordre des appels récursifs? Par exemple avec une liste (doublement chaînée ?), où l'on placerai l'appel suivant en tête, ou à la fin de la queue, ou ... ?
J'en aurai besoin pour un programme d'optimisation d'un ordonnancement :
L'idée est qu'on regarde à chaque temps toutes les possibilités, tant qu'on a pas trouvé un ordonnancement satisfaisant.
Par exemple (no comment!) pour un jeu de stratégie dont on voudrait trouver l'ordonnancement de tâches qui donnent 3 ouvriers, 2 casernes, 3 cavaliers le plus vite possible, mon prog ferai pour l'instant :
histoire de vraiment tout tester. Ca fait certes beaucoup d'appels. Mais on peut déjà limiter un peu la casse. Si on visualise un arbre d'appels récursifs (avec en profondeur le temps), la solution recherchée est le 1er ordonnancement valide rencontré lorsqu'on parcours l'arbre en largeur. Or la fonction présentée ci-dessus fait parcourir l'arbre en profondeur !
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6 au temps t, avec un ordonnancement A : - si j'ajoute la construction du i-ème bâtiment à A (A' := bat(i) :: A) est-ce que l'objectif est atteint ? si oui afficher A - sinon tester au temps t, avec le (i+1)-ème bâtiment, et l'ordonnancement A' - sinon tester au temps t, avec le (i+1)-ème bâtiment, et l'ordonnancement A - quand tous les bâtiments et unités sont testés, aller au temps t+1 avec le 1er bâtiment.
donc si il était possible d'utiliser par exemple une liste L d'appels récursifs, faire
Normalement ceci devrait résoudre le problème (sauf erreur de ma part et ça m'emmerderai bien d'avoir écrit tout ça pour rien.).
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9 au temps t, avec un ordonnancement A : - si j'ajoute la construction du i-ème bâtiment à A (A' := bat(i) :: A) est-ce que l'objectif est atteint ? si oui afficher A - sinon ajouter en tête de L [ tester au temps t, avec le (i+1)-ème bâtiment, et l'ordonnancement A' ] - sinon ajouter en tête de L [ tester au temps t, avec le (i+1)-ème bâtiment, et l'ordonnancement A ] - si tous les bâtiments et unités sont testés, ajouter en queue de L [ au temps t+1 avec le 1er bâtiment et A ] exécuter List.hd L
Savez vous comment procéder pour manipuler de tels objets, c.a.d. les appels récursifs eux-même? (ça doit être faisable en créant un type spécial et en concaténant tout au passage, mais je demande aussi ça pour la culture G).
Merci de votre aide !
Partager