Implémentation des nœuds dans l'algorithme A*

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:

---

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 !

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:

---

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:

---

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:

---

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 };;

---

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.

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

Citation:

---

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