Répondre à la discussion
Affichage des résultats 1 à 26 sur 26

problème du voyageur de commerce



  1. #1
    Adri0

    problème du voyageur de commerce


    ------

    Bonjour à tous,
    J’ai une idée que je souhaiterai exprimer concernant le problème du voyageur.
    N’hésiter pas à me rattraper au vol si c’est incompréhensible ou simplement si c’est nimp..

    Le problème du voyageur de commerce pose comme problématique de trouver le chemin le plus court reliant plusieurs villes entre elles avec un point de départ et d’arrivée identique.
    Il n’existe pas un mais deux trajets les plus courts, le premier et son exact inverse pour le second.
    Le chemin est une boucle passant une fois par toutes les villes et revenant à la ville d’origine, ce qui implique que nous ne sommes pas obligé de commencer le calcul par la ville d’origine, nous pouvons commencer par n’importe quelles villes à visiter. (du moment que l-on passe une fois par toutes les villes)


    Soit
    Nice = N
    Paris = P
    Londres = L
    Rome = R
    Madrid =M
    Berlin = B
    Athènes =A

    Avec 6 villes :
    21 distances à mesurer :
    NP = PN = 688 km
    PL = LP = 344 km
    LN = NL = 1.028 km
    NR = RN = 471 km
    PR = RP = 1 105 km
    RL = LR = 1.433 km
    MN = NM = 975 km
    MP = PM = 1054 km
    ML = LM = 1263 km
    MR = RM = 1363 km
    BN = NB = 1081 km
    BP = PB = 879 km
    BL = LB = 932 km
    BR = RB = 1184 km
    BM = MB = 1870 km
    AN = NA = 1.520 km
    AP = PA = 2.096 km
    AL = LA = 2391 km
    AR =RA = 1051 km
    AM =MA = 2368 km
    AB =BA = 1083 km

    I.
    faire la somme des chemins d’une ville à toutes les autres :
    Dans l’exemple avec une ville d’origine et 4 villes à visiter :

    Pour la ville de Nice :
    Nice à Rome + Nice à Paris + Nice à Madrid + Nice à Londres = 3162km
    Pour la ville de Paris :
    Paris à Londres + Paris à Nice + Paris à Madrid + Paris à Rome = 3191km
    Pour la ville de Londres :
    Londres à Paris + Londres à Nice + Londres à Rome + Londres à Madrid = 4068km
    Pour la ville de Rome :
    Rome à Nice + Rome à Londres+ Rome à Madrid+ Rome à Paris = 4372km
    Pour la ville de Madrid :
    Madrid à paris + Madrid à Londres + Madrid à Rome +Madrid à nice = 4655km

    La somme la plus petite détermine la ville de départ, il s’agit de la ville la plus centrée par rapport aux autres.
    II. classer les villes par rapport aux sommes obtenues en I. , respectivement de gauche pour la plus petite à droite pour la plus grande dans un tableau.
    Ici :
    Tout à gauche Nice avec 3162km puis Paris avec 3191km puis Londres avec 4068km puis Rome avec 4372km puis tout à droite Madrid avec 4655km.

    III.
    Les chemins possibles ainsi que leurs distances sont inscrit dans les colonnes en dessous de chaque ville et par ordre croissant (le plus petit en haut).

    VI.
    Chercher les combinaisons les plus petites existantes, il faut « passer d’une colonne à une autre et repartir de la donnée possible la plus haute dans la colonne »

    Dans l’exemple :
    Nous partons de Nice vers Rome,
    Une fois dans la colonne de Rome nous sélectionnons le chemin le plus court au départ de Rome (le plus haut possible dans la colonne Rome), ici départ vers Paris.
    Une fois dans la colonne de Paris nous sélectionnons le chemin possible le plus court au départ de Paris(le plus haut possible dans la colonne Paris), ici vers Londres.
    Dans la colonne de Londres nous sélectionnons le chemin possible le plus court, ici vers Madrid car Londres-Paris déjà fait, Londres-Nice retour impossible car toutes les villes n’ont pas été visitées.
    Et retour de Madrid vers Nice.
    Soit : NR + RP + PL+ LM + MN pour le chemin numero 1.


    tableau calcul chemins par équilibre des distances 5 villes.png

    tableau calcul chemins par équilibre des distances 6 villes.png

    tableau calcul chemins par équilibre des distances 7 villes.jpg

    si vous avez lu merci à vous..

    -----
    x + x = x * x

  2. Publicité
  3. #2
    gg0
    Animateur Mathématiques

    Re : problème du voyageur de commerce

    Bonjour.

    Il te reste à traduire ça en un algorithme précis, puis démontrer que ça donne bien le chemin le plus court à chaque fois; et enfin calculer le temps d'exécution de ton algorithme. Si tu fais mieux que les algorithmes connus (il y en a plusieurs) tu amènes un progrès et si ton algorithme est polynomial c'est une révolution !
    Le problème du voyageur de commerce, c'est ces deux derniers points.

    Cordialement.

    NB: rien à voir avec la logique.
    Dernière modification par gg0 ; 23/09/2021 à 21h36.

  4. #3
    amineyasmine

    Re : problème du voyageur de commerce

    Bonjour
    Tu es en train de s’attaquer au problème PNP (P vs NP), il est à un million de dollars.

    Il est facile de vérifier une solution mais trouver une solution générale (algorithme) demandant un temps polynomiale n’est pas facile et on ne sait pas si cette solution existe.

    On remplace les villes par les grains de sable d’une petite plage et le voyageur par un être miniature qui doit passer par toutes villes (tous les grains) et faire le chemin le plus cours.

    Il faut pousser la réflexion un peu plus loin

  5. #4
    Deedee81
    Modérateur

    Re : problème du voyageur de commerce

    Salut,

    Pour s'attaquer au problème PNP, il me semble qu'il est plus intéressant de prendre une version la plus simple possible des problèmes NP-Complet.
    Il me semble qu'au niveau théorique le plus simple pour une attaque théorique est 3-Sat : https://fr.wikipedia.org/wiki/Probl%C3%A8me_3-SAT

    S'il s'agit juste de s'amuser avec un problème NP-Complet je trouve que le problème du démineur est plus sympa (à partir d'une configuration intermédiaire quelconque déterminer si cela peut correspondre à un jeu réel).

    S'il s'agit juste de pondre un algorithme, pourquoi pas. Comme dit plus haut il en existe plusieurs y compris des approchés fort bons et polynomiaux (le recuit simulé par exemple). Et le voyageur de commerce a le bon goût d'être à la base de beaucoup de problèmes pratiques, parfois sous des formes modifiées (la conception de circuits intégrés ou imprimés par exemple).

    Mais même dans ce cas il est indispensable de faire ce qui a été dit : démontrer (au sens mathématique rigoureux) que ça marche dans tous les cas et déterminer (au moins par des essais) sa complexité (sauf si on veut gagner le PNP, là faut le démontrer, pas juste donner des exemples).
    (je n'ai lu qu'en diagonale, c'est assez touffu et confus, mais à première vue je doute que ça marche dans tous les cas, mais je peux me tromper, je n'ai pas assez creusé)

    Mais d'une manière générale : ce message est mal placé, non ? Il n'a rien à voir avec https://fr.wikipedia.org/wiki/Logique_math%C3%A9matique
    (ne pas confondre évidemment avec la logique au sens commun)
    Il faudrait le déplacer dans le forum de math du supérieur si la question est mathématique ou dans le forum d'algorithmique s'il s'agit plutôt de programmation. Le message initial n'est pas clair sur ce point.
    Je laisse Adri0 en décidé ou les modos de ce forum.
    Dernière modification par Deedee81 ; 24/09/2021 à 06h33.
    Keep it simple stupid

  6. A voir en vidéo sur Futura
  7. #5
    albanxiii
    Modérateur

    Re : problème du voyageur de commerce

    Citation Envoyé par gg0 Voir le message
    NB: rien à voir avec la logique.
    Et donc déplacé en mathématiques du supérieur, faute de rubrique algorithmique et fondements de l'informatique.
    Not only is it not right, it's not even wrong!

  8. #6
    MissJenny

    Re : problème du voyageur de commerce

    Citation Envoyé par Adri0 Voir le message
    Il n’existe pas un mais deux trajets les plus courts, le premier et son exact inverse pour le second.
    il pourrait y en avoir plus de deux.

  9. Publicité
  10. #7
    danyvio

    Re : problème du voyageur de commerce

    Citation Envoyé par MissJenny Voir le message
    il pourrait y en avoir plus de deux.
    Tout à fait
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  11. #8
    Deedee81
    Modérateur

    Re : problème du voyageur de commerce

    Salut,

    Si c'est une boucle (comme proposé au début du premier message) il y en a même plus de deux (en incluant le point de départ)
    Keep it simple stupid

  12. #9
    Médiat

    Re : problème du voyageur de commerce

    Bonjour,

    Avant de se lancer dans des démonstrations, avez-vous
    1) vérifié que vos solutions pour 4, 5, 6 et villes sont optimales
    2) compté le nombre de calculs à faire pour 50 ou 100 villes, n villes (si c'est possible)
    3) vérifié que votre solution pour 50 ou 100 villes est optimale
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  13. #10
    Médiat

    Re : problème du voyageur de commerce

    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  14. #11
    Médiat

    Re : problème du voyageur de commerce

    Personnellement, si j'ai bien compris, je doute que cela marche :

    1) Choisir la ville de départ comme vous le faite, pourquoi pas, de toute façon il faut passer par toutes.
    2) Choisir la 3ième ville repose sur un algorithme
    3) Choisir la 2ième ville repose sur la liste exhaustive de tous les cas possibles

    Autrement dit votre alorithme marcherait à partir de la troisième mais pas de la deuxième ville, c'est bizarre et même suspect.

    Si j'étais vous, je testerais sur le défi des 250 villes pour voir où vous vous placez en distance et en temps
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  15. #12
    Deedee81
    Modérateur

    Re : problème du voyageur de commerce

    Citation Envoyé par Médiat Voir le message
    Si j'étais vous, je testerais sur le défi des 250 villes pour voir où vous vous placez en distance et en temps


    Le mieux serait déjà qu'il le programme (c'est quand même pas difficile d'écrire un programme) et le teste sur disons 4 villes
    (d'abord pour voir s'il sort quelque chose de cohérent, puis après seulement s'il donne bien le plus court et enfin après sur pleins de villes pour les performances)
    C'est déjà ça faute de démonstration.
    Keep it simple stupid

  16. Publicité
  17. #13
    Deedee81
    Modérateur

    Re : problème du voyageur de commerce

    Ah tiens, question. En dehors des défis du style 250, trouve-t-on facilement sur le net des cas avec seulement quelques villes mais azvec des configurations assez piégeuses pour des algos trop simplistes ?
    Parce que si j'ai 2000 villes sur une droite, là, c'est facile
    Keep it simple stupid

  18. #14
    Biname

    Re : problème du voyageur de commerce

    Salut,
    Le nombre d'itinéraires possibles est égale à la permutation du nombre de villes à parcourir ? Soit pour 7 villes : 7! = 5040 itinéraires. Le cas 7 villes se résout par la 'brute force' en quelques dizaines de microsecondes sur le PC 'qui va bien'. Pour 250 villes, il y a 3.23e492 itinéraires différents ... là, faudra aider la 'brute force' .

    Poser le problème en utilisant des distances établies de manière aléatoire(Rand, Rnd, Random) est très simple en informatique, écrire le code de la solution ne me paraît pas bien difficile non plus ??? Le pb est le temps machine nécessaire pour résoudre le problème, lorsque le nombre de villes augmente.

    Biname

  19. #15
    Médiat

    Re : problème du voyageur de commerce

    Bonjour,

    Citation Envoyé par Biname Voir le message
    Le nombre d'itinéraires possibles est égale à la permutation du nombre de villes à parcourir ? Soit pour 7 villes : 7! = 5040 itinéraires.
    Non, c'est plutôt (n-1)!/2 pour les graphes non orientés, comme ici et (n-1)! pour les graphes orientés, pour 7 villes, ici on trouve 360.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  20. #16
    Deedee81
    Modérateur

    Re : problème du voyageur de commerce

    Citation Envoyé par Biname Voir le message
    écrire le code de la solution ne me paraît pas bien difficile non plus ???
    Je suis d'accord, c'est même élémentaire. Mais ci-dessus je parlais bien entendu code pour l'algorithme de Adri0
    Keep it simple stupid

  21. #17
    Médiat

    Re : problème du voyageur de commerce

    Citation Envoyé par Deedee81 Voir le message
    Je suis d'accord, c'est même élémentaire.
    C'est bien pourquoi je proposais le défi des 250 villes, l'algorithme ne devant pas touné plus d'une minute dans ce cas
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  22. #18
    GBo

    Re : problème du voyageur de commerce

    Citation Envoyé par Médiat Voir le message
    C'est bien pourquoi je proposais le défi des 250 villes, l'algorithme ne devant pas touné plus d'une minute dans ce cas
    Et ce serait une très bonne preuve du concept. Et c'est à Adri0 de s'y coller, car c'est à lui de prouver que son algo est intéressant

  23. Publicité
  24. #19
    MissJenny

    Re : problème du voyageur de commerce

    Citation Envoyé par Biname Voir le message
    Le nombre d'itinéraires possibles est égale à la permutation du nombre de villes à parcourir ?
    c'est le cas si on a un chemin entre chaque paire de villes, mais dans certaines versions du problème ça n'est pas le cas et on peut être amené à passer plusieurs fois par la même ville.

  25. #20
    Deedee81
    Modérateur

    Re : problème du voyageur de commerce

    Chose étonnante, pour un graphe quelconque il existe un algorithme optimal et polynomial de recherche du plus court chemin entre deux points.
    (doit pas passer par toutes les villes !)
    C'est utilisé dans les GPS par exemple
    (c'est un ami mettant au point un algo de manipulation de bras robotique pour les tokamaks qui m'avait montré ça il y a, ooooohhhhh, fort longtemps )

    Comme quoi des problèmes qui se ressemblent n'ont pas nécessairement les mêmes difficultés du tout
    Keep it simple stupid

  26. #21
    Médiat

    Re : problème du voyageur de commerce

    ..... Dijkstra ?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  27. #22
    Deedee81
    Modérateur

    Re : problème du voyageur de commerce

    Citation Envoyé par Médiat Voir le message
    ..... Dijkstra ?
    Ah, j'ai regardé de près. Il est un peu plus général que la version que je connaissais (qui n'était applicable qu'à un graphe plongé dans un espace métrique) mais c'est bien ça.
    Merci,
    Keep it simple stupid

  28. #23
    Médiat

    Re : problème du voyageur de commerce

    En plus ça se programme en 10mn douche comprise, euh documentation comprise.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  29. #24
    Deedee81
    Modérateur

    Re : problème du voyageur de commerce

    Citation Envoyé par Médiat Voir le message
    En plus ça se programme en 10mn douche comprise, euh documentation comprise.
    faut quand même initialiser le graphe, si tu fais ça en lignes de code ça peut prendre un peu de temps

    Mais l'algo en soi oui, c'est simple. A l'époque j'avais trouvé ça extraordinaire.
    Keep it simple stupid

  30. Publicité
  31. #25
    Opabinia

    Re : problème du voyageur de commerce

    Bonjour,

    Si tu veux trouver la solution optimale sur un ensemble de 7 villes, par exemple, tu peux commencer par en établir la liste classée par ordre alphabétique et en déduire le tableau des distances, matrice carrée symétrique à éléments diagonaux nuls.

    La boucle fermée, dont la longueur ne dépend pas du point de départ, commence à la première ville d'indice nul; on considère d'abord les deux points reliés au précédent par un trajet direct, donc celui qui intervient en seconde position (d'indice Ia) et le dernier (d'indice Ib): le trajet sera ainsi représenté par la séquence
    < 0 , Ia , J1 , J2 , J3 , J4 , Ib , 0 > .

    Chaque boucle pouvant être parcourue dans un sens ou dans l'autre, on conviendra de ne retenir que celles vérifiant
    Ia < Ib
    afin d'éviter tout calcul inutile; l'énumération des premiers indices s'effectuera donc sur les domaines:
    0 < Ia < Nv - 1 et Ia < Ib < Nv .
    Pour les 3 suivants (J1, J2, J3) il faudra balayer l'intervalle [1 ; Nv - 1] en évitant les valeurs mutuellement identiques, ou égales à celles des précédents indices (Ia, Ib).
    Le dernier s'obtient par simple différence, compte tenu de ce que la somme de tous les termes est constante:
    Ia + Ib + J1 + J2 + J3 + J4 = 1 + 2 + ... + 6 = 21 .
    L'énumération de tous les cas s'effectue rapidement dans le cas envisagé:

    Nom : Tab_123.png
Affichages : 96
Taille : 168,3 Ko

    L'algorithme, bien que comportant déjà 5 boucles imbriquées, n'est pas très compliqué; mais on voit facilement qu'il ne peut conduire à la solution rigoureuse dans le cas le plus général, en raison d'un allongement considérable et de plus en plus rapide du temps de calcul; l'introduction d'une nouvelle ville s'accompagne de l'insertion d'une boucle supplémentaire, et l'exécution du programme cale en pratique au-delà d'une douzaine de villes - je ne me rappelle plus la limite exacte.

    PS: La première ligne des résultats (zone noire) affiche les dernières valeurs énumérées de (Ia) et (Ib).
    Dernière modification par Opabinia ; 24/09/2021 à 17h18.

  32. #26
    Biname

    Re : problème du voyageur de commerce

    Salut,
    Citation Envoyé par Médiat Voir le message
    Bonjour,
    Non, c'est plutôt (n-1)!/2 pour les graphes non orientés, comme ici et (n-1)! pour les graphes orientés, pour 7 villes, ici on trouve 360.
    Oui ! Heureusement, j'avais laissé un point d'interrogation
    - tous les chemins sont des boucles qui peuvent être parcourues dans les deux sens, on divise par deux
    - un chemin/boucle peut débuter en chacun des points de ce chemin, chacun de ces chemins présente la même distance à parcourir (n-1)

    En pratique pour un programme :
    Ai nodes/villes pour i = 1 à n, tous les chemins commencent par/à A1 et l'index du second node du chemin est toujours inférieur à l'index du dernier node, ... dans le cas d'une énumération croissante de gauche à droite ... comme ci-dessous (dans les autres cas aussi ????).

    essai avec a b c d (n-1)/2 = 3 A1 = a, A2 = B, A3 = c, A4 = c
    a b c d
    a b d c
    a c b d exclu 'a c d b' car index de b (dernier) < index de c (second)

    essai avec a b c d e (n-1)/2 = 12
    01: a b c d e
    02: a b c e d
    03: a b d e c
    04: a b d c e
    05: a b e c d
    06: a b e d c
    07: a c b d e
    08: a c b e d
    09: a c d b e exclu 'a c d e b' car ic > ib et = 06
    10: a c e b d exclu 'a c e d b' car ic > ib et = 03
    11: a d b c e exclu 'a c d e b' car ic > ib et = 06 exclu 'a d b e c' car id > ic et = 10
    12: a d c b e
    : a e x x x toujours exclus car ix tjrs < ie

    Ouf ! avec les index c'est peu clair A1 A3 A2 A4 ???

    Biname

Discussions similaires

  1. Les applications du Problème du voyageur de commerce
    Par grantstewart2 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 22/01/2019, 07h48
  2. Python : Problème du voyageur de commerce
    Par Elsoulevor dans le forum Programmation et langages, Algorithmique
    Réponses: 9
    Dernier message: 29/12/2018, 22h02
  3. Problème du voyageur de commerce
    Par naya76 dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 03/11/2010, 13h16
  4. probleme du voyageur de commerce
    Par boussoute dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 15/03/2009, 21h09