Discussion :

[chlab]

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 :

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.

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 !

donc si il était possible d'utiliser par exemple une liste L d'appels récursifs, faire

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

 

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.).

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 !

[LLB]

Je ne suis pas sûr d'avoir compris toute la question, mais si tu veux faire un parcours en largeur, utilise plutôt une file.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
let q = Queue.create() in
Queue.push premier_element q;
while not (Queue.is_empty q) do
    let elt = Queue.pop q in
    (* ... Queue.push ... *)
done

[chlab]

c'est un peu ça l'idée. Je connaissais pas les Queues ! Mais si j'ai bien lu la doc, on ne peut manipuler que la fin d'une Queue et pas la tête?

En fait il faudrait un type qui manipule à la fois les piles FIFO (file d'attentes) et LIFO (listes classiques en caml), qui permette de faire qqchose comme ça, en mélangeant les Queue et les List :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
let rec fonctiontest a t tmax L ()= match (a,t) with
	| (a,t) when t=tmax (*ou si une certaine condition sur a est vérifiée*) -> print a
	| (a,t) when a=10 -> Queue.add (fonctiontest 1 (t+1) tmax L) L; let ap = Queue.take !L in ap();
        | (a,t) -> L := (fonctiontest (a+1) t tmax) :: !L ;
                      L := (fonctiontest a (t+1) tmax) :: !L ;
                      let ap = Queue.take !L in ap ()
;;

bon c'est un peu bizarre comme programme, mais j'espère avoir été un peu plus clair ... en fait je stocke les appels récursifs ap = (fonctiontest a t tmax L) et je les execute avec ap(), à priori ça devrait marcher.

Existe-t-il des outils pour manipuler ce genre de files? Ou un autre type, une sorte d'hybride de Queue et de Liste ?

[gorgonite]

une liste doublement chaînée alors ?
http://bleu.west.spy.net/~dustin/pro...inkedlist.html