P=np

[invite686ac3e5]

Parce que ça ne coute rien d'essayer, et parce qu'il est particulièrement simple a comprendre, J'ai passé quelque heures a tenter de résoudre ce problème. Étant physicien le problème NP complet du voyageur de commerce m'a interpellé, car sa résolution pourrait être potentiellement réalisable expérimentalement je m'explique : la lumière empruntant toujours le chemin le plus cours on peut simuler le trajet du voyageur par des rayon lumineux et reproduire les distances a l’échelles, et faire la manip, et ainsi trouver rapidement la solution. Et si la manip est faisable, la théorie est déroulable, donc même pas besoin de faire la manip. J'ai beaucoup d'idée sur le sujet, mais manque malheureusement de pratique mathématique., est ce que quelqu'un a déjà tenté cette approche ?
-----

[Deedee81]

Salut,

[...] est ce que quelqu'un a déjà tenté cette approche ?

Dans ce cas particulier, je ne sais pas. Je me demande d'ailleurs si ce message ne serait pas mieux placé en physique, d'autant des "résolutions de théorème" par des phénomènes physiques il y en a pas mal (par exemple, la détermination des surfaces minimales avec des films de savon).

Mais cette méthode n'implique pas que la mise en équation donne une solution de complexité polynomiale.

[KerLannais]

Bonjour,

On ne veut pas seulement que le chemin soit le plus court on veut également passer une et une seule fois par chaque sommet et je doute que l'on puisse faire ça avec des rayons lumineux

[Amanuensis]

annulé......

[A voir en vidéo sur Futura]

[invite1445654e]

euh on pourrait pas le mettre dans la partie mathématiques appliquées voire algorithmique ?

[KerLannais]

Il n'est pas usuel d'ajouter cette contrainte, il me semble.

Il faudrait alerter wikipédia pour qu'ils corrigent leur page dans ce cas.

Mais même sans la contrainte de passer au plus une fois par chaque ville il faut quand même passer au moins une fois dans chaque ville et je ne vois pas non plus comment faire ça avec des rayons lumineux.

[invite686ac3e5]

Il faudrait alerter wikipédia pour qu'ils corrigent leur page dans ce cas.

Mais même sans la contrainte de passer au plus une fois par chaque ville il faut quand même passer au moins une fois dans chaque ville et je ne vois pas non plus comment faire ça avec des rayons lumineux.

Les rayon lumineux passeraient plusieurs par les villes. on obtiendrait des interférences. et je pense que rapdiment ya pas mal de math, c'est pour ca que je post le sujet ici
Heuuu j'ai cherché ou poster, et je n'ai pas trop su ou.. libre aux modo de me placer ou bon ils leurs semblent...

[invite1445654e]

Les rayon lumineux passeraient plusieurs par les villes. on obtiendrait des interférences. et je pense que rapdiment ya pas mal de math, c'est pour ca que je post le sujet ici
Heuuu j'ai cherché ou poster, et je n'ai pas trop su ou.. libre aux modo de me placer ou bon ils leurs semblent...

par des rayons lumineux mmhh et pourquoi pas des fibres optiques mais je ne vois pas comment tu vas implémenter l'algorithme ainsi

[invite986312212]

(...)la lumière empruntant toujours le chemin le plus cours (...)

si le trajet du voyageur de commerce doit le ramener à son point de départ, le chemin le plus court est le chemin nul. Ce que tu cherches c'est un chemin court qui passe par des points imposés. Je ne crois pas que le principe de Fermat puisse t'aider ici. Il parle de chemin extrémal entre points de départ et d'arrivée fixés, mais pas de ce qui se passe entre les deux.

par ailleurs, dans le problème du voyageur de commerce, tu as un certain nombre de points et une "distance" (valuation) donnée pour chaque paire de points, mais rien ne dit qu'il existe une configuration de points dans l'espace à 3 dimensions telle que les distances usuelles entre paires de points soient égales aux valuations données. On sait qu'il existe une telle configuration dans un espace de dimension suffisamment grande, et donc tu vas devoir faire de l'optique en dimension supérieure à 3.