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
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2019
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : août 2019
    Messages : 2
    Points : 4
    Points
    4

    Par défaut 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
    Avatar de SpiceGuid
    Homme Profil pro
    Inscrit en
    juin 2007
    Messages
    1 694
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : juin 2007
    Messages : 1 694
    Points : 2 960
    Points
    2 960

    Par défaut 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
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2019
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : août 2019
    Messages : 2
    Points : 4
    Points
    4

    Par défaut

    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
    Avatar de SpiceGuid
    Homme Profil pro
    Inscrit en
    juin 2007
    Messages
    1 694
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : juin 2007
    Messages : 1 694
    Points : 2 960
    Points
    2 960

    Par défaut

    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.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Implémenter des API dans ASP.Net
    Par ines1985 dans le forum Services Web
    Réponses: 1
    Dernier message: 10/01/2011, 11h06
  2. Réponses: 2
    Dernier message: 13/02/2010, 16h45
  3. l'utilisation des shémas dans l'algorithme génétique
    Par mayouta dans le forum Intelligence artificielle
    Réponses: 0
    Dernier message: 19/02/2009, 01h40
  4. Réponses: 4
    Dernier message: 04/12/2008, 20h46
  5. Réponses: 1
    Dernier message: 26/06/2006, 11h33

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo