Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Candidat au Club
    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 :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 !

  2. #2
    Membre émérite
    Ce fameux noeud nul
    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
        };;
    Du même auteur: le cours OCaml, le dernier article publié, le blog dvp et le jeu vidéo.
    Avant de poser une question je lis les règles du forum.

  3. #3
    Candidat au Club
    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.

  4. #4
    Membre émérite
    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
    Du même auteur: le cours OCaml, le dernier article publié, le blog dvp et le jeu vidéo.
    Avant de poser une question je lis les règles du forum.