1. #1
    Candidat au Club
    Homme Profil pro
    Architecte matériel
    Inscrit en
    février 2016
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Aveyron (Midi Pyrénées)

    Informations professionnelles :
    Activité : Architecte matériel

    Informations forums :
    Inscription : février 2016
    Messages : 6
    Points : 3
    Points
    3

    Par défaut Recherche du chemin le moins coûteux avec contraintes particulières

    Bonjour !

    Je suis confronté au problème suivant :

    J'ai N sommets numérotés de 1 à N, on associe à chaque couple de sommets un coût, c'est le coût du chemin les reliant. L'objectif est de trouver le chemin de longueur N passant par N sommets distincts tel que ce chemin soit le moins coûteux possible.
    Jusque là il me semble -je suis novice en informatique- que plusieurs algorithmes permettent de répondre au problème, par exemple l'algorithme de Bellman-Ford
    Sauf que j'ai une contrainte supplémentaire :
    A chaque étape d'un chemin de longueur N on a un certain nombre de sommets accessibles et une fois qu'on a choisi un sommet alors celui-ci n'est plus accessible pour la suite puisqu'on veut passer par N sommets distincts. En fait c'est comme si le graphe évoluait pendant la simulation

    Par exemple, pour N=5, on peut imaginer la liste suivante : [[1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5], [2, 3, 4, 5], [3, 4, 5]] donnant, pour chaque étape, la liste des sommets disponibles (pour l'étape 1 on ne peut choisir que parmi les sommets 1,2,3 , pour l'étape 2 on choisit parmi 1,2,3,4 en enlevant le sommet choisi à l'étape 1 et ainsi de suite...)

    Pour résoudre ça, je vous avoue que je suis légèrement à court d'idées
    Je pense que mon problème n'est pas non plus très original donc j'aimerais savoir si il existe des algorithmes pouvant le résoudre (sans énumérer toutes les solutions bien sûr). Ou alors, est-il possible d'adapter l'algorithme de Bellman-Ford à mon problème ?
    Je suis également preneur de la moindre idée

    Merci beaucoup pour votre aide !

  2. #2
    Membre régulier
    Profil pro
    Inscrit en
    septembre 2006
    Messages
    101
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France

    Informations forums :
    Inscription : septembre 2006
    Messages : 101
    Points : 108
    Points
    108

    Par défaut

    Bonjour,

    Je vous suggère de vous renseigner sur les graphes hamiltoniens.

    Cordialement.

  3. #3
    Candidat au Club
    Homme Profil pro
    Architecte matériel
    Inscrit en
    février 2016
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Aveyron (Midi Pyrénées)

    Informations professionnelles :
    Activité : Architecte matériel

    Informations forums :
    Inscription : février 2016
    Messages : 6
    Points : 3
    Points
    3

    Par défaut

    Bonjour, merci pour le lien je vais aller voir de ce côté là !
    Je me suis également pas mal renseigné sur le problème du voyageur de commerce, j'ai vu qu'il pouvait être approché par des algorithmes génétiques, j'ai essayé d'écrire un tel algorithme hier. Le souci c'est que, à part pour les cas où on peut dénombrer toutes les solutions, je ne vois pas comment évaluer la performance de l'algorithme. Certes il sort un résultat mais comment estimer à quel point ce résultat est proche de l'optimum ?

  4. #4
    Membre régulier
    Profil pro
    Inscrit en
    septembre 2006
    Messages
    101
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France

    Informations forums :
    Inscription : septembre 2006
    Messages : 101
    Points : 108
    Points
    108

    Par défaut

    Bonjour,

    Pour évaluer, une solution, il faut calculer une borne inférieure.

    Vous trouverez diverses ressources sur ce problème ici.

    Cordialement

  5. #5
    Responsable Qt


    Avatar de dourouc05
    Homme Profil pro
    Doctorant
    Inscrit en
    août 2008
    Messages
    22 084
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Doctorant
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 22 084
    Points : 117 694
    Points
    117 694

    Par défaut

    La meilleure estimation de la distance à l'optimum reste toujours de calculer cette solution optimale, ce qui est très souvent à portée avec des techniques d'optimisation mathématique ou de programmation par contraintes (pas vraiment triviales pour de gros problèmes).

    Sinon, pour la question d'origine, non, Bellman-Ford ne permet pas de résoudre ce type de problème : c'est bien un voyageur de commerce complet (pas le meilleur chemin entre deux points, mais le meilleur cycle dans le graphe). Je ne suis pas bien sûr de comprendre ta contrainte supplémentaire : tu veux bien dire que (pour prendre les noms utilisés pour le TSP) tu dois passer une et une seule fois dans chaque ville ? C'est justement le principe du TSP .

    Si tu ne veux pas trop coder, regarde du côté de Concorde. Sinon, http://laurent-ott.developpez.com/tu...el-vba-tome-3/ est une bonne introduction au domaine "avec les mains".
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions) ? Contactez-moi par MP.

    Nouveau ! 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
    Candidat au Club
    Homme Profil pro
    Architecte matériel
    Inscrit en
    février 2016
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Aveyron (Midi Pyrénées)

    Informations professionnelles :
    Activité : Architecte matériel

    Informations forums :
    Inscription : février 2016
    Messages : 6
    Points : 3
    Points
    3

    Par défaut

    Oui je dois passer une seule et unique fois par chaque ville et par exemple, sur le cas que j'ai donné dans mon premier message, la ville n°1 ne peut être visitée qu'à la première, à la deuxième ou à la troisième étape. Le chemin 2-3-4-5-1 est par exemple impossible puisque la ville n°1 est visitée à la 5e étape. J'ai donc moins de solutions possibles que pour le TSP mais ça reste ingérable par dénombrement
    Merci pour les liens !

Discussions similaires

  1. Trouver le chemin le moins coûteux
    Par jecht10 dans le forum Général Algorithmique
    Réponses: 2
    Dernier message: 18/05/2017, 12h41
  2. Recherche de chemin avec A* en trois dimensions
    Par Snoopyjackson dans le forum Général Algorithmique
    Réponses: 6
    Dernier message: 01/10/2015, 14h06
  3. Plus court chemin dans un graphe avec contraintes
    Par tomjr dans le forum Général Algorithmique
    Réponses: 9
    Dernier message: 30/12/2009, 12h36
  4. Réponses: 2
    Dernier message: 26/09/2003, 15h54
  5. Algorithme de recherche de chemin
    Par amelie gaya dans le forum Général Algorithmique
    Réponses: 3
    Dernier message: 09/06/2002, 15h29

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