Si je fais ce poste aujourd’hui c’est parce que je pense avoir trouvé une solution au problème du voyageur de commerce. Quand je dis solution, je veux dire une méthode ou algorithme permettant de trouver le plus court chemin « rapidement » et ce, dans tous les cas.
Si vous préférez lire avec PDF, je vous mets le fichier à disposition ici.
Le problème du voyageur de commerce :
Le problème est posé de la façon suivante :
Imaginons que vous ayez un certain nombre de villes à visiter, une seule fois, et que vous souhaitiez revenir au point de départ à la fin. Ainsi vous connaissez les villes à visiter ainsi que toutes les distances qui les séparent. Le but est de trouver le chemin le plus court qui vous fera passer par toutes les villes, une fois, et vous ramènera au point de départ. Il existe plusieurs façons de résoudre ce problème (plus ou moins longues à réaliser) comme par exemple, en testant tous les chemins afin de les comparer entre eux, mais en ne gardant que le plus court. Vous imaginez bien que, plus on a de villes à visiter, plus il y a de chemins à tester et cette technique devient vite irréalisable même avec un ordinateur « très puissant ». Toute la difficulté est là. Il faut trouver un moyen d’obtenir le plus court chemin à chaque fois, et cela quel que soit le nombre de villes, les distances qui les séparent et tout ça dans un temps raisonnable (bien plus rapide qu’avec la méthode dite « brutale »). Pour plus d’information sur ce problème, je vous laisse consulter la page Wikipédia.
Passons donc à ma solution.
Voici ce que je propose :
Prenons un schéma composé de n points (appelons ces points : k0, k1, k2, …, kn-1.). Tous ces points sont reliés entre eux et espacés par des distances (appelons ces distances : d0 la distance de k0 à k1, d1 la distance de k1 à k2, …, dn la distance de kn-2 à kn-1.).
Maintenant, prenons les 3 points qui composent ce schéma ainsi que les distances correspondantes de façon totalement aléatoire, cela n’a aucune importance vous le verrez par la suite. (Avec un schéma à trois points vous pouvez tester plusieurs chemins, mais vous verrez que la distance totale sera la même pour tous, on peut représenter ça par un triangle). De plus, dans notre schéma de départ, tous les points sont reliés entre eux, ce qui veut dire que si vous partez du point k0 ou de n’importe quel autre point du schéma, vous pourrez obtenir le même chemin le plus court. Tout ça pour dire que le point de départ n’a aucune importance.
Bref, vous vous retrouvez avec un schéma à 3 points. Maintenant il vous faut arriver à un schéma avec vos n points. Pour cela rajoutons un point supplémentaire à votre schéma avec les distances correspondantes (ce point doit appartenir à votre schéma) de sorte à avoir un chemin passant par 4 points différents. Bien entendu, il ne faut pas rajouter ce point n’importe où, il faut faire en sorte que ce chemin soit le plus court de tous et pour cela voilà comment procéder :
Soit x,y,z vos trois points sélectionnés et xyzx votre chemin avec les distances correspondantes, vous voulez rajouter w (w appartient à votre schéma). Trois possibilités s’offre à vous soit xwyzx, soit xywzx ou xyzwx. Ensuite il faut simplement prendre l’un des trois chemins, celui qui est le plus court et répéter ça jusqu’à avoir un chemin passant par vos n points et revenant au point départ.
Par ailleurs, calculer la taille totale de chaque chemin demanderait :
(n²-n-6)/2 étapes, où n est le nombre de points de votre schéma initial.
Pour que ce soit plus simple, illustrons cela par un exemple.
Exemple :
Votre schéma de départ est composé de 5 points : A, B, C, D, E. Pour ma part je note les distance de cette façon-ci (dans le cas où d(x,y) = d(y,x) ): A :{AB ; AC ; AD ; AE} B :{BC ; BD ; BE} C :{CD ; CE} D :{DE}
A :{4 ; 2 ; 1 ; 3} B :{6 ; 1 ; 3} C :{7 ; 2} D :{1}
Comme cela on peut facilement voir d0(AB) ; d1(AC) …etc. Prenons 3 points du schéma au hasard : A, D et C et fixons le premier chemin ADCA. (Notez que l’on peut fixer des paramètres en plus comme par exemple imposer le point de départ). Maintenant, je veux rajouter un point. (Là aussi ça peut être n’importe lequel) Rajoutons B au chemin : 3 possibilités : ABDCA, ADBCA ou ADCBA.
ABDCA = 14 ; ADBCA = 10 ; ADCBA = 18. Le chemin ADBCA étant le plus court, je le garde. Maintenant je dois rajouter le dernier point E pour avoir mon chemin complet. Ici 4 possibilités :
AEDBCA, ADEBCA, ADBECA ou ADBCEA.
AEDBCA =13, ADEBCA = 13, ADBECA = 9, ADBCEA = 13.
Alors le chemin le plus court passant par A, B, C, D et E en partant de A et en revenant à A est ADEBCA. Je tiens à préciser tout de même qu’il est possible qu’il y ait plusieurs chemin partant du même point de départ qui soit les plus courts mais nous devons trouver au moins un chemin qui est le plus court.
Je vous remercie d’avoir pris le temps de lire ce post et je vous remercie d’avance pour tous les commentaires que vous ferais au sujet de cette solution (pour me dire si elle est valide, ce qu’elle vaut, ce que je peux en faire …etc.). De plus si quelqu’un veut m’aider pour réaliser le programme informatique pas de soucis, il suffit de me demander ;).
Le type d'algorithme que tu propose est assez connu des programmeurs avancés, on appelle ça un algorithme glouton : on maximise/minimise la solution sur un sous-problème et on agrandit les données d'entrée petit à petit. C'est une heuristique qui peut être super utile, on la retrouve notamment dans l'algorithme de Dijkstra pour trouver les plus courts chemins entre les points d'un graphe. Elle sert aussi à donner des solutions "pseudo optimales", c'est-à-dire pas optimales, mais pas loin non plus, notamment dans le problème du sac à dos, ou pour le voyageur de commerce que tu présente.
Il me semble qu'on peut cependant démontrer qu'elle donne un résultat "plus court que deux fois la longueur du trajet optimal". C'est en ce sens que les solutions sont assez efficace.
Au passage, je me permet de te dire que si réellement un jour tu trouvais un algorithme polynomial pour résoudre le problème du voyageur de commerce, étant donné que celui-ci est NP-complet, alors tu résoudrait le problème P=NP, qui fait partie des 7 problèmes du millénaire donnés pas l'institut Clay. La récompense pour la résolution d'un tel problème est à un million de Dollar.
Tu n'est donc pas le premier à te creuser la tête là dessus, notamment des brutes légendaires se sont cassés la tête sans trouver de solution, et avec des outils bien plus puissants que ceux que tu as à ta disposition. Il a donc été intelligent de ta part d'expliquer clairement ta méthode sur internet, les chances que tu résolve VRAIMENT ce problème étant quand même assez minimes (On déjà vu des gens venir sur ce forum en disant "j'ai résolu tel problème, mais je vais pas vous poster la solution sinon vous allez me voler le million de dollar... Sauf que comme d'hab leur solution était fausse, du coup on a galéré à leur expliquer pourquoi)
Si tu as la moindre question, que ce soit sur un terme technique que j'aborde, ou sur un point du contre-exemple que tu n'as pas pleinement compris, n'hésites pas
En lisant je n'ai rien vu d'insensé... Bon bah essayons de prouver que c'est faux, et si au bout de beaucoup de temps on a toujours pas trouvé de contre on peut la considérer comme valide.
Merci Grob' pour ton commentaire car je ne savais pas que ça existait déjà. Et ensuite je viens de passer sur le site et je me rends bien compte qu'en effet ça ne donne pas la solution optimale dans ce cas-là mais, dans tous les autres si ?
Sinon pour palier à ce problème, au lieu de comparer les nouveaux chemins, on peut comparer une distance (deux points) avec un chemin à trois points.
Exemple : Si je reprends mon exemple, on a nos 3 points A, D et C et le premier chemin est ADCA. Maintenant on veut rajouter B au lieu de comparer les chemins ABDCA, ADBCA et ADCBA, on regarde si AD>ABD, DC>DBC, CA>CBA. Si il y en a un qui est plus petit on le prend, dans le cas où il y en plus qu'un on compare les deux ex: ABD et CBA et dans le cas où il sont tous plus grands, on les compare tous : ABD, DBC et CBA.
Merci Grob' pour ton commentaire car je ne savais pas que ça existait déjà. Et ensuite je viens de passer sur le site et je me rends bien compte qu'en effet ça ne donne pas la solution optimale dans ce cas-là mais, dans tous les autres si ?
Non, c'est plutôt l'inverse : ton algorithme ne donne pas la solution optimale dans la majorité des cas, mais dans quelques-uns, comme ceux que tu étudies, si. Le problème est que pour les cas ayant peu de points (entre 1 et 10), ta méthode amène souvent au résultat optimal. Quand on a plus de points (entre 20 et 100), ton algorithme risque de ne donner quasiment jamais une solution optimale. Le problème, c'est qu'une instance du voyageur de commerce avec une vingtaine de points, c'est horrible à visualiser pour un humain comme toi et moi.
Le problème de l'algo glouton pour le voyageur de commerce, c'est que parfois rajouter un point change complètement le circuit à faire. L'algo glouton est super efficace sur des problèmes "stables par ajout de point", comme le calcul de la distance minimale entre deux points.
Et je n'ai pas bien compris ta proposition pour palier au problème, mais elle ne me semble pas "si" ouf, dans le sens où de toute manière les faiblesses de ton algorithme sont assez énorme, là où tu sembles penser qu'elles doivent être minimes et simple à patcher.
Ce n'est pas le million de dollars qui m’intéresse c'est simplement le fait de résoudre des problèmes qui paraissent très simple en apparence mais qui regorgent de de complexité et de mystère à la fois. Et il me semble important même à une petite échelle comme la mienne de partager les solutions que l'on trouve avec d'autre pour essayer très, très modestement de faire avancer la résolution et peut être même la compréhension de ces problème. Bon dans ce cas-ci ça ne change pas grand chose mais bon c'était sympas d'avoir chercher, je vais tenter une nouvelle route maintenant.
Grob' a écrit:
Et je n'ai pas bien compris ta proposition pour palier au problème, mais elle ne me semble pas "si" ouf, dans le sens où de toute manière les faiblesses de ton algorithme sont assez énorme, là où tu sembles penser qu'elles doivent être minimes et simple à patcher.
- Edité par Grob' il y a moins de 30s
Je voie donc plus notre problème à de points mois j'aurai une chance de trouver la bonne solution en procédant ainsi ?
Et oui je ne me rends pas forcement compte de tous ce que ça peut impliquer désolé.
Mais sinon ce que je proposais c'est Au moment ou on veut rajouter un point pour compléter le schéma, donc je veut rajouter B au chemin ADCA pour ça je ne compare pas les valeurs de ABDCA avec ADBCA et ADCBA mais je vais calculer ABD, DBC et CBA et les comparer respectivement à AB, DC et CA. Si imaginons que ABD<AD alors je sais que si j'inserts B de cette façon ABDCA j'aurai le chemin le plus court. Mais si par exemple, ABD<AC mais, que DBC<DC alors je compare ABD et DBC et je prends le plus petit si ils sont égaux, je compare AD et DC et je met B là ou la différence entre AD - ABD et DC - DBC est la plus petite et si AD = DC peu importe la solution. Enfin dans le dernier cas si Aucun des petits chemins ABD, DBC et CBA n'est plus petit que AD,DC et CA alors je fais la même procédure que précédemment mais avec toutes les distances : AD, DC, CA, ABD, DBC et CBA.
Mais maintenant je me rends compte de ce que tu voulais dire c'est que justement quand il y a égalité de distance et même dans ce que je viens dire plus haut, l'algorithme choira un chemin au hasard parce qu'il y en plusieurs qui sont égaux mais, le problème dans tous ça c'est que cela peut (et plus il y a de point plus il y a de chance que ça arrive) ne pas nous donner le chemin le plus court en rajoutant les points suivants à cause de ce choix. Et si on voulait contrôler cela la résolution ne serait plus polynomiale.
En tous-cas merci pour toutes ces informations ;).
Si ce type d'algorithme n'est pas choisit c'est parce qu’il est moins efficace (rapport résultat optimal/temps d’exécution et proportionnel au nombre de point) que les autres comme les algorithmes génétiques ou l'algorithme glouton du plus proche voisin ? Ou il y a d'autres raisons ?
J'aime bien ta vision de la recherche en général Certes on ne peut pas toujours faire avancer la recherche théorique parce qu'on a pas le niveau, mais mine de rien se pencher sur des problèmes comme ça, c'est aussi apprendre la méthodologie de la recherche, et apprendre le sujet dont on fait des recherches. Et éventuellement propager l'idée à d'autres gens (ici les lecteurs éventuels du forum) (Il faut savoir que, notamment en maths, des chercheurs passent leur vie sans jamais rien trouver, juste découvrir ce qui a déjà été fait, relayer les idées et informations entre théoriciens et praticiens etc.)
SuperToriel a écrit:
Mais sinon ce que je proposais c'est Au moment ou on veut rajouter un point pour compléter le schéma, donc je veut rajouter B au chemin ADCA pour ça je ne compare pas les valeurs de ABDCA avec ADBCA et ADCBA mais je vais calculer ABD, DBC et CBA et les comparer respectivement à AB, DC et CA. Si imaginons que ABD<AD alors je sais que si j'inserts B de cette façon ABDCA j'aurai le chemin le plus court. Mais si par exemple, ABD<AC mais, que DBC<DC alors je compare ABD et DBC et je prends le plus petit si ils sont égaux, je compare AD et DC et je met B là ou la différence entre AD - ABD et DC - DBC est la plus petite et si AD = DC peu importe la solution. Enfin dans le dernier cas si Aucun des petits chemins ABD, DBC et CBA n'est plus petit que AD,DC et CA alors je fais la même procédure que précédemment mais avec toutes les distances : AD, DC, CA, ABD, DBC et CBA.
Okay, je comprends ta démarche. En pratique si on devait implémenter ton algo c'est surement comme ça qu'on s'y prendrait. Au fond, l'idée reste la même : on compare les chemins, certes en comparant les seules parties qui sont différentes, mais on compare des chemins spécifiques.
Mais maintenant je me rends compte de ce que tu voulais dire c'est que justement quand il y a égalité de distance et même dans ce que je viens dire plus haut, l'algorithme choira un chemin au hasard parce qu'il y en plusieurs qui sont égaux mais, le problème dans tous ça c'est que cela peut (et plus il y a de point plus il y a de chance que ça arrive) ne pas nous donner le chemin le plus court en rajoutant les points suivants à cause de ce choix. Et si on voulait contrôler cela la résolution ne serait plus polynomiale.
Non, c'est même pire que ça. Si je reprend l'exemple du lien, mais que je décide de décaler un poil vers le bas les points C, A, J et B, le chemin optimal sans le point J est bien le chemin [...]ED[...]ACB[...], et il est unique (à priori, mais ça dépend des autres points), là où le chemin optimal avec le point J est [...]ECD[...]AJB[...]. Il y a des cas où l'ajout d'un point change complètement la tête du chemin optimal. Je viens d'en avoir une idée, je fais le dessin et j'édite ce post (incoming).
Pour ta question : En pratique il n'y a pas d'algorithme supra efficace pour résoudre ce problème. Quand on veut implémenter une solution proche de ce problème, il y a plein de méthodes, qui dépendent en pratique de comment exactement sont les entrées de ton problème, quelle taille de code on est prêt à utiliser, si on s'autorise à faire une réduction polynomiale, quel langage on utilise.
Je ne sais pas si des résolutions pratiques du voyageur de commerce utilisent l'algorithme glouton ou pas..
Et pour la culture, de mémoire, il existe un algorithme polynomial (donc assez rapide) pour le voyageur de commerce euclidien (càd un voyageur de commerce "comme sur une carte"). [EDIT : ma mémoire est fausse. Cf le 25e message de ce topic]
Très bien ! Merci pour toutes ces informations Grob' qui m'ont été précieuse et elle m'ont permis de comprendre plus de choses liées à ce problème et à l'optimisation en général.
Je vais me repencher sur le problème un peu plus tard et puis refaire un post si je trouve quelque chose à nouveau.
Bon, du coup je fais une nouvelle réponse pour mon contre-exemple (j'ai eu un truc à faire entre temps) :
J'ai fait le dessin pour l'idée, en pratique il faudra sûrement décaler quelques points, mais : Sans le point F, le trajet optimal, en rouge, serait ABCDEJIHGA Avec le point F, le trajet optimal, en bleu, serait AGBHCIDJEFA
Et ces deux trajets sont quand même très différents...
Et si, au lieu d'étudier des points, on étudiait des zones à la place ?
Reprenons le schéma de Grob' (merci à propos, c'est vachement plus pratiquement un schéma ), et penchons sur le point C par exemple : la distance la plus faible entre lui et un autre point, on remarque facilement que c'est le point H. On trace un cercle de centre C et de rayon CH, puis on l'agrandi en rajoutant un petit + à ce rayon (nommons-le h, le rayon de ce cercle devient CH+h). Forcément, à partir de ce h d'autres points vont arriver à l'intérieur de notre cercle. Et forcément, plus ce h est grand, plus on a une probabilité faible que les points à l'extérieur du cercle soit un morceau de notre chemin le plus court avec ce point C.
En mettant beaucoup de points sur une petite surface (genre 500 sur 1mm²) et en essayant d'avoir une probabilité forte que notre point soit dans le cercle en question pour solution du chemin le plus court (fixons 99%), on élimine tout les points peu probable (erreur de 1%) pouvant être morceau du chemin le plus court, points qu'on ne traite pas dans l'algorithme. Enfin, en comparant chacune des zones faites pour chaque point on peut vite remarquer que certains points n'auront que peu de points comme étant fort probable (notamment ceux en périphérie de la zone de points), ce qui réduit encore le nombre de choses à analyser.
Qu'est-ce que vous en pensez ? ^^'
(Oui c'est une procédure par élimination de possibilités, quand il y a trop de possibilités à analyser on est bien obligé, et qui dit éliminer des possibilités dit souvent appel aux probabilités... Désolé pour ceux qui trouvent la proposition moche)
J'ai mis du temps à comprendre ce que tu proposais mais si j'ai bien compris pour chaque point de notre schéma on trace des cercles de rayon xy+a, où x est notre point de départ et y le point le plus proche ainsi que a le petit "+" avec un échelle adapté pour pouvoir trouver les points correspondants, ceux qui se trouvent dans la zone sont les plus probables. Il faut que je test pour mieux me rendre compte, parce que là j'ai l'impression que c'est un résolution longue au début mais rapide à la fin. Un temps de résolution décroissant. Je te redis demain quand j'aurai testé (pour tout te dire, les images c'est pas trop mon fort ^^)
Bien que ton algo à l'air de limiter fortement le nombre de cas pratique, je suis pas sur qu'il présente un algorithme asymptotiquement plus intéressant que le bruteforce...
Je ferai des images pour expliquer (lorsque je serai sorti du bac ).
@Grob' : C'est même plus long car il faut d'abord faire ce cercle pour chaque point pour une proba fixé puis tester les points étant dans les cercles, donc 2 parties complètement différent dans l'algo qui prennent légèrement de temps que le bruteforce... Chacun. T_T
Je me souviens en particulier d'un algorithme de tri ( tri-bulle je crois), où la version de base contient 2 boucles imbriquées... temps de traitement souvent catastrophique, mais tri correctement effectué.
On ajoute une 3ème boucle exterieure, for (step =n/2 ; step=step/2; step >=1) ... et hop ! en rajoutant une boucle qui apparaît totalement redondante, on accélère le tri.
Et si, au lieu d'étudier les points, on étudiait les segments...?
On choisi une variable (on va la nommer V car V comme variable ) et on lui donne la valeur 0 pour départ. Ensuite on augmente V en le faisant passer par toutes les valeurs (de façon continue), et à chaque fois qu'une distance entre 2 points va être égale à V on trace son segment représentatif. Il suffira de stopper V lorsqu'on remarquera qu'une boucle est formé par les segments tracés. Non ?
C'est en ayant des alternatives à la tête que des idées naissent, et c'est souvent ensemble qu'on trouve une solution à un gros problème... Ce n'est pas pour rien que les scientifiques bossent toujours en groupe et que le groupe change peu. Après tu n'as pas faux, c'est loin d'être le + pratique comme méthode.
Dans ce problème, si on a par exemple 95 points, un dans chacune des 95 préfectures de France... galère.
Si on a toujours autant de points à relier, mais 10 autour de Marseille, 10 autour de Strasbourg... on arrive quasiment à une dizaine de problèmes beaucoup plus simples.
Une première étape du traitement peut donc être de chercher si on peut constituer des 'clusters'.
Je change un peu de sujet, mais en révisant je suis tombé là dessus :
Si jamais \(P \neq NP\) (ce qu'on a de bonnes chances de penser mais qui n'a pas encore été démontré), alors il n'existe aucun algorithme polynomial qui permet une approximation du voyageur de commerce.
(approximation = pas optimal mais pas loin)
Et pour le voyageur de commerce euclidien, alors pour toute constante C strictement plus grande que 1, il existe un algo polynomial permettant une C-approximation. (le problème euclidien n'est donc visiblement pas polynomial comme j'ai pu le dire à mon premier post, mais "quasiment")
(C approximation = la solution donnée est plus petite que C fois la solution optimale. Si C=1 ça implique de donner le résultat optimal).
Donc les hypothèses du problème dont on parle sont très importantes !
...Et sinon on peut chercher à optimiser un algo exponentiel.
Si jamais \(P \neq NP\) (ce qu'on a de bonnes chances de penser mais qui n'a pas encore été démontré), alors il n'existe aucun algorithme polynomial qui permet une approximation du voyageur de commerce.
(approximation = pas optimal mais pas loin)
Edité par Grob' il y a 36 minutes
Pour ce qui est d'un algorithme approximation pour le problème du voyageur du commerce je crois bien qu'il a été prouvé qu'il ne peut pas y avoir d'algorithme d'approximation pour le problème du voyageur du commerce là où d'autre problème NP-complet en ont. Il y a quand même une petite nuance il existe un algorithme d'approximation pour ce problème mais dans un cas particulier. Lorsqu'il y a égalité triangulaire et peut être un ou deux autres paramètres en plus. Dans ce cas il existe un algorithme d'approximation.
Je me suis aperçu de quelque chose quand à la manière dont on résout ce type de problème. Quelque soit la façon de faire plus on avance dans sa résolution, moins il y a de choix à faire et plus nous pouvons nous tromper. D'ailleurs, plus il y a d'instance de départ, moins on a de chance de trouver la bonne solution.
A mon avis, il n'y a pas de solution pour toujours avoir 100% des choix disponibles à n'importe quel moment de la résolution du problème. De même qu'avoir 100% des choix disponible est résolu pas la méthode brute. Mais cette méthode est TROP longue. Peut être que l'on peut résoudre ce problème si l'on connaissait dès le début la taille du meilleur chemin. Et si non, je pense qu'on ne pourra trouver d'algorithme optimale pour trouver la meilleure solution dans un temps polynomiale.
Pour ce qui est d'un algorithme approximation pour le problème du voyageur du commerce je crois bien qu'il a été prouvé qu'il ne peut pas y avoir d'algorithme d'approximation pour le problème du voyageur du commerce là où d'autre problème NP-complet en ont. Il y a quand même une petite nuance il existe un algorithme d'approximation pour ce problème mais dans un cas particulier. Lorsqu'il y a égalité triangulaire et peut être un ou deux autres paramètres en plus. Dans ce cas il existe un algorithme d'approximation.
...C'est exactement ce que j'ai dit, du coup... (enfin à la nuance près que si P=NP, alors il existe un algorithme de résolution exact du voyageur de commerce...) Du coup il me semble que Voyageur de commerce euclidien demande "juste" à avoir l'inégalité triangulaire ;)
A mon avis, il n'y a pas de solution pour toujours avoir 100% des choix disponibles à n'importe quel moment de la résolution du problème. De même qu'avoir 100% des choix disponible est résolu pas la méthode brute. Mais cette méthode est TROP longue. Peut être que l'on peut résoudre ce problème si l'on connaissait dès le début la taille du meilleur chemin. Et si non, je pense qu'on ne pourra trouver d'algorithme optimale pour trouver la meilleure solution dans un temps polynomiale.
Oui, je pense qu'une solution testant à chaque fois tous les choix disponibles est obligatoirement la méthode brute. Elle est en \(n!\) Il y a des méthodes plus rapides et exactes, cependant (avec de la programmation dynamique on peut faire \(n^2 2^n\), ce qui est exonentiel, mais aussi vachement plus rapide).
Et il me semble pas que connaître dès le début la taille du meilleur chemin aide tant que ça...
"Et sinon je pense que[...]" -> Ben ça c'est exactement le problème ouvert "P=NP", et il est loin d'être aussi simple qu'il en a l'air...
simple question qui n'est pas d'ordre mathématique pour le moment mais concernant le trajet recherché soit le plus cour n'est il pas possible de parler des trajets les plus courts, le premier et son exact inverse pour le second?
Dans ce cas la première et la dernière ville d'un trajet sont respectivement la dernière et la première ville du second.
Pour exemple
soit deux villes x et y
o ville de départ
il est simple de vérifier qu'il existe deux itinéraire les plus courts
o vers x vers y et retour vers o
o vers y vers x et retour vers o
il en est de meme quelques soit le nombre de villes. Si et seulement si cela est le cas la formule recherché devrait exprimer cette dualité car les deux résultats serai nécessairement vrai.
2x=x²