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 :

Algorithme des K plus courts chemins dans un graphe dirigé


Sujet :

Algorithmes et structures de données

  1. #1
    Membre confirmé
    Avatar de geforce
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Janvier 2010
    Messages
    1 055
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Canada

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Janvier 2010
    Messages : 1 055
    Points : 559
    Points
    559
    Par défaut Algorithme des K plus courts chemins dans un graphe dirigé
    Bonjour à tous,

    J'ai cherché des exemples de code source Java idéalement, qui fait l'implémentation, la plus simple possible des algorithmes qui permet de détermine les K plus court chemin dans un graphe dirigé, pour les cas suivant :
    1. Algorithmes de FordBellman
    2. Algorithmes de dijkstra
    3. Algorithmes de floydWarshall
    4. S'il y d'autres qui sont plus performant (temps d'exécution et complexité) je suis preneurs

    .

    NB: Mes recherche en permise de trouver des exemples correctement exploitable pour :
    dijkstra : http://www.vogella.com/tutorials/Jav...a/article.html
    floydWarshall : http://javascool.gforge.inria.fr/?pa..../exercice.htm

    Merci pour toutes vos suggestions et propositions

  2. #2
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 410
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Mai 2002
    Messages : 3 410
    Points : 5 801
    Points
    5 801
    Par défaut
    salut

    il y a aussi l'algorithme A* très utilisé dans les jeux vidéo
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  3. #3
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Août 2008
    Messages
    26 609
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2008
    Messages : 26 609
    Points : 188 580
    Points
    188 580
    Par défaut


    Les algorithmes que tu proposes sont parmi les plus efficaces en restant exacts (liste plus complète : https://en.wikipedia.org/wiki/Shorte...shortest_paths) : A* est une approche heuristique à la recherche de chemin (il estime la distance encore à parcourir entre un nœud et la destination sans la calculer). Pour améliorer les temps de calcul, en fonction de la forme du graphe, tu peux encore utiliser une représentation hiérarchique du graphe (pour trouver le plus court chemin entre ta rue et un hôtel à Zagreb, tu ne considères pas tous les petits chemins, plutôt le chemin jusqu'à une autoroute, puis le chemin en restant sur autoroute jusqu'à proximité de ta destination). Bien évidemment, gagner en temps complexifie le code.
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  4. #4
    Membre confirmé
    Avatar de geforce
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Janvier 2010
    Messages
    1 055
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Canada

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Janvier 2010
    Messages : 1 055
    Points : 559
    Points
    559
    Par défaut
    OK, merci pour vos réponses.

    Je c'est pour un grand graphe il peut avoir un problème combinatoire (peu prendre grand temps) pour un résultat

    Donc je me demande s'il y a une solution pour réduire ce problème ? (Idéalement une proposition avec la méthode Branche and bound) sinon tout autre suggestion et proposition serai la bienvenu,

    NB: si possible des exemples avec du code en java serai appréciable

  5. #5
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Août 2008
    Messages
    26 609
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2008
    Messages : 26 609
    Points : 188 580
    Points
    188 580
    Par défaut
    Citation Envoyé par geforce Voir le message
    (Idéalement une proposition avec la méthode Branche and bound)
    Une formulation en nombres entiers ? Voir https://en.wikipedia.org/wiki/Shorte...ng_formulation : d'abord résoudre ce programme (par séparation et évaluation, si tu le souhaites), puis explorer toutes les solutions de même coût pour les K chemins (puis ajouter une contrainte imposant un coût strictement supérieur aux meilleurs chemins pour aller chercher d'autres chemins pour atteindre les K, mais des chemins suboptimaux — ça peut très bien fonctionner avec des coûts entiers, nettement moins bien avec des réels). Dans ce cas, tu es pile poil dans du "classique" (sauf que peu de gens implémentent des algorithmes de résolution, c'est déjà très bien fait par d'autres).

    Citation Envoyé par geforce Voir le message
    Donc je me demande s'il y a une solution pour réduire ce problème ?
    Tu n'as pas d'explosion combinatoire, puisque les algorithmes sont polynomiaux (si c'est bien ça la question). Par contre, ça peut prendre beaucoup de temps (d'où les solutions heuristiques à la A* ou HPA*).

    En y réfléchissant un peu (mais pas trop), A* implémente une forme de séparation et évaluation : partant de l'origine, tu choisis une branche à continuer en fonction de la distance (euclidienne) qui reste à parcourir après cette branche jusqu'à la destination ; ensuite, tu retires la branche évaluée et tu ajoutes les nœuds nouvellement accessibles dans l'ensemble des nœuds actifs.
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  6. #6
    Membre confirmé
    Avatar de geforce
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Janvier 2010
    Messages
    1 055
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Canada

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Janvier 2010
    Messages : 1 055
    Points : 559
    Points
    559
    Par défaut
    Bonjour dourouc05,

    Je n’ai pas très bien compris ta 1er réponse tu parles d'un exemple de séparation évaluation avec des nombre entier ? Si c'est le cas peu tu me faire un déroulement que je puisse appliquer par la suit avec un algorithme de parcours de graphe?

    Puis pour la 2em, je crois que c'est moi qui a fait une erreur (oui c'est vrais que l’algorithme peu prendre beaucoup de temps) amis serai plus problématique NP-complet.

    Merci

  7. #7
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Août 2008
    Messages
    26 609
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2008
    Messages : 26 609
    Points : 188 580
    Points
    188 580
    Par défaut
    J'aurais tendance à penser l'approche par nombres entiers indépendante du parcours de graphe : la traversée est modélisée sous la forme d'(in)équations au lieu d'opérations directement sur le graphe (le parcours consiste à créer ces équations).
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

Discussions similaires

  1. Plus court chemin dans un graphe
    Par kader58 dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 26/04/2015, 11h19
  2. Calcul de plus court chemin dans un graphe
    Par Elmilouse dans le forum Prolog
    Réponses: 6
    Dernier message: 21/03/2010, 21h26
  3. Plus court chemin dans un graphe avec contraintes
    Par tomjr dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 30/12/2009, 13h36
  4. trouver le plus court chemin dans un graphe
    Par buggen25 dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 15/08/2008, 18h34
  5. 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, 01h32

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