"P = NP ? " La recherche d'un algorithme
Discussion fermée
Page 1 sur 4 12 3 DernièreDernière
Affichage des résultats 1 à 30 sur 96

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



  1. #1
    Jeanveux

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


    ------

    Bonjour à tous ,


    Tout d'abord j'espère que je poste bien dans la bonne section mes excuses si ce n'est pas le cas .
    Alors voilà, ayant récemment décidé de me lancé dans la recherche d'une preuve capable de prouvé une égalité concernant l'un des problèmes du millénaire
    "P = NP ?", j'ai décidé de m'attaquer à un problème dit NP-Complet (la résolution d'un seul de ces problèmes en temps polynomiale garantissant l'égalité). J'ai donc trouvé un algorithme , que j'aimerais testé . Le problème concerner est celui du voyageur de commerce
    Je ne sais pas si la charte m'autorise à poster cette algorithme je pourrais éventuellement le donner par message privé .
    En attendant voici mes questions :

    - comment tester moi même le dit algorithme ( quels outils utiliser sachant que je n'ai aucune véritable notion de codage) toute aide à ce sujet est la bienvenue .

    - en admettant que l'algorithme soit exacte, s'envoyer une lettre recommander est t'il toujours valide pour prouvé sa paternité ?

    - toujours en admettant que le dit algorithme soit exacte, dans quel genre de revue publier le résultat ( dans quel catégorie des mathématiques ?)

    Je précise que je cherche à mettre en échec cette algorithme (si c'est possible)

    Merci d'avance pour votre temps et pour vos réponse .

    -----

  2. #2
    obi76

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

    Bonjour,
    Pour la paternité, une publi fait l'affaire. Pour le journal, ça dépend, mais de mon côté je viserait plutôt l'analyse numérique ou des journaux d'algorithmique.

    Vous pouvez donner la méthode en question ? Si elle marche (très peu probable je ne vous le cache pas) je veux bien la coder si vous voulez. Inutile de s'embêter si on voit que l'algo n'est pas polynomial. Le coder c'est une fois qu'on est sûr que ça marche. Personnellement je pencherai sur du F90 : c'est simple et rapide.

    Édit : de toutes façons un algo n'est pas deposable...
    Dernière modification par obi76 ; 15/09/2020 à 17h31.
    \o\ \o\ Dunning-Kruger encore vainqueur ! /o/ /o/

  3. #3
    Jeanveux

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

    Merci pour votre réponse, voici l'algorithme :

    - Choisir une ville de départ
    - Ranger par ordre croissant les distances reliant à cette ville
    - Prendre la médiane
    - Comparer chaque distance à la médiane
    - Prendre toute les distances inférieurs ou égale à la médiane
    - Recommencer
    - Relier les villes qui était égale à la médiane lors de l’opération mais au dessus dans celle en cours

    J'espère m'être correctement exprimer j'ai déjà tester l'algorithme à la main il fonctionne normalement

    Je donnerai un exemple si nécessaire .
    Dernière modification par Jeanveux ; 15/09/2020 à 18h39.

  4. #4
    obi76

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

    Je veux bien un exemple oui.

    Mais par contre je ne vois pas comment vous pouvez prouver que le trajet obtenu est LE plus court... (D'ailleurs est-ce toujours le cas ? J'en doute...)
    Dernière modification par obi76 ; 15/09/2020 à 18h56.
    \o\ \o\ Dunning-Kruger encore vainqueur ! /o/ /o/

  5. A voir en vidéo sur Futura
  6. #5
    Médiat

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

    Citation Envoyé par obi76 Voir le message
    Je veux bien un exemple oui.
    +1

    Mais par contre je ne vois pas comment vous pouvez prouver que le trajet obtenu est LE plus court... (D'ailleurs est-ce toujours le cas ? J'en doute...)
    +1

    Et je précise qu'aussi efficace que soit cet algorithme, il ne pourra être lié au problème P = NP qu'à la condition express d'avoir cette démonstration (sans démonstration, et même si ce n'est pas le plus court dans 100% des cas, il peut servir dans la pratique, ce n'est déjà pas si mal)
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  7. #6
    Liet Kynes

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

    Citation Envoyé par Médiat Voir le message
    Et je précise qu'aussi efficace que soit cet algorithme, il ne pourra être lié au problème P = NP qu'à la condition express d'avoir cette démonstration (sans démonstration, et même si ce n'est pas le plus court dans 100% des cas, il peut servir dans la pratique, ce n'est déjà pas si mal)
    Bonjour, sera t-il pour autant énonçable en tant que conjecture dans le cas d'une application pratique?

  8. #7
    jacknicklaus

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

    Citation Envoyé par Jeanveux Voir le message
    J'espère m'être correctement exprimer j'ai déjà tester l'algorithme à la main il fonctionne normalement
    J'avoue ne pas avoir compris votre algorithme. C'est assez obscur.

    Citation Envoyé par Jeanveux Voir le message
    Je donnerai un exemple si nécessaire .
    +1
    There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.

  9. #8
    Jeanveux

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

    Je vais faire plus simple que point par point :

    -On prend une instance composé de 4 point ,[AB] = 100, [BC ]=3 ,[CD] =20 ,[DA] = 37,[DB] (la diagonale)=1104 ,[AC](l'autre diagonale)= 15

    -On range les distance par ordre croissant soit 3<15<20<37<100<1104

    -On prend la médiane soit 213,16

    -On choisi la première valeur inférieur à la médiane ou égale ici 100 (dans le cas où le nombre totale de valeur est pair, la valeur du millieu dans les cas impair)

    (les valeurs que l'on relie sont sont la médiane et les point qui était en dessous de la médiane précédente mais au dessus lors de l'opération précédente sauf pour la dernière opération )

    -On recommence à partir du point 3 (prendre la médiane )

    le chemin le plus court est normalement l'addition 3 + 20 + 37 + 100 =160

    la vrai question est est-il possible de trouver un chemin qui passe par toute les villes et qui soit de longueur inférieure à L ?( qui est la version décisionnel du problème,à laquelle mon algorithme est censé répondre )

    Il suffit de regarder si le chemin trouver passe bien une seul fois par toute les villes et est bien de longueur inférieur au chemin L
    Dernière modification par Jeanveux ; 15/09/2020 à 20h25.

  10. #9
    gg0
    Animateur Mathématiques

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

    Attention,

    213,16 est la moyenne des trois valeurs, pas "la" médiane (ici, toute valeur entre 20 et 37 est une médiane).

    Plus embêtant : Il n'existe pas 4 villes ayant ces distances là ! Si DB=1104, alors DA >= DB-BA =1104-100 = 1004.

    Enfin, je n'ai rien compris à "(les valeurs que l'on relie sont sont la médiane et les point qui était en dessous de la médiane précédente mais au dessus lors de l'opération précédente sauf pour la dernière opération ) "

    Cordialement.

  11. #10
    Jeanveux

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

    Je me suis certainement trompé sur 1104 (je fais la chose de souvenir ma feuille étant passer à la poubelle), je voulais dire que lorsque que l'on ne peux pas prendre la médiane par convention on fait la moyenne (selon le livre que j'ai entre les mains),puis on prend la première valeur inférieur à cette moyenne.Comme n-1 on ne fait pas la dernière opération.
    Dernière modification par Jeanveux ; 15/09/2020 à 20h56.

  12. #11
    gg0
    Animateur Mathématiques

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

    "lorsque que l'on ne peux pas prendre la médiane par convention on fait la moyenne (selon le livre que j'ai entre les mains)" ???
    Soit tu as un livre idiot, soit tu n'as pas lu ce qu'écrit le livre. Tu t'es arrêté au milieu d'une phrase !!

    Et évite les phrases incohérentes genre "Comme n-1 on ne fait pas la dernière opération." n-1 n'est pas une circonstance !!
    D'ailleurs ce n'est pas la fin de ta phrase ("sauf pour la dernière opération") qui me pose problème (ça, j'avais compris), mais la phrase entière.
    Ce serait mieux si tu essayais de t'exprimer en français. Avec des phrases construites pour être lues par ceux qui ne savent pas ce qu'il y a dans ta tête (tout le monde sauf toi). Et même s'il faut en écrire plus.

    Cordialement.

  13. #12
    Médiat

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

    Une première question : pouvez-vous préciser les contraintes (il y a plusieurs version de ce problème (début et fin imposés ou non, passage unique dans chaque ville ou non ...))

    Le chemin ACBCDA coute 15+3+3+20+37=78
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  14. #13
    Deedee81

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

    Salut,

    De toute façon, préciser exactement cet algorithme et vérifier qu'il donne un résultat n'est pas le plus difficile. Le plus dur sera de démontrer que cet algorithme donne bien le chemin le plus court parmi tous les chemins possibles. Et on sait bien que c'est là que le bât blesse avec tous les algorithmes de voyageur de commerce. Et pire encore, ça doit pouvoir être démontré formellement (mathématiquement) et pas avec des exemples.

    En fait trouver des algorithmes de recherche est souvent le plus facile.

    Par contre une fois l'algorithme vraiment clair, il peut être relativement aisé de trouver un contre-exemple s'il en existe.
    "Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)

  15. #14
    obi76

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

    Citation Envoyé par Deedee81 Voir le message
    Par contre une fois l'algorithme vraiment clair, il peut être relativement aisé de trouver un contre-exemple s'il en existe.
    Dans ce cas il est clair qu'il est généralement plus simple de trouver un contre-exemple et donc d'invalider la démarche que de démontrer que ça marche tout le temps
    \o\ \o\ Dunning-Kruger encore vainqueur ! /o/ /o/

  16. #15
    Deedee81

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

    Citation Envoyé par obi76 Voir le message
    Dans ce cas il est clair qu'il est généralement plus simple de trouver un contre-exemple et donc d'invalider la démarche que de démontrer que ça marche tout le temps
    Une fois qu'on aura un algo clair et précis en tout cas

    si on échoue alors à trouver un contre-exemple il devient intéressant de chercher à démontrer formellement la validité. C'est pas gagné (surtout que je suis de ceux qui pensent que P est différent de NP, comme la majorité d'ailleurs mon principal argument étant le caractère clairement combinatoire de certains problèmes NP complets sans indices disant qu'on pourrait faire mieux).
    "Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)

  17. #16
    jacknicklaus

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

    Citation Envoyé par gg0 Voir le message

    Plus embêtant : Il n'existe pas 4 villes ayant ces distances là ! Si DB=1104, alors DA >= DB-BA =1104-100 = 1004.
    Je ne pense pas que ceci ait une importance. Rien ne dit que le chemin d'un point A à un point B soit en ligne droite.
    There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.

  18. #17
    gg0
    Animateur Mathématiques

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

    Heu ... le trajet de D à B en passant par A fait 137, d'où peut provenir le 1104 ?

    Dans le problème du voyageur de commerce, on suppose, bien entendu, qu'on prend les trajet le plus court (suivant le moyen de transport) d'une ville à l'autre, pas qu'on fait des détours par Pétaouchnok.

    Cordialement.

  19. #18
    Médiat

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

    Et la mesure peut-être en unités de temps...

    Mais gg0 a raison sur un point, si l'inégalité triangulaire n'est pas respectée, alors un des côtés sera systématiquement ignoré
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  20. #19
    Médiat

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

    Citation Envoyé par gg0 Voir le message
    Heu ... le trajet de D à B en passant par A fait 137, d'où peut provenir le 1104 ?
    Une route en travaux, ou pas d'avion direct entre ces deux villes : obligé de prendre son vélo, etc. il y a des centaines d'explications possibles
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  21. #20
    Deedee81

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

    Citation Envoyé par gg0 Voir le message
    pas qu'on fait des détours par Pétaouchnok.
    Et si une des villes est Pétaouchnok ???
    "Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)

  22. #21
    jacknicklaus

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

    Citation Envoyé par gg0 Voir le message
    Heu ... le trajet de D à B en passant par A fait 137, d'où peut provenir le 1104 ?
    Eh bien, avec par exemple 3 points A B C, je peux tout à fait faire un AB = 1, BC = 1, (donc trajet AC = 2 "via" B), et une route "directe" AC = 10, car elle fait de beaux zigs-zags dans la campagne... Si la problème inclut une interdiction de passer deux fois au même endroit, ce qui est le cas dans le problème du voyageur de commerce, le trajet "direct" AC ne doit pas être écarté à priori.
    There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.

  23. #22
    Médiat

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

    Citation Envoyé par jacknicklaus Voir le message
    Si la problème inclut une interdiction de passer deux fois au même endroit, ce qui est le cas dans le problème du voyageur de commerce, le trajet "direct" AC ne doit pas être écarté à priori.
    Ce qui est le cas du problème théorique usuel, mais qu'un vrai voyageur de commerce ne fera jamais (et il y pire, si les trajets se font en train et que Briançon est dans la liste, il n'y a pas de solution sans passer deux fois dans la même ville).
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  24. #23
    gg0
    Animateur Mathématiques

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

    Effectivement,

    en tordant le problème de base (obligation d'utiliser un trajet), la proposition avec 1104 devient possible.

    Bon, tout ça manque un peu de sérieux !!

  25. #24
    Médiat

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

    En tout état de cause, peu importe les exemples (sauf à titre pédagogique), le seul point qui compte est l'algorithme, et ne pense pas être le seul à ne l'avoir pas compris
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  26. #25
    Deedee81

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

    A noter un tout petit couac (heu, enfin, quand je dis "un"). Si la méthode dit "relier A à B" il n'est pas exclu que ça passe par C. Evidemment, ça ne peut pas empirer le résultat sauf que ça peut vachement compliquer l'algorithme car il faut chaque fois vérifier si on ne passe pas par un autre point pour ne pas y passer deux fois. C'est Jacknicklaus qui m'y a fait penser. L'algorithme peu clair ou pas ne traite pas du tout cette difficulté.

    P.S. et non, je crois que personne n'a vraiment compris l'algorithme.

    P.S.2 Jeanveux n'est plus rapassé mais il ne se connecte peut-être que fin de journée.
    "Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)

  27. #26
    jacknicklaus

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

    Citation Envoyé par gg0 Voir le message
    en tordant le problème de base (obligation d'utiliser un trajet), la proposition avec 1104 devient possible.
    En fait, un point était clair depuis le début : un seul passage par chaque ville, ce qui est conforme au problème classique https://fr.wikipedia.org/wiki/Probl%...a%20ville%20de

    en effet :

    Citation Envoyé par Jeanveux Voir le message
    Il suffit de regarder si le chemin trouver passe bien une seul fois par toute les villes [...]
    Cette précision cruciale permet, à priori, d'utiliser n'importe quelle "distance" entre deux villes.


    Sinon, moi, j'ai toujours rien compris à l'algorithme proposé.
    There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.

  28. #27
    Deedee81

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

    Citation Envoyé par jacknicklaus Voir le message
    Sinon, moi, j'ai toujours rien compris à l'algorithme proposé.
    Attendons qu'il repasse. En 24h il aura bien trouvé le temps de rédiger un algo précis et clair (c'est faisable puisqu'il le teste "à la main", faut juste le rédiger clairement)
    "Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)

  29. #28
    Jeanveux

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

    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)

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

    Si Oui ( si Non on prend la valeur inférieur)

    - On prend la valeur au-dessus de cette moyenne ici 20 ( on reprend ensuite à l'étape 5)

    - On reprend de les valeurs de la plus petite à la valeur prise (20)

    - On prend la médiane puisque le nombre de valeur est impaire ici 15

    - On prend la valeur inférieur ici 3

    fin

    On additionne les valeurs noter 100 + 37 + 20 + 3 = 160

    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

    La question de la version décisionnelle est :

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

    Si on ne peux pas trouver de chemin de longueur inférieur à L c'est que ce chemin (L) est le plus court.
    Seulement si on trouve un algorithme en temps polynomiale capable de trouver un chemin plus court (respectant les règles)c'est que le chemin de
    longueur L est plus long,donc en utilisant l'algorithme on peux répondre par oui ou non résolvant le problème NP-Complet.

    Avec mon algorithme si une seul valeur de composant la longeur totale L n'est pas retenu alors l'algorithme est censé s'arrêter et répondre que
    oui il est possible de trouver un meilleur chemin si l'algorithme arrive à la fin alors il n'est pas possible de trouver meilleur chemin.
    (si j'ai bien compris ça voudrais dire que cette algorithme serait la preuve que ce chemin est bien le (l'un des) plus court dans la version traditionnelle du problème)

    D'après vous l’algorithme proposé est-il polynomiale ?
    L'algorithme fonctionne t'il quelque soit l'instance ? (donc de façon générale)
    Le chemin trouver par l'algorithme respecte t'il bien toute les règles quels que soit l'instance?(Ne passer qu'une seul fois par ville et par toute les villes )

    J'ai personnellement souvent des doutes sur la dernière question.

    Vous pouvez tester l'algorithme sur ce problème (exemple tiré de Wikipédia problème du voyageur de commerce ):

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

    Le meilleure chemin est de longeur 7

    PS : ATTENTION !!! Quand on tri par ordre croissant les valeurs de même longueur, compte pour une dans l'exemple de wikipédia
    il y a 2 valeur de longeur 1 il ne faut les compter que pour une seule.
    J'ai tester sa fonctionne je donnerai une correction si vous n'y arriver pas.

    J'espère avoir été plus claire, merci pour votre temps et vos réponse.



    Cordialement

  30. #29
    DavianThule95

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

    Y'a peut être quelque chose que j'ai pas compris, mais tu dis :

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

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

    Sauf que [DB] <= [DA] + [AB], donc [DB] <= 37 + 100 = 137. 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.
    Je dis ça je dis rien mais j'le dis quand même.

  31. #30
    Jeanveux

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

    Si j'ai bien compris ce n'est pas une norme d'après moi

Page 1 sur 4 12 3 DernièreDernière

Discussions similaires

  1. Programmer un site avec un ""ALGORITHME"" qui parcourt plusieurs site pour afficher des resultats
    Par invite8481e418 dans le forum Programmation et langages, Algorithmique
    Réponses: 5
    Dernier message: 11/08/2018, 16h45
  2. VB mettre le micro en mode " ecoute" "veille" et "stop" sous visual basic
    Par invite5ea368ff dans le forum Programmation et langages, Algorithmique
    Réponses: 1
    Dernier message: 14/12/2015, 13h45
  3. excipients: recherche de definition "véhicule" et "base"
    Par invite7a05ec5e dans le forum Santé et médecine générale
    Réponses: 0
    Dernier message: 27/03/2012, 20h54
  4. recherche composant qui peut "attraper" et "lâcher"
    Par invitef22c7fa3 dans le forum Électronique
    Réponses: 11
    Dernier message: 17/08/2009, 20h01