Le probleme du voyageur de commerce : reflexions

[Mario2015]

En bref, le probleme du voyageur de commerce dans sa version standard c`est :
-de partir d`une ville, de passer par toutes les autres villes une seule et unique et de retourner a son point de depart.
-de suivre le chemin le plus court.

On connait la position geographique de chacune des villes et les distances qui les separent. C`est tout ce que l`on sait. On fait l`hypothese que toutes les villes sont connectees par une route.

L`idee m`est venue tout de suite.
Des clous places au bon endroit sur une suface en bois (auparavant "decoupee" en une grille nxn).
Ensuite, une ficelle assez longue pour pouvoir relier toutes les villes.

Commmencons par la fin. Nous avons trouve le chemin minimal!
On a donc notre ficelle qui relie toutes les villes.
Cela nous donne si on detache ficelle et clous de notre planche en bois un cercle dont la circonference est exactement egal au chemin minmimal.
Donc notre chemin minimal peut etre represente par une seule et unique valeur : la longueur du rayon de ce cercle.

La question mysterieuse qui se pose alors est la suivante : peut-on connaitre en temps polynomial ce rayon et donc le chemin minimal a partir des distances separant les villes (la matrice des distances)?

Si on repond correctement et avec certitude (ou forte probabilite) a cette question, une grosse partie du probleme est resolue. On connait l`objectif. Donc on tient notre ficelle qui represente le chemin minimal. Il ne reste plus qu`a l`ajuster et le tour est joue. Ce probleme d`ajustement sera discute apres.

Je vous laisse mediter une semaine ou deux sur cette question.
Comment peut-on a partir du tableau des distances estimer avec certitude ou forte probabilite la longueur de ce fameux rayon?

[lulu math discovering]

C'est un peu un problème de recherche tu sais ?

[Mario2015]

Une petite exprience :
Prenez un cercle de rayon connu r.
Placez au hasard 5 points (A,B,C,D,E) sur la circonference de ce cercle.
Calculer les arcs AB,BC,CD,DE,EA.
Maintenant que vous connaissez la longueur de chaque arc essayez de les transformer en un polygone en respectant exactement les memes distances point a point.
Combien de polygones differents vous pouvez creer (abstraction faite des rotations, des symetries et autres transformations)?

[Robot]

Si tu connais en temps polynomial la longueur du chemin minimal, tu sais répondre en temps polynomial au problème de décision associé au problème du voyageur de commerce (L étant donné, existe-t-il un chemin visitant toutes les villes de longueur plus petite que L ?). Ce dernier problème est NP-complet. Tu aurais donc prouvé P=NP, félicitations !
Bon, mais la règle du jeu est de prouver ce qu'on annonce. J'attends de voir.

Déjà, il y a un peu de flou : certitude ou forte probabilité ? Solution optimale ou presque optimale ?

S'il s'agit d'avoir une solution approchée, on sait (grâce à un mathématicien et à un informaticien théoricien) qu'il y a un schéma d'approximation en temps polynomial pour le problème du voyageur de commerce euclidien (en particulier dans le plan). Tu pourras trouver ça et d'autres informations intéressantes sur cette page wikipedia.

[Robot]

Une petite exprience :
Prenez un cercle de rayon connu r.
Placez au hasard 5 points (A,B,C,D,E) sur la circonference de ce cercle.
Calculer les arcs AB,BC,CD,DE,EA.
Maintenant que vous connaissez la longueur de chaque arc essayez de les transformer en un polygone en respectant exactement les memes distances point a point.
Combien de polygones differents vous pouvez creer (abstraction faite des rotations, des symetries et autres transformations)?

Une infinité, et alors ? A moins que par "polygone" tu veuilles dire polygone inscriptible dans un cercle ? Ou alors à moins que par ton "en respectant exactement les memes distances point a point", assez flou, tu veuilles dire autre chose que "la distance A'B' (resp. B'C', C'D', D'E', E'A') est égale à la longueur de l'arc (resp. ).

[Mario2015]

Une infinité, et alors ? A moins que par "polygone" tu veuilles dire polygone inscriptible dans un cercle ? Ou alors à moins que par ton "en respectant exactement les memes distances point a point", assez flou, tu veuilles dire autre chose que "la distance A'B' (resp. B'C', C'D', D'E', E'A') est égale à la longueur de l'arc (resp. ).

Prends ton temps. Analyse les hypotheses meme celles implicites etc....
Tu as une serie d`arcs qui lient des villes, forcement tu te dois de transformer ces arcs en lignes droites puisque le but est de creer un polygone irregulier.
Ce qui est te semble flou tu le precises et tu continue ton raisonnement.
Je parle de reflexions et non de preuves?
Pourquoi refusez-vous des idees?
Une idee devient preuve absolue et irrefutable apres avoir ete sujette a des milliers de cribles.

Les idees ne vous interessent pas. Passez votre chemin.
Il y a des gens qui sont capables d`aller au-dela de l`idee et de voir tout de suite l`ebauche d`une solution. Si on connait ceci peut-on connaitre cela. Et en connaissant cela a quoi cela nous mene.
etc... La pensee n`est la propriete de personne. Seul ce que l`on peut faire d`une idee est important.
Au dela des droits d`auteur, de la paternalite de telle ou telle decouverte, il y a le progres de la science. Personne ne s`interesse a l`argent et c`est la guerre quand il s`agit de qui. Qui a eu l`idee le premier? Qui est plagiaire qui ne l`est pas? Qui recevra les honneurs? et qui ne les recevra pas? etc... Si ces minus se declarent des scientifiques alors merde a la science. Une vie est sauvee et on se chamaille pour qui a sauvee cette vie. Mais bordel de merde! Une vie est sauve!!!! C`est cela le plus important.

[Mario2015]

En termes bambiniques tu as calcule la longueur de tes arcs AB,BC,CD,DE,EA.
Tu les transforme en batonnets de meme longueur AB,BC,CD,DE,EA et tu les donnes a un gamin en veillant a lui fournir un marteau, 5 clous (A,B.C,D,E) et une planche de bois. Tu lui demande de creer un polygone en reliant les clous.
Combien de polygones peut-il creer?

[Robot]

Alors j'ai déjà donné la réponse, à peu près évidente : une infinité. N'as-tu pas lu ? C'est tellement évident que je me demandais si tu n'avais pas quelque chose d'autre en tête.

L'analyse de la complexité d'algorithmes est une matière assez délicate. Des idées, c'est très bien. Mais si tu affirmes comme ça une complexité polynomiale qui entraînerait P=NP, personne ne te croira sur parole et c'est bien normal.
Je note que tu poursuis ton baratin de café du commerce, sans prendre la peine de préciser : solution certaine ou probable ? Solution exacte ou approximation de la solution ?

[Mario2015]

Alors j'ai déjà donné la réponse, à peu près évidente : une infinité. N'as-tu pas lu ? C'est tellement évident que je me demandais si tu n'avais pas quelque chose d'autre en tête.

L'analyse de la complexité d'algorithmes est une matière assez délicate. Des idées, c'est très bien. Mais si tu affirmes comme ça une complexité polynomiale qui entraînerait P=NP, personne ne te croira sur parole et c'est bien normal.
Je note que tu poursuis ton baratin de café du commerce, sans prendre la peine de préciser : solution certaine ou probable ? Solution exacte ou approximation de la solution ?

Donne un cercle de ton choix, 5 points A,B,C,D,E et cree-moi juste 5 polygones en respectant les distances. Je ne te demande pas une infinite juste 5 polygones.
Geogebra te sera utile.
Merci.

[Mario2015]

Pour te faciliter la tache je te donne 5 batonnets de longueur. 5 clous, un marteau et une planche.
Relies les 5 clous pour former un polygone.
Combien peux-tu en creer de distincts?
J`ai bien dit abstraction faite des rotations symetries et autres transformations.
Autrement, le meme polygone tu peux le placer en une infinite de positions differentes. Cela est evident. C`est toujours un SEUL polygone. Si par infinite tu vises cela c`est totalement faux et cela ne correspond en rien aux contraintes enoncees plus haut.

J`attends toujours tes polygones.
Je repasserai plus tard.

[Robot]

Pour te faciliter la tache je te donne 5 batonnets de longueur. 5 clous, un marteau et une planche.
Relies les 5 clous pour former un polygone.
Combien peux-tu en creer de distincts?
J`ai bien dit abstraction faite des rotations symetries et autres transformations.
Autrement, le meme polygone tu peux le placer en une infinite de positions differentes. Cela est evident. C`est toujours un SEUL polygone. Si par infinite tu vises cela c`est totalement faux et cela ne correspond en rien aux contraintes enoncees plus haut.

J`attends toujours tes polygones.
Je repasserai plus tard.

J'ai bien dit une infinité de non isométriques (pas obtenus l'un de l'autre par un déplacement ou une symétrie. Je m'étonne que tu ne saches pas qu'un pentagone n'est pas rigide. Il n'y a que le triangle comme polygone rigide (clair intuitivement). Pour des dessins, il te faudra attendre demain : pas de Geogebra sur mon téléphone!

[Mario2015]

Salut et bon dimanche,

Le Robot serait-il tombe en panne?
Et ce n`est que le debut! Cette discussion sera la plus longue de ce forum si vous ne le savez pas encore.
D`autres elements viendront car je sais ou je vais...
Les matheux d`aujourd`hui sont plus des attendeurs-de-reponses-toutes-cuites et de demonstrations-toutes-finies.
Alors que Wiles le pauvre a du se faire corriger a plusieurs reprises sa demonstration avant qu`elle ne soit publiee!!! Meme Wiles a commis des fautes! Il a continue son chemin car derriere tout ce qu`il a pondu il y avait une idee simple.

Allez! C`est dimanche, je vous pardonne d`etre si peu disert.
A demain donc!
Meditez! meditez! meditez!

[Mario2015]

Je radote je radote je radote.
Amen! Les grands matheux ont dit que ce probleme est NP complet.
Alors a quoi bon se casser les neurones nous qui sommes que de petits matheux.
Fermez cette discussion moi j`ai pris ma decision.
Je n`interviendrai plus jamais ni ici ni ailleurs.
Internet adios!
Mes idees je me les garde bien au chaud.
Pourquoi partager mes idees?
Aucun interet!
Un meteore venu d`ailleurs detruira surement tout ce que les bipedes ont fait.
Buvons et rebuvons a la sante des putains d`Amsterdam, de Kaboul, de Teheran, d`Ispahan ou d`ailleurs.

[Robot]

Bon du vent, rien que du vent donc.
Mario a dû se rendre compte que son histoire de polygone ne tenait pas debout.
On a ce qu'on appelle un 5-barres en théorie des mécanismes articulés. Il peut prendre une infinité de configurations. Quelques-unes sont représentées dans les figures qui suivent. La barre AB est fixe. Le point D peut bouger à l'intérieur de la zone bleutée.

[Dzp]

Bonsoir,
Une fois n'est pas coutume, j'interviens en public.
D'après ce que j'ai lu sur le sujet, et je crois que rien d'important ne m'a échappé, il y a le problème posé "P=NP, OUI ou NON ?"
A titre d'exemple, on cite le problème du voyageur de commerce.
Je le résume pour éviter toute ambiguïté : un voyageur de commerce doit visiter ses clients qui habitent différentes villes. Comment déterminer le trajet le plus court. Les villes ont une position connue et le trajet le plus court est assimilé à la distance entre villes. Toute autre considération, par exemple type de route, est exclue de l'intitulé de l'exemple.
S'il y a environ 70 villes, le nombre de solutions possibles et à tester est de l'ordre de 10^100. Ce qui est considéré, à juste titre, comme impossible à traiter.

Bon, le problème P= NP, ne me concerne pas, manque de compétences.

Par contre, l'exemple "voyageur de commerce" mérite une explication :
1- Il y a un problème à résoudre : étant donnée une certaine configuration de routes : quel est le meilleur trajet. Par trajet, il faut comprendre la meilleure route à suivre, compté tenu de certains choix. Ce problème n'est pas très difficile et est résolu depuis longtemps.
2- le voyageur de commerce part de chez lui le matin, fait sa tournée et rentre chez lui le soir. L'énoncé précise dans l'exemple que chaque ville ne doit être traversée qu'une seule fois. Cela n'a aucune justification de poser cela dans le cas réel.
3- Dans la réponse exposée par Robot, il y a une infinité de solution, même dans le cas de 5 villes. Sauf erreur de calcul, le nombre de possibilités avec 5 villes est 24. Que je sache, les villes ont une position fixe.

Petit [HS] : le problème de représentation d'une figure constituée d'objets liés par des relations, que l'on assimile, pour la représentation, à des distances, a été posé sur un autre forum. Ce problème est intéressant et me parait en rapport très proche avec le problème du voyageur de commerce.

Bonne soirée.

[Mario2015]

@Robot

Non! Je ne me debine pas.
Ma strategie de solution est claire : trouver en premier le chemin minimal.
Au debu, j`avais imagine une solution probabiliste pour m`en approcher en faisant des simulations. Mais aujourd`hui en visionnant une video sur un probleme de Hilbert m`est venue l`idee d`approcher cette valeur par convergence et la, j`aurai une valeur exacte.
Je reviens a mon polygone. Oui tu as raison. Il y a une infinite de polygones possibles. Quelqu`un m`a fait decouvrir cette mecanique d`articulation et je l`en remercie. Mon erreur etait due a mon idee de polygones distincts. L`articulation n`est qu`un type de transformation que je n`avais pas prevu. Ce qui est certain c`est que ce polygone qui est le circuit minimal vu que le reseau est constitue de lignes (de ville a ville), ce polygone appartient a coup sur a cette infinite de polygones possibles. La marice des distances fait que dans les faits seuls quelques polygones sont possibles voire un seul.
Pour eviter cet ecueil, il y a l`algorithme du "non-convex hull" qui permet de cerner de maniere assez precise ce polygone. Il ne correspond pas exactement au chemin minimal mais il s`en rapproche.
Pour me resumer, trouver la valeur exacte de ce chemin minimal avant de determiner exactement ce chemin est ma premiere priorite. Pour ce faire, j`aurai a solutionner de maniere dynamique une equation diophantienne simple.
Hypothse1-resultat-hypothese2-resultat etc... jusqu`a aboutir a la longueur exacte du chemin minimal.
Une fois ce travail fini, la seconde etape est plus classique avec la aussi une innovation de ma part que je tairai. Cela accelere le processus de classement des villes dans l`ordre requis pour atteindre ce putain de chemin minimal. Et la boucle est boucle.
Le probleme repute NP devient un probleme quasiment simple a resoudre.
Meme pour 1000000 de villes!

Maintenant, je me barre car j`en ai dit assez pour que certains d`entre-vous trouvent la solution et aillent reclamer leur du a la fameuse fondation.
L`argent, je n`en ai rien a cirer.

Ps : je n`ai pas relu mon post, alors s`il y eu des omissions ou des fautes d`orthographe, je m`en excuse. J`ai un clavier qwerty (je vis en zone anglophone)

[Robot]

"Le probleme repute NP"
Mario refuse toujours de comprendre que le problème de décision associé au problème du voyageur de commerce (étant donné L, existe-t-il un circuit visitant toutes les villes de longueur totale plus petite que L ?) est NP-complet, et que ce fait est un théorème démontré que rien ne pourra jamais remettre en cause.
Ceci n'entraîne pas qu'il n'existe pas d'algorithme polynomial pour le résoudre (puisqu'on n'a pas la preuve que P est différent de NP), et est tout a fait compatible avec le fait qu'il existe des schémas d'approximation en temps polynomial pour le problème du voyageur de commerce (ici aussi, c'est un théorème démontré).
Petite mise au point nécessaire pour contrer le flot d'obscurantisme.

[Monsieur23]

Résumé de la solution de Mario :

Pour trouver le chemin minimal
— trouver la longueur du chemin minimal
— trouver le chemin qui réalise la longueur minimale.

Grosse avancée, bravo.