Méthode pour voyageur de commerce

[leafar]

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… )

[fatal_error]

hello,

as-tu des benchmarks pour comparer ta méthode avec les autres?