"P = NP ? " La recherche d'un algorithme

[jacknicklaus]

Donc on ne peut pas avoir [DB] = 1004, car [DB] doit être inférieur ou égal à 137. Ou alors ce n'est pas une norme.

Bonjour,

On n'a jamais parlé de norme dans le problème du voyageur de commerce. Ce point a déjà été abordé dans ce même fil, lire message 21 et suivants par exemple.
-----

[gg0]

Bon, je vais rectifier pour la médiane, puisque Jeanveux refuse de lire son livre jusqu'au bout de la phrase.

Pour un nombre n pair de valeurs, la médiane est entre deux valeurs, la n-ième et la (n+1)ième. Par convention (*) on prend alors la moyenne de ces deux valeurs.

Vouloir résoudre un problème mathématique compliqué quand on n'est pas capable de lire des questions mathématiques de fin de collège, c'est assez osé !
Sans compter que le problème pour 4 villes ne demande pas l'aide d'un ordinateur, et qu'avec les valeurs proposées et aucune condition sur une ville de départ, on a un chemin de longueur 55, et même en imposant le départ, on a au maximum 140; tout ça on le voit sur un dessin élémentaire. Manifestement, Jeanveux n'a même pas regardé si son algorithme donnait bien le minimum sur son exemple facile !! Lamentable !

J'en ai assez vu, je laisse tomber.

(*) une convention courante, mais il y en a d'autres ...

[Médiat]

Le fait de passer de la médiane à la moyenne selon la parité ne me donne pas confiance

[gg0]

En fait, c'est seulement une erreur de lecture du PP.

[Jeanveux]

Tout d'abord c'est un livre de vacance . et j'ai tout lu
Ensuite précision il faut partir par exemple du point A (point de départ) puis trouver un moyen de revenir à ce point de départ en passant par tout les points ,une seul et une seul fois et ce chemin doit être le plus court

[Jeanveux]

J'ai pas compris erreur de lecture du PP ?
Essayer l'algorithme sur les deux problèmes au moins ,j'ai réussi à trouver les longueur les plus courtes de mon coté .

[obi76]

Le fait de passer de la médiane à la moyenne selon la parité ne me donne pas confiance

+1. On doit avoir à peu près la même intuition sur ce coup là...

On remarque que le chemin additionnant ces valeurs est bien le (l'un des)plus court, et qu'il passe bien une seule fois par tout les points

Tout est dans la parenthèse. LE ou L'UN DES ? Parce que si ce n'est pas "LE", inconditionnellement, alors ça ne marche pas.

Merci vous avez raison, ma méthode de travail n'est pas idéale
( je pense d'abord au problème et seulement quand je pense avoir une solution je note sur papier)
Je me suis emmêler les pinceaux et me suis trompé dans l'algorithme
Je vais reprendre et déveloper mon exemple

[AB] = 100 [BC]= 3 [CD] = 20 [DA] =37

Les diagonales [DB] = 1004 et [CA] = 15

-Ranger les valeurs par ordre croissant soit :

3<15<20<37<100<1004

- Quand le nombre de valeur est paire on fait la moyenne

Sinon on prend la médiane

- On prend la valeur inférieur à cette moyenne ici 100

- On reprend les valeurs de la plus petite à la valeur en-dessous de celle prise (37)

Jusque là OK

- On prend la moyenne puisque le nombre de valeur est paire et on regarde si cette moyenne est inférieur à la valeur inférieur

Là non : de quelle valeur inférieure parlez vous ?

[Jeanveux]

Il faut savoir que je regarde ce qui ce dit sur Wikipédia (page :Problème du voyageur de commerce , sa vous aidera peut être à suivre mon point de vue ).Ensuite il peu y avoir plusieurs différent chemins de même longueur (il me semble d'après l'exemple que j'ai retenue tiré d'un livre ) d'ailleurs le chemin est un boucle puisque l'on revient au point de départ et on peut prendre la boucle en partant dans un sens ou dans l'autre puisque sa ne change pas la longueur . Pour :

"On prend la moyenne puisque le nombre de valeur est paire et on regarde si cette moyenne est inférieur à la valeur inférieur"

Ne tenez pas compte de la partie en gras je l'ai rajoutez pour le 2 ème exemple que je vous est donner à tester je vais y réfléchir plus tard je manque de temps

[Jeanveux]

Je viens de comprendre en gros on prend les valeurs 3,15,20 et 37 on fait la moyenne, puis on prend la première valeur supérieur à cette moyenne ici 20 ,en bref sa revient à ce que je dit dans le message précédent ignorer la partie en gras (c'est le "à la valeur inférieur" qui pose problème en réalité je l'ai mis la pour que l'algorithme reste juste dans le deuxième exemple que je vous est donner ,c'est un cas particulier il faut que j'explicite quand le compter )

[Jeanveux]

Sinon l'algorithme vous paraît-il au moins polynomiale ?

[Jeanveux]

J'ai tout compris je vous montrer l'exemple 2 demain .

[jacknicklaus]

Cet algo ne fonctionne pas (le doute était il permis ?)

Comme aucune information relative aux villes n'est utilisée, seulement les distances, il suffit de garder exactement les mêmes distances :
3 15 20 37 100 1004

mais affectées respectivement à BC (3), CA (15), DB (20), DA(37), AB(100), CD (1004).

l'algo va donc sortir la même solution, dans le même ordre : 100, 37, 20, 3. Soit les segments BA,AD,DB,BC , ce qui n'est pas un circuit valide.

[Jeanveux]

Bonjour,

Comme promis voici la façon d'on j'ai opéré pour l'exemple 2 que je vous ait donner à tester:

[AB] = 4 , [BD] = 2 , [DC] = 5 , [CA] = 3
Les diagonales [CB] et [DA] = 1






-On trie les chemins par ordre croissant : 1,1<2<3<4<5 (puisque les deux diagonales on la même longueur elle compte donc pour une seul valeur)

-Le nombre de valeur est donc impair on prend la médiane en soit 3

-Le nombre de valeur est paire ont prend la moyenne soit 1+2 diviser par 2 = 1.5 on voit que 1.5 est plus petit que que 2 d'où le :

"et on regarde si cette moyenne est inférieur à la valeur inférieur " (la valeur inférieur dont je parle est 2 et elle est supérieur à la moyenne )

-Comme dit dans l'algorithme SI OUI ont prend la valeur supérieur donc on prend 2


-On reprend l'algorithme comme c'est dit à l'étape 5

-Puisque le nombre de valeur est paire on prend 1+2=3 diviser par 2 =1.5

La valeur inférieur ici est 1 est comme 1.5 > 1 ont prend 1

3 + 2 + 1 + 1 = 7 ont voit bien que c'est bien le chemin optimale comme dit sur Wikipédia (page :Le problème du voyageur de commerce dans l'exemple donner )


Plus qu'un algorithme maintenant, mon raisonnement :

Quand ont fait la moyenne ou quand on prend la médiane on élimine le ou l'ensemble des chemins les plus long.
On ne peux donc prendre qu'un chemin en dessous où égale à la moyenne et si le nombre de valeur de base était impaire la valeur correspondant à la médiane
d'où l'alternance médiane / moyenne .
On se retrouve donc avec les valeurs les plus petite c'est bien mais il ne faut pas prendre de chemin qui nous ferais passer deux fois la même ville le reste
de l'algorithme est censé nous prévenir de ça . Au passage une précision l'algorithme va recommencer N fois -1 l'opération après avoir pris la toute première
moyenne ou médiane N étant le nombre de ville moins la ville de départ.

Bref je voulait vous remercier pour le temps que vous passer à me lire et à m'aider , je n'ai pas l'intention d'abandonner avant d'avoir trouver
(beaucoup peuvent dire ça mais moi je m'y tiendrai ).

Bonne journée /soirée


Cordialement

[Deedee81]

Salut,

Sinon l'algorithme vous paraît-il au moins polynomiale ?

De ce que j'ai vu il me semble que oui (mais j'ai malheureusement peu de temps pour creuser, je te remercie néanmoins pour tes précisions).
Par contre le plus difficile sera de démontrer qu'il donne le plus court chemin dans tous les cas et pas seulement sur des exemples.

[obi76]

De ce que j'ai vu il me semble que oui (mais j'ai malheureusement peu de temps pour creuser, je te remercie néanmoins pour tes précisions).

Oui il l'est (il est en N²).

Par contre le plus difficile sera de démontrer qu'il donne le plus court chemin dans tous les cas et pas seulement sur des exemples.

Mais il est faux, cf #42, la réponse à tout

[Opabinia]

Bonjour,

Si l'on veut s'attaquer à ce problème, il convient de fixer très clairement les données de l'énoncé.

1°) Le parcours est une ligne brisée passant par tous les points une fois et une seule; sa longueur ne dépend ni du point de départ, ni de son sens (à moins que l'on tienne à s'offrir le luxe de quelques complications gratuites); le départ se situe donc au point d'indice (1), admettant pour voisins immédiats dans la boucle déjà constituée ceux d'indice (i) et (j>i); on conviendra de choisir pour dernier point celui d'indice le plus élevé, de sorte que les rangs des 3 points évoqués vaudront respectivement:

r(1) = 1 ; r(i) = 2 ; r(j) = N .

On ne commence à appréhender la complexité du problème qu'en envisageant des ensembles de quelques dizaines de points; le nombre de boucles dans les conditions précédemment données vaut alors:

N_b = (N - 1)!/2 ,

et l'on obtient pour N = 100 (cas facilement géré par l'ordinateur): N_b = 4.6663E¹⁵⁵ .
Si l'on convient de noter D_min et D_max les distances minimale et maximale séparant deux points quelconques de l'ensemble, la longueur totale de la boucle se retrouve bornée par les valeurs extrêmes:

L_min = N*D_min et L_max = N*D_max ;

les (N_b) longueurs de boucles apparaissent ainsi séparées par un écart moyen:

e ~ (L_max - L_min)/N_b = 2N*(L_max - L_min)/(N - 1)! ,

soit en prenant D_max = 1 : e ~ 2/(N - 2)! = 10^-153 (résultat largement surestimé).
Le repérage du parcours minimal absolu suppose une précision calculatoire extravagante.
Il serait intéressant de connaître l'aspect de l'histogramme, qui présente une densité probablement beaucoup plus faible en ses extrémités; la recherche d'une boucle relativement courte apparaît néanmoins hors de portée d'un procédé aléatoire, et plus encore d'un calcul manuel.

2°) L'algorithme peut être allégé par le calcul préalable de toutes les distances (d_ij), que l'on consignera dans une matrice à éléments réels ou entiers; il ne s'agit pas forcément de la distance euclidienne, mais de la longueur du parcours direct entre les deux points considérés.

3°) On peut envisager la croissance régulière d'une boucle fermée par insertion d'un point à allongement minimal, soit à partir d'un triangle (i, j, k) - il y en a N(N - 1)(N - 2)/6 - soit à partir de l'enveloppe du nuage de points; mais les complications ne tardent pas à surgir, parce que la boucle immédiatement obtenue n'est pas optimale: il faut procéder au décroisement des segments en intersection, et échanger les connexions des extrémités de certains brins.

L'algorithme conduit bien à un raccourcissement substantiel du parcours total, mais le résultat dépend de l'ordre et de la fréquence des corrections apportées. Sa traduction graphique est intéressante, mais la mis au point du code est abominable.
Bon courage.

[Deedee81]

Mais il est faux, cf #42, la réponse à tout

Ah zut, j'avais pas vu.

Rectification alors : après correction (par l'un ou l'autre cht'tit test).
(EDIT si c'est possible ainsi car le message d'Opabinia me fait sérieusement douter)

Mais j'en doute fort quand même (ce serait trop beau), mais bon, Jeanveux peut toujours se lancer dans l'aventure

[Opabinia]

Bon courage.

(Suite) Il me paraît cependant téméraire de t'attaquer à la totalité du problème si, de ton propre aveu, tu es dépourvu de toute expérience de programmation.

Un projet plus limité, telle que l'expression de la longueur d'une boucle, peut déjà constituer une bonne initiation.

[obi76]

2°) L'algorithme peut être allégé par le calcul préalable de toutes les distances (d_ij), que l'on consignera dans une matrice à éléments réels ou entiers; il ne s'agit pas forcément de la distance euclidienne, mais de la longueur du parcours direct entre les deux points considérés.

J'ai envisagé uniquement l'algorithme proposé (qu'il soit bon ou pas est un autre problème), et du coup pour moi c'était bien ça qui était limitant, d'où le N².

Mais de toutes façons polynomial ou pas ne change rien à l'affaire, PUISQU'IL ne marche pas... Il trouve un trajet, oui, mais qui ne respecte pas systématiquement les consignes de départ, et dont à priori il ne trouve pas toujours LE minimum.

CQFD.

[Jeanveux]

Merci obi76 il l'est est donc bien en N² comme prévu.

Jacknicklaus tout ce qui compte c'est d'avoir tout les segments pour construire le parcours complet c'est tout, d'ailleur je crois que c'est ce que Opabinia dit par
ligne brisée.

Opabinia merci pour ta participation et oui je suis téméraire (je n'est pas l'habitude de me lancer dans des combat perdu d'avance).


Je ne sais pas si vous avez vu mais je vous conseil la vidéo de science etonnante sur le sujet (je préviens environ 30 min de bonheur) publié il y a 1 mois et demie
et le billet qu'il à écrit sur son blog (du même nom) qui apporte des précision et toujours Wikipédia à la page concernant le problème du voyageur.

Y a t'il vraiment besoin d'une démonstration qui montre que sa fonctionne dans tout les cas d'après la vidéo que je vous conseil il suffit juste
de trouver un algorithme polynomiale répondant à la question :

Est-il possible de trouver un chemin qui passe par toute les villes et qui soit de longueur inférieur à L ?

Comme dit dans un précédent message, si mon algorithme peut répondre à cette question décisionnelle par oui ou par non normalement ça devrais être un bonne preuve ?

Au passage est-ce que je pourrais avoir la position de chacun sur le problème et surtout si vous croyez que P différent de NP mon algorithme vous fait t'il douter
(il est polynomiale c'est pas mal déjà ) ?

Selon moi je l'ai déjat démontrer en vous donnant mon raisonnement dans mon précédent message :

Quand ont fait la moyenne ou quand on prend la médiane on élimine le ou l'ensemble des chemins les plus longs.
On ne peux donc prendre qu'un chemin en dessous où égale à la moyenne et si le nombre de valeur restant est impaire on prend la valeur correspondant à la médiane
d'où l'alternance médiane / moyenne .
On se retrouve donc avec les valeurs les plus petite, c'est bien mais il ne faut pas prendre de chemin qui nous ferais passer deux fois la même ville le reste
de l'algorithme est censé nous prévenir de ça en éliminant les chemins de trop.

Si il s'applique à petite échelle alors il n'y à aucune raison qu'à plus grande échelle il soit défaillant (si c'est le bon algorithme) ,il conviendrais de tester l'algorithme à plus grande échelle à minima (concernant le problème
en version traditionnelle , pour la version décisionnelle il suffit de prendre n'importe quel chemin respectant respectant les règles suivantes:

-passer par tout les points
-passer une seule fois par chaque point


Puis de lancer l'algorithme qui nous dira si il y a un plus court chemin (un plus court ,pas le plus court,bien que je sois persuader personnellement
que si il est le plus court sur un petit graphe il doit l'être dans un plus gros).

Tu crois que tu peux m'aider pour le code Obi76 ?

EDIT: Obi76 quel consigne ne sont pas respecter de mon coté tout va bien .

Je sais que balance des gros pavé , Merci de votre temps.

[obi76]

Tu crois que tu peux m'aider pour le code Obi76 ?

EDIT: Obi76 quel consigne ne sont pas respecter de mon coté tout va bien .

2 solutions :
- soit c'est un problème simple que je peux coder en 5 minutes (ce que je fais parfois ici pour trouver des contre exemples à chaque fois qu'on a une nouvelle révolution sur les nombres premiers ou sur Syracuse),
- soit c'est un problème long à coder (même si pas forcément difficile), et dans ce cas j'attends de voir l'intérêt. Si vous montrez que vous trouvez le plus court chemin et respectant les conditions initiales, je veux bien m'y coller. Dans le cas contraire j'ai autres choses à faire

Comme dit précédemment : le coder ne vous apportera absolument rien. Vous pouvez tomber sur des contre exemple par la simulation, auquel cas vous savez que ce que vous avez dit est faux. Mais ne pas en trouver ne veut pas dire que c'est juste (c'est ce que l'on vous a dit dès le départ). Votre algorithme a peut-être tort extrêmement rarement, vous ne le verrez peut-être jamais à la simulation, mais ça ne prouve rien.

[Deedee81]

Est-il possible de trouver un chemin qui passe par toute les villes et qui soit de longueur inférieur à L ?

Hé non, hélas ce n'est pas suffisant.

[Opabinia]

... je vous conseille la vidéo de science étonnante sur le sujet (je préviens environ 30 min de bonheur) publiée il y a 1 mois et demi ...

Je viens justement de regarder la vidéo, il y a quelques jours:

https://www.youtube.com/watch?v=AgtOCNCejQ8

elle est bien tounée, nous serons d'accord là dessus; cependant la réponse, quoique conjecturale, est formelle: (P) apparaît différent de (NP)

pour la majorité des experts (99 %).

Pour le problème du voyageur de commerce, la croissance du nombre de cas à envisager suit une loi factorielle, comme cela a été indiqué; elle dépasse en rapidité celle de tout polynôme, et même celle de toute exponentielle.

[Médiat]

mon algorithme vous fait t'il douter

Tant que vous n'aurez pas démontré que cet algorithme trouve le chemin le plus court dans 100% des cas, la question ne se pose même pas

[Jeanveux]

Je doit très mal m'expliquer mais le but de l'algorithme est de répondre à la version décisionnelle du problème
Disons que l'on prend un chemin respectant les règles au hasard il faut simplement trouver un chemin de longueur moins longue

J'insiste il faut répondre à cette question:
Est-il possible de trouver un chemin qui passe par toute les villes et qui soit de longueur inférieur à ?

PAS A LA QUESTION DE LA VERSION TRADITIONNELLE !!!

Mon algorithme est conçu pour trouver un chemin moins long qu'une autre chemin donner !

[Jeanveux]

Il faut prouver que P n'est pas égale à NP ce qui n'est pas fait par ces même expert sa laisse donc de l'espoir entre ce que les expert pense et la réalité il y a un gouffre ne prenez pas ce sondage au pied de la lettre plein de gens pensait que la terre était plate des "experts" à leur époque
pensait que tout tournait autour de la Terre maintenant nous savons que c'était faux !

Le problème reste donc ouvert !

[Médiat]

Tant que vous n'aurez pas démontré que cet algorithme trouve un chemin plus court quand il en existe dans 100% des cas, la question ne se pose même pas.

[Jeanveux]

On est d'accord que le trajet le plus court qui respecte les conditions imposer est forcément l' addition de segments :

1 - dont la longueur est moins longue
2 - dont l'addition permet de ne passer qu'une seule fois par ville
3 - dont l'addition permet de passer par toute les villes

OUI ? ou NON ?

[Médiat]

Que "plus court" = " moins long" je ne saurais le contester

[Jeanveux]

Je parle de la longueur des segment à additionner c'est la longueur de chaque segment qui doit être courte
je ne pas faire plus claire