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

[Médiat]

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

oui, mais cela est faux (sinon le problème serait résolu depuis longtemps)!
-----

[Jeanveux]

Mais ce n'est pas la seul condition que j'ai mis dans le message précédant ,vous voyez quand même que j'ai énuméré 3 chose essentiel !

[obi76]

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 ?

Oui, mais rien ne vous dit qu'à un moment l'optimum ne consiste pas à prendre un chemin plus long que ce qui est disponible, et que du coup cela réduirait la somme des segments restant, suffisament pour que la somme de toutes les longueurs soit plus petite que ce que vous proposez. Donc non, vous n'avez pas démontré que le chemin que vous avez est LE plus court. Et rien ne prouve non plus que l'algorithme que vous proposez respecte les conditions que vous avez énoncées (cf #42).

Et si vous ne savez pas montrer que vous trouvez TOUJOURS le chemin LE plus court, alors vous n'avez rien résolu. Même si vous avez raison dans 99,99...9 % des cas, ce n'est pas 100%, le problème n'est donc pas résolu.

Comme déjà dit : faire un code vous permettra éventuellement de prouver que vous ne résolvez pas exactement 100% des cas en trouvant un contre-exemple (donc que ça ne marche pas), mais ne pas trouver de contre-exemple par cette méthode ne prouve en rien que vous le trouvez dans 100% des cas (donc que ça marche). Vous ne démontrerez rien avec cette approche.

Il faut faire les choses dans l'ordre. L'intérêt d'un code, c'est quand ce sera démontré. Et jusqu'à là il n'y a pas un début de preuve.

[Jeanveux]

Je sait tout ça je l'ai expliquer dans plein de message ou je dit comment j'ai construit mon algorithme
pourquoi on prend la moyenne ou la médiane etc... il faut que je réexplique ?

[Médiat]

Mais ce n'est pas la seul condition que j'ai mis dans le message précédant ,vous voyez quand même que j'ai énuméré 3 chose essentiel !

Ces autres conditions sont celles de l'énoncé !

Moi, j'abandonne !

[obi76]

Je sait tout ça je l'ai expliquer dans plein de message ou je dit comment j'ai construit mon algorithme
pourquoi on prend la moyenne ou la médiane etc... il faut que je réexplique ?

On a bien comprit. Mais COMMENT PROUVEZ-VOUS que cette méthode :
- donne LE chemin le plus court à chaque fois
- respecte bien les conditions que vous avez énoncées ?

Pour le moment ni l'un ni l'autre n'est montré. Et tant que ça n'est pas fait, on en revient à discuter du sexe des anges à chaque fois.

Si vous l'avez compris, ben démontrez-le...

Par ailleurs, le message #42 montre que les conditions ne sont pas systématiquement respectées, ce qui invalide la totalité de ce que vous dites. Qu'y répondez-vous ?

[Liet Kynes]

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 !

Ce n'est pas fait et le sondage est donc un non sens. Quand on ne sait pas, on prouve ou l'on énonce une conjecture. Pour énoncer une conjecture il faut soit avoir un crédit maxi-maxi en tant qu'expert ou sortir un test sur un nombre XXL^XXL d'essais avec un résultat vrai (idéalement le test sur un échantillon aléatoire ) la conjecture permet peut-être de réduire le champs de recherche mais peut aussi être un biais cognitif et un grand nombre de tests sans arguments et développement préalable d'hypothèse risque fort d'être laissé de côté par les experts.

[obi76]

C'est surtout que dans un cas comme celui-là, si la preuve n'est pas 100% exacte (et donc les essais ne servent à rien), elle est invalide. Point barre.

[Jeanveux]

Je n'ai que peu de moyen en tant qu'amateur pour que l'on m'écoute je ne vois que deux moyen vous faire comprendre , et tester l'algorithme un grand nombre de fois et vérifier .
Vous réexpliquée lentement mais surement

Obi76 s'il vous plaît pouvez-vous coder l'algorithme ? Je ne peux le vous demander qu'en tant que faveur .

Je vais réexpliqué dans le prochain message en reprenant les 2 exemples précité .

[Liet Kynes]

C'est surtout que dans un cas comme celui-là, si la preuve n'est pas 100% exacte (et donc les essais ne servent à rien), elle est invalide. Point barre.

Il suffit d'un contre exemple pour déterminer que l'on ne peut dire "pour tout.." et en même temps il reste la possibilité de dire " pour tout"+"sauf". L’apparition du contre exemple permet cependant sa généralisation dans ses déclinaisons: la quantification de celles ci est alors déterminante. Je ne sais pas s'il y a des exemples de telles circonstances?

[Jeanveux]

Si Obi76 accepte de coder et trouve un seul contre exemple je reverrai mon algorithme , il est sûr que même en une centaine d"essaie il n'en trouvera pas .

[Liet Kynes]

Si Obi76 accepte de coder et trouve un seul contre exemple je reverrai mon algorithme , il est sûr que même en une centaine d"essaie il n'en trouvera pas .

100 c'est un peu 100^100 c'est un peu plus etc.. vous avez besoin de tester mais le fait qu'un "grand" nombre de résultats (pour peu que le mot grand ne soit pas grotesque dans sa sémantique dans ce contexte) ne permettra peut-être pas de faire de cette algorithme une conjecture: il faut d’abord analyser et décrire certaines règles pré établies, ou en définir de nouvelles pour attirer des analystes trouvant votre démarche pertinente.
Dans le problème P=NP le temps de calcul et de travail des experts est malheureusement limité.. Quelques amateurs pourront peut-être s'y pencher mais dans ce cas le mieux est de consacrer votre propre temps.

[Jeanveux]

Si je comprend bien je doit vous montrer pourquoi la construction de mon algorithme trouve UN chemin( pas LE ) moins long parmi n'importe quel chemin pris au hasard et ce dans 100 % des cas .

[Liet Kynes]

Si je comprend bien je doit vous montrer pourquoi la construction de mon algorithme trouve UN chemin( pas LE ) moins long parmi n'importe quel chemin pris au hasard et ce dans 100 % des cas .

Je vais citer gg0: "en maths, savoir c'est quasiment comprendre" le "quasiment" consiste à montrer ce que l'on affirme et ce n'est pas le chemin le plus court, le plus souvent

[obi76]

Si Obi76 accepte de coder et trouve un seul contre exemple je reverrai mon algorithme , il est sûr que même en une centaine d"essaie il n'en trouvera pas .

1 - non, comme je vous l'ai dit, je n'ai aucune bonne raison ni espoir de le faire pour le moment
2 - une centaine... j'espère que vous rigolez là... Si avec quelques millions ou milliards ça marche systématiquement (avec 0 contre exemple donc), on pourra commencer à se poser la question de si c'est toujours le cas (ce qui ne répondra même pas à la question).
Juste pour l'exemple, je suis tombé il y a quelques années sur un problème du même genre (purement algorithmique lui), avec 10^15 tests sans aucune erreur, je ne considère même pas que c'est validé, mais juste que c'est "fiable". Et dans votre cas, "fiable" ne suffit pas. Il en faudrait une infinité, ce qui n'est pas possible. Il vous faut donc une démonstration, que la simulation ne vous apportera pas comme ça. C'est ça que vous devez comprendre : simulation ou pas, c'est une démonstration qui vous permettra de le prouver (si c'est vrai, ce dont beaucoup d'entre nous doutons, pour rester dans l'euphémisme).

[obi76]

Si je comprend bien je doit vous montrer pourquoi la construction de mon algorithme trouve UN chemin( pas LE ) moins long parmi n'importe quel chemin pris au hasard et ce dans 100 % des cas .

Heu non : LE.

1 - Un algorithme qui trouve UN chemin dans 100% des cas, ce n'est pas très compliqué à faire. En fait c'est même évident. UN DES CHEMINS LES PLUS COURT, c'est un peu plus dur, mais vraiment pas compliqué non plus.

2 - Trouver LE chemin le plus court (dans le sens : il n'existe pas de chemin plus court), parmi des points choisis au hasard, et-ce dans 100% des cas, et en plus en respectant les critères énoncés au départ, là est tout la difficulté... et ce qui est nécessaire. (c'est la réponse à cette question qui est de difficulté factorielle, et donc si vous trouvez un algo polynomial qui arrive TOUJOURS à ce résultat qui serait d'une extrême importance).

Pour le moment, ce que vous avez fait est dans le cas n°1 (et encore pas toujours, cf #42, j'insiste). Votre ambition est le cas n°2. Et entre les deux... ben si vous arrivez à répondre à cette question, là ça sera vraiment sérieux. Pour le moment on en est (très) loin, puisque le point n°1 n'est même pas toujours rempli.

Si votre ambition est de trouver "un des" chemins les plus courts, là on sait bien faire en polynomial, et donc ce que vous avez fait n'apporte rien. C'est bien "LE" plus court systématiquement qui apporterait quelque chose.

[Deedee81]

Salut,

A noter que sélectionner les plus courts chemins de chaque segment ça existe depuis longtemps. C'est même le premier algorithme connu. J'aurais été bien infoutu de le reconnaitre car si cet ancêtre était rédigé clairement l'algorithme décrit ici lui a été rédigé en Chinois puis traduit en Swahili avant d'être retraduit en Français, en bref (ou akuna matata si vous voulez) un algorithmes si mal rédigé qu'il aura fallu plus de 70 messages pour le comprendre. Franchement, même quand je parle en suédois ils me comprennent plus vite (mais pas en anglais à cause de mon horrible accent ).

Or on sait depuis le début que cet algorithme n'est pas optimal, loin de là. Comme expliqué plus haut il faut fréquemment sélectionner un segment plus long que ce qu'on voudrait pour que le chemin complet lui soit plus court. Et malheureusement avec l'augmentation du nombre de villes (ou de circuits électroniques, les calculs de pistes en circuits imprimés ou intégrés est typiquement un problème de ce type) ce nombre de cas augmente vite.

La méthode du recuit simulé consiste d'ailleurs à s'éloigner volontairement d'une solution que l'on croit naïvement optimale pour essayer d'en trouver une meilleure.

Donc si l'algorithme :

Je parle de la longueur des segment à additionner c'est la longueur de chaque segment qui doit être courte

n'est pas le meilleur, loin de là.

Au moins le recuit simulé fonctionne bien et lui est en N.log N (et utilisé dans un grand nombre d'applications NP complet).
Et donc meilleur que l'algorithme de jeanveux qui est en N². Donc quitte à choisir un truc "approximatif" je préfère conserver ce qui existe.

Pour terminer je rappellerai qu'en science c'est à l'auteur de démontrer. On ne peut pas faire le plus simple (pondre un algorithme, car ça je peux en pondre dix à la douzaine, c'est même l'essentiel de mon métier ) puis demander aux autres de faire le plus difficile : coder, chercher des contre-exemples, démontrer. Faudrait être fameusement culotté pour ça. Et en plus contrairement à d'autres notions de "vérité" dans la vie humaine c'est l'auteur qui doit prouver et non les autres invalider. Allez y les gars, j'ai fait 1% du boulot faites le reste bande de nazes

Et rappelons que tous ont leurs propres recherches dans divers domaines et n'ont pas que ça à faire, s'occuper des problèmes des autres : non merci, j'ai les miens. Et vu les résultats cités ci-dessus je doute fort qu'une équipe se forme !!!!! Les chercheurs n'aiment pas trop les trucs foireux et préfèrent les recherches pouvant réellement aboutir.

Je crois que ce fil va maintenant assez vite clôturer il me semble.

[DavianThule95]

Au fait, simple curiosité de ma part :
Depuis l'accueil, on peut voir que cette discussion est ornée de 5 étoiles (pièce jointe pour une image).

Qu'est-ce que cela veut dire ?

[Antoane]

Bonjour,

Au fait, simple curiosité de ma part :
Depuis l'accueil, on peut voir que cette discussion est ornée de 5 étoiles (pièce jointe pour une image).

Qu'est-ce que cela veut dire ?

Qu'il y a encore du travail pour que le logiciel du forum soit bien paramétré... mais c'est en cours

[DavianThule95]

OK ok !

Merci lol

[Liet Kynes]

Au moins le recuit simulé fonctionne bien et lui est en N.log N (et utilisé dans un grand nombre d'applications NP complet).
Et donc meilleur que l'algorithme de jeanveux qui est en N². Donc quitte à choisir un truc "approximatif" je préfère conserver ce qui existe.

Marrant, je me suis posé la question de savoir si dans la nature un organisme vivant était confronté d'une façon ou d'une autre au problème du voyageur de commerce: comme dans la nature les choses ont parfois tendance à s'optimiser de façon impressionnante en particulier dans le principe de l'économie de la ressource (énergie /eau / nutriments): j'ai trouvé ce site https://interstices.info/le-probleme...r-de-commerce/ qui donne une vision assez large du problème mais pour la nature il ne cite que les fourmis et l’intelligence en essaim: c'est déjà super passionnant cela dit.
Il y a d'autres exemples dans les sciences du vivant (hors génétique: juste les bébêtes et les plantes) pour un individu optimisant le problème du voyageur de commerce?

[Jeanveux]

Bon après ma petite dépression d'hier je pense pouvoir vous faire une petite démonstration elle sera par contre schématique :
Donc on prend un crayon et on trace un triangle quelconque :


[AB]= 3 ,[BC]= 6 ,[CA]= 5


Ici quel est la longueur le chemin le plus court pour aller de du point A au point B ?
Je pense qu'il n'y a pas de suspense si je vous dit le segment [AB], pour la simple raison que c'est la ligne droite !
Si on avait la bonne idée de passer par le point C pour le rejoindre le point B le chemin serait évidement plus long .

En faisant la moyenne du segment [AB] et de l'addition des segments [BC] et [CA], bien entendu la longueur du segment [AB] est en dessous de cette moyenne
on en déduit donc que pour toute longueur la plus courte ,elle doit être inférieur à la moyenne de la longueur à laquelle on la compare .

Suivant cette logique dans le problème du voyageur de commerce :

la longueur totale du chemin le plus court est = à l' addition des segments inférieur à la moyenne à laquelle on les comparent

L'algorithme va donc discriminé les valeurs qui contribuent à l'augmentation inutile de la longueur du trajet(tout en retirant les valeurs qui nous ferait repasser par les même villes
par la même .
Il ne donnera donc à la fin que les valeurs permettant de construire le chemin le plus court.

J'espère que cette démonstration vous aura convaincu !


Au passage l'algorithme que je vous est donné plus tôt est faux (ou plutôt partiellement) j'ai trouver un contre-exemple (oui oui je sais ça nous surprend tous )
Je vous enverrai la correction de l'algorithme .
J'ai tout de même bien avancé je pense grâce à vos interventions merci encore de votre temps

Cordialement

[obi76]

D'accord, et donc comment prouvez-vous que ça donne LE plus court quelque soit le nombre de points ?

Un algo qui marche pour 3 ne marche pas forcément pour 4, ni pour 50...

[Jeanveux]

Je vous les dit toute les valeurs participe à l'opération puis l'algorithme discrimine les valeurs qui sont au dessus de la moyenne
parce que si il sont au dessus de chaque moyenne il ne peuvent pas être les plus courts sa ne change pas quelque soit le nombre
de valeur . N'hésitez pas à relire ma petite démonstration

[obi76]

Je vous les dit toute les valeurs participe à l'opération puis l'algorithme discrimine les valeurs qui sont au dessus de la moyenne
parce que si il sont au dessus de chaque moyenne il ne peuvent pas être les plus courts sa ne change pas quelque soit le nombre
de valeur . N'hésitez pas à relire ma petite démonstration

Oui, mais votre démonstration marche pour 3 points. Vous ne prouvez pas que ça marche pour 4, ni pour 5, etc.

Votre démonstration, comme la dit Deedee, c'est du vu, du revu et du re-revu. Ca marche pour 3, mais pas forcément pour plus.

Une démonstration ce n'est pas "je donne un exemple qui marche avec 3, donc ça marche pour tout". Ce n'est pas non plus "ça me semble logique", ou bien "il est évident que". Là, vous ne prouvez rien du tout.

[Jeanveux]

Je ne sais pas comment vous expliqué que tout les chemins les plus court respecte la règle :

- ils sont inférieur à la moyenne avec le chemin auxquelles on les compare

c'est comme si vous me disiez que la ligne droite n'est pas le plus court chemin .

[Médiat]

c'est comme si vous me disiez que la ligne droite n'est pas le plus court chemin .

Justement, c'est le plus court chemin seulement si les deux point sont bien en face l'un de l'autre

[obi76]

Je ne sais pas comment vous expliqué que tout les chemins les plus court respecte la règle :

- ils sont inférieur à la moyenne avec le chemin auxquelles on les compare

"tous les chemins les plus courts" ça veut dire quoi ? Et on ne cherche pas "UN DES" chemin les plus court, mais LE plus court, sinon ça n'a aucun intérêt. Je ne sais pas non plus comment vous le faire comprendre.

Justement, c'est le plus court chemin seulement si les deux point sont bien en face l'un de l'autre

[Jeanveux]

Justement je sais ça je vous dit que tout les chemins les plus courts quand on fait la moyenne avec un chemin plus long se retrouve en dessous (ou égale )de cette moyenne

[Jeanveux]

Dans le problème du voyageur de commerce je vous est déjà dit qu'il y avait plusieurs chemin plus de même longueur comme c'est une boucle on peut la prendre dans les deux sens on les considère comme de chemin différent c'est même pour çaa que sur Wikipédia ( à la page du problème )il dise qu'il divise par 2