IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
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

Algorithmes et structures de données Discussion :

Le plus court chemin


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Homme Profil pro
    .
    Inscrit en
    Décembre 2009
    Messages
    35
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Fidji

    Informations professionnelles :
    Activité : .

    Informations forums :
    Inscription : Décembre 2009
    Messages : 35
    Par défaut Le plus court chemin
    Bonjour

    Je ne sais pas quel algo choisir, je dois effectivement donner le plus cours chemin entre deux sommets dans un graphe. Les arrêtes non pas de valeur de longueur.

    L'algorithme de Dijkstra n'a pas l'air d'être bon pour ce genre de graphe et l'algorithme A* me semble peu rapide dans certain cas.

    Alors lequel choisir ? en connaissez-vous d'autre ?
    Merci

  2. #2
    Membre éprouvé Avatar de Bucketpc
    Inscrit en
    Août 2008
    Messages
    98
    Détails du profil
    Informations personnelles :
    Âge : 38

    Informations forums :
    Inscription : Août 2008
    Messages : 98
    Par défaut
    Bonjour,

    Si vous dites que le A* est un peu lent, alors je dirai que votre problème est NP-Complet (voir le signification sur le net).

    Pour résoudre le problème, il faut utiliser des méthodes méta-heuristiques tel que le Algorithmes génétiques, recherche dispersée, colonies de fourmis.

  3. #3
    Membre très actif
    Inscrit en
    Décembre 2009
    Messages
    123
    Détails du profil
    Informations forums :
    Inscription : Décembre 2009
    Messages : 123
    Par défaut
    Graphe non valué, recherche de chamin => problème NP-Complet

    Je pense plutôt qu'il s'agit d'un problème de taille d'instances, mais juste avec les infos initiales on ne peut pas t'aider.

  4. #4
    Membre éprouvé Avatar de Bucketpc
    Inscrit en
    Août 2008
    Messages
    98
    Détails du profil
    Informations personnelles :
    Âge : 38

    Informations forums :
    Inscription : Août 2008
    Messages : 98
    Par défaut
    Citation Envoyé par IDontLikeYou Voir le message
    Graphe non valué, recherche de chamin => problème NP-Complet

    Je pense plutôt qu'il s'agit d'un problème de taille d'instances, mais juste avec les infos initiales on ne peut pas t'aider.
    Le titre c'est: Le plus court chemin, et non pas un chemin quelconque. s'il s'agit seulement de trouver le chemin alors A* sera suffisant et rapide.

  5. #5
    Membre très actif
    Inscrit en
    Décembre 2009
    Messages
    123
    Détails du profil
    Informations forums :
    Inscription : Décembre 2009
    Messages : 123
    Par défaut
    Citation Envoyé par Bucketpc Voir le message
    Le titre c'est: Le plus court chemin, et non pas un chemin quelconque. s'il s'agit seulement de trouver le chemin alors A* sera suffisant et rapide.
    Je suis bien d'accord, d'où le fait que je dise qu'on manque d'infos. Par contre je ne vois toujours pas ce que le NP-Complet vient faire là dedans ...

    Edit : d'ailleurs sur un graphe non valué au pire tu tapes un parcours complet en O(nm), donc ce doit forcément être un problème de taille d'instance.

  6. #6
    Membre averti
    Homme Profil pro
    .
    Inscrit en
    Décembre 2009
    Messages
    35
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Fidji

    Informations professionnelles :
    Activité : .

    Informations forums :
    Inscription : Décembre 2009
    Messages : 35
    Par défaut
    D'apres ce que j'ai vu (wikipedia), A* peine a trouver le chemin dans cette situation:



    Apres je ne vois pas quoi donner en plus comme precision

  7. #7
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par Damoun Voir le message
    L'algorithme de Dijkstra n'a pas l'air d'être bon pour ce genre de graphe
    ah ? pourquoi ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Discussions similaires

  1. Calcul de plus court chemin dans un graphe
    Par Elmilouse dans le forum Prolog
    Réponses: 6
    Dernier message: 21/03/2010, 20h26
  2. Plus court chemin - graphe NON orienté et pondéré
    Par Nicodemus dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 14/03/2006, 15h32
  3. N plus courts chemin dans un graphe
    Par MLK jr dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 13/03/2006, 00h32
  4. [algo] plus courts chemins (au pluriel !!)
    Par ADSL[fx] dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 18/01/2006, 14h40
  5. Réponses: 2
    Dernier message: 21/03/2004, 18h57

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