Methode problèmes NP complets

par **leafar** » 24 Sep 2015, 18:01

Bonjour,

Voici une approche pour le problème du voyageur de commerce

L'algorithme suit ces étapes :

* superposer au « nuage » de points représentant les villes, une spirale particulière
* placer le centre de cette spirale sur le centre de gravité du nuage de points,
* puis de la faire tourner afin de minimiser la « rugosité » (voir détails)
* effectuer une détection des « amas », à partir de 4 étoiles ou plus.
* Traiter récursivement l'amas comme sous-problème.
* Rattacher l'amas selon la méthode des plus proche récursive: apparition automatique de deux bras spirales dans l'amas inclus dans un super-amas...
* Détection et traitement des cas « d'accrétion » haute et basse entre un bras et l'autre.

Le document joint comporte 24 pages, un algorithme détaillé, des considérations mathématiques, force schéma

[URL=
http://www.les-mathematiques.net/phorum ... download=1]Doc PDF ici[/URL]

J'espere qu'il retiendra l'attention de certains d'entre vous.

Je serai heureux de pouvoir en discuter avec quelqu'un.

Très cordialement

PS : la phase d'initialisation (rotation spirale en minimisant rugosite n'est peut être pas de complexité linéarisable, mais pas exorbitante non plus )

par **Mario2015** » 24 Sep 2015, 20:03

Salut,

Si je peux me permettre un bref commentaire, je dirai la chose suivante :
Quand on affronte ce genre de probleme (et autres similaires), il faut trouver un moyen simple de calculer exactement ou de manirer tres rapprochee (uper bound-lower bound aussi epsilonien que possible). Une fois que l`on connait la valeur de cet optimum (voire de la minimalite du circuit), il devient tres facile de l`obtenir par convergence.

J`ai k points repartis dans un espace a 2 dimensions, je dois relier tous ces points en passant une seule fois par les k points. Si je connais la distance minimale mon probleme est en grande partie resolu. Si je ne la connais pas, je ne peux que raisonner en termes de "progres" : ce chemin obtenu a l`instant t est plus court que celui obtenu a l`instant t-1. Etc....

Moi, j`ai trouve que la solution de ce probleme de commerce est plus simple a obtenir si on utilisait une machine physique qui exploite les forces gravitationnelles.

Cela dit, il faut jeter un coup d`oeil ici :

http://www.math.uwaterloo.ca/tsp/problem/index.html

Tres instructif.
Je solutionne un circuit de 50 villes en moins de 10 minutes.
Je solutionne dans le cas dont je parle est que j`atteins leur minimum en moins de 10 minutes.
Amusez-vous a jouer c`est tres eclairant sur la nature du probleme.

C`est un probleme NP disent-ils : pour moi c`est un gros mythe entretenu par les mathematiciens.
On decouvrira dans les annees a venir que beaucoup de problemes sont plus faciles a resoudre si on adopte la bonne approche.
Que de problemes mathematiques seront resolus quand on etudiera mieux la biologie et la physique.

par **lulu math discovering** » 24 Sep 2015, 21:34

Quand à ce problème là, je vous conseille de vous intéresser aux mathématiques savonneuses

par **Mario2015** » 24 Sep 2015, 22:11

lulu math discovering a écrit:Quand à ce problème là, je vous conseille de vous intéresser aux mathématiques savonneuses

Je ne sais pas comment te remercier quoique mon idee de machine physique soit basee sur des principes autres.
Je vais lire cet article attentivement, peut-etre m`aidera-t-il a mieux preciser mon idee.

Mille mercis!!!

par **Mario2015** » 24 Sep 2015, 22:24

Mon idee remonte a fevrier 2012 donc bien apres la publication de cet article.
Le materiel de base au depart c`etait une ficelle et des clous (les clous representent les villes et la ficelle le chemin). L`idee a evolue depuis, vers quelque chose de plus sophistique. Au point qu`un manipulateur humain aide par une puissance de calcul peut resoudre en une journee le chemin d`un reseau de 10.000 villes et plus.

Encore une fois merci!

Principe similaire de solution pour le probleme celebre du sac a dos.
Une autre machine la aussi.

par **Robot** » 24 Sep 2015, 22:32

Je vois que leafar n'annonce plus à grands coups de trompette "la résolution linéaire des problèmes NP-complets" comme il l'a fait sur le forum les-mathématiques.net. Le commencement de la sagesse ?

Quand a Mario2015, il ne comprend pas que "le gros mythe entretenu par les mathématiciens", à savoir le problème P=NP, est un vrai problème ouvert de théorie de la complexité, un vrai problème ouvert de mathématiques, et que trouver en temps polynomial des solutions approchées au problème du voyageur de commerce est une histoire différente.

par **Mario2015** » 24 Sep 2015, 22:53

Robot a écrit:Je vois que leafar n'annonce plus à grands coups de trompette "la résolution linéaire des problèmes NP-complets" comme il l'a fait sur le forum les-mathématiques.net. Le commencement de la sagesse ?

Quand a Mario2015, il ne comprend pas que "le gros mythe entretenu par les mathématiciens", à savoir le problème P=NP, est un vrai problème ouvert de théorie de la complexité, un vrai problème ouvert de mathématiques, et que trouver en temps polynomial des solutions approchées au problème du voyageur de commerce est une histoire différente.

Merci pour les precisions.
J`en tiendrai compte.
Mais avant je tiens a dire une chose : sur quoi se base les mathematiciens pour dire qu`un probleme est NP? Moi je le dis tout : ils se basent leur propre ignorance.
Projette-toi un peu dans le temps. Dans quelques siecles peut-etre les enfants du primaire pourraient te lister les nombres premiers comme aujourd`hui ils listent les nombres entiers naturels 1,2,3,4..............n etc...
La communaute mathematique m`ulcere!!!!
Elle agit comme une secte ou presque.
Le fonctionnement de l`univers physique et non physique est surement regi par des principes tres simples que nous bipedes ignorons.
Allez! Je retourne a mes moutons avant de devenir desagreable.

par **Robot** » 24 Sep 2015, 23:05

Mario2015 a écrit:sur quoi se base les mathematiciens pour dire qu`un probleme est NP? Moi je le dis tout : ils se basent leur propre ignorance.

Ils se basent sur une définition précise d'une classe de complexité. Tu peux voir ici. Et quand ils affirment qu'un problème (comme celui du voyageur de commerce ou le problème SAT) est NP-complet, c'est qu'ils ont démontré un théorème à cet effet.
Tu parles sans savoir et accuses les mathématiciens de ton propre défaut : l'ignorance. C'est ridicule.
Apprends un peu de théorie de la complexité si tu veux arrêter de balancer des stupidités sur le sujet.

par **Mario2015** » 24 Sep 2015, 23:30

Mais oui! On se base toujours sur des definitions precises puis quelques annees plus tard tout le systeme est chamboule!
Les mathematiques comme la physique d`ailleurs c`est du grand blabla organise reposant sur une theorie ou la principale preoccupation est de ne pas se contredire.
C`est toujours juste jusqu`a cela devienne faux.
Que de theories se sont ecroulees depuis que l`homme existe.
Faire plus simple, les mathematiciens l`ignorent.
Ils sont toujours la a construire un edifice "abstrait" ou ils sont les seuls a pouvoir frequenter.
Les mandarins du 21eme siecle!!!
Les pharaons je dirai.
Aucun homme n`est autre chose que bipede.
Nous faisons tous caca et nous finirons tous par crever.
De extra-terrestres sont en train de pisser de rire maintenant a voir notre ignorance (la mienne et celle des mathematiciens dits les "plus avances" (ce mot me fait rire.

Je suis hors-sujet mais il me fallait sortir mes modestes pensees.
C`est fait.

par **Robot** » 24 Sep 2015, 23:35

:ptdr: Pathétique.

par **Mario2015** » 25 Sep 2015, 00:17

Robot a écrit::ptdr: Pathétique.

Ce qui est surement pathetique, c`est l`etat des mathematiques a ce jour.
Bref, je m`arrete la.

par **Doraki** » 25 Sep 2015, 02:04

C`est toujours juste jusqu`a cela devienne faux.

o_____________o

par **Sylviel** » 25 Sep 2015, 16:29

La communaute mathematique m`ulcere!!!!

Pourquoi venir sur un forum de maths alors ?

Dire qu'un problème est NP c'est dire que si on sait le résoudre en temps polynomial alors on sait résoudre tous les problèmes de la classe NP en temp polynomial. Ce n'est pas dire qu'il n'est pas possible de résoudre le problème en temps polynomial...

par **Robot** » 25 Sep 2015, 17:17

P veut dire "Polynomial", c.-à-d. qui peut être résolu en temps polynomial par une machine de Turing déterministe.
NP veut dire "Nondeterministic Polynomial", c.-à-d. qui peut être résolu en temps polynomial par une machine de Turing non déterministe. Ca peut aussi se définir comme la classe de problèmes dont une solution peut être vérifiée en temps polynomial par une machine de Turing déterministe.
On a bien sûr P contenu dans NP. Le problème de savoir si P=NP est ouvert. Pratiquement tout le monde pense que P est différent de NP, mais personne n'en a la preuve. L'Institut Clay a mis le problème P=NP ? dans la liste de problèmes ouverts en mathématiques pour la solution desquels il offre un million de dollars.

Un problème A est NP-complet s'il est dans la classe NP et si tout problème B dans la classe NP peut se ramener à A en temps polynomial (à l'aide d'un oracle donnant la solution à A, on peut résoudre B en temps polynomial par une machine de Turing déterministe). Il a été prouvé que le problème du voyageur de commerce est NP-complet.
Si on montrait qu'un problème NP-complet est dans P, on aurait montré que P=NP.

par **lulu math discovering** » 25 Sep 2015, 17:23

Mais oui! On se base toujours sur des definitions precises puis quelques annees plus tard tout le systeme est chamboule!

Aujourd'hui, ça risque pas, même les axiomes mathématiques ont été démontrés.

par **Doraki** » 25 Sep 2015, 17:23

Robot a écrit:Il a été prouvé que le problème du voyageur de commerce est NP-complet.

J'croyais qu'on savait seulement qu'il était NP-difficile ?
C'est facile de vérifier qu'un parcours donné à une longueur donnée, mais c'est beaucoup plus dur de montrer que c'est vraiment le parcours le plus court.

par **lulu math discovering** » 25 Sep 2015, 17:25

Il y a plusieurs sortes de NP ? :doh:

par **Sylviel** » 25 Sep 2015, 17:31

@lulu : oui il y a plusieurs sorte de NP (jette un oeil sur le net). Et on ne peut pas "démontrer les axiomes". Les axiomes sont des choses desquelles on part pour montrer tout le reste...

par **Doraki** » 25 Sep 2015, 17:32

il y a les problèmes qui sont dans NP,
les problèmes qui sont NP-difficiles (qui ne sont pas forcément NP), pour lesquels n'importe quel problème NP a une réduction polynomiale vers ce problème.
Et les problèmes NP-complets, qui sont les problèmes NP-difficiles qui sont NP eux-même.

par **lulu math discovering** » 25 Sep 2015, 17:39

D'accord merci.

Sinon, il me semble que certains (tous ça m'étonnerait) axiomes mathématiques ont été démontrés grâce à de la logique "pure".

Methode problèmes NP complets

Methode problèmes NP complets

Qui est en ligne