Discussion :

[Wanderes]

Bonjour,

J'essaye en ce moment de coder l'algorithme A* sous Ocaml. Je pense avoir bien saisi le concept général de l'algorithme et j'aimerais donc passer à son implémentation. De tous les algorithmes / programmes que j'ai vu aucun n'était sous Ocaml d'où ma venue.

En fait je bloque à l'implémentation des Noeuds. J'ai essayé de refaire comme sur les autres algorithmes c'est à dire :

Code :

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

type noeud = {x : int; y: int; mutable depart : int; mutable fin : int; mutable parent : noeud};;

Ce qui me rassure c'est qu'une telle commande semble marcher (sans erreur en tout cas) alors que le type nœud s'appelle lui-même. Toutefois il me faut bien un premier nœud et je ne vois pas comment le définir, n'y a-t'il pas moyen de créer une sorte d'exception (un Noeud 0) ? J'ai bien essayé de magouiller un peu mais ça ne fonctionne guère...
Je vais continuer à chercher de mon côté (j'espère que c'est toutefois possible) mais si vous pouviez m'aider je vous en serais très reconnaissant.

Bonne journée !

[SpiceGuid]

Tous les types sont implicitement rec c'est pourquoi ils peuvent s'appeler eux-mêmes.
Dans le cas contraire on utilise type nonrec ....

Je ne connais que 3 réponses pratiques à ta question.
N'hésitez pas à en proposer une(des) autre(s).

Ou bien tu crées toi-même un noeud nul à l'aide d'une valeur récursive :

Code ocaml :

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

1
2
let rec noeud_nul = 
  {x=0;y=0;depart=0;fin=0;parent=noeud_nul};;

Ou bien tu assumes le noeud nul dans le type lui-même à l'aide du type option :

Code :

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

1
2
3
4
5
6
7
type noeud =
    {
    x : int; y: int;
    mutable depart : int;
    mutable fin : int;
    mutable parent : noeud option
    };;

Ou bien tu assumes le noeud nul à l'aide d'un type inductif (code pas testé!) :

Code :

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

1
2
3
4
5
6
7
8
9
type noeud =
  | Noeud_nul
  | Noeud of
    {
    x : int; y: int;
    mutable depart : int;
    mutable fin : int;
    mutable parent : noeud
    };;

[Wanderes]

Merci pour votre réponse.

J'ai testé les 3 méthodes et en effet elles conviennent toutes. Je vais toutefois opter pour la première pour le moment car sinon j'aurais sans doute des exceptions à gérer dans mon programme.
Concernant la troisième méthode c'est une sorte de somme avec un enregistrement dedans finalement ?

En tout cas encore merci je vais mettre en résolu.

[SpiceGuid]

Si tu optes pour la 1ère méthode tu devras faire des comparaisons du genre if n != noeud_nul then (comparaison physique) plutôt que if n <> noeud_nul then (comparaison profonde qui risque bien de boucler à l'infini).

Concernant la troisième méthode c'est une sorte de somme avec un enregistrement dedans finalement ?

Tout à fait. C'est un raccourci (pas de déclaration du type enregistrement) et aussi une optimisation mémoire, nouveauté depuis OCaml 4.03 au pifomètre