Discussion :

[Saryk]

Bonjour,

Je cherche comment adresser une version simplifiée du problème du commis voyageur (Travelling salesman problem en anglais), qui, plutôt que de chercher les chemin le plus court entre des points sur un plan, cherche le chemin le plus rapide passant par tous les points sur un axe. Il y a 1000 points, et suivent une distribution normale centrée en 0. Chacun est représenté par un float, positif ou négatif.

L'objectif est d'avoir un algorithme optimisé, mais je ne connais rien en optimisation. Auriez-vous des pistes ?

[emixam16]

Bonjour,

Quelles sont les contraintes de ton problèmes?

Car si il n'y en à pas, partir de la ville la plus à gauche aller linéairement jusqu'à la ville la plus droite à droite est une solution trivialement optimale (Preuve: il est difficile d'aller plus rapidement d'un point A à un point B qu'avec une ligne droite... Et A et B doivent être visitées... Donc optimal ).

Mais peut-être y-a-t-il des subtilités supplémentaires ?

[Saryk]

J'ai effectivement omis de préciser les contraintes :
- on part du 0 et on revient au 0.
- on définit, plutôt qu'une distance, que l'écart entre deux points correspond à un temps.
- on veut que la moyenne du temps d'attente de chaque point avant le passage du voyageur soit le plus court possible.
- solution algorithme polynomial (ce dont je ne saisis pas trop le sens).
- doit être 85% plus rapide qu'un algorithme glouton (soit aller au point le plus proche à chaque étape), en moyenne sur plusieurs tests.

[emixam16]

Pour ta question sur la complexité : si ton algorithme explore toutes les possibilités ici, s'il y n points, tu as cas. (Par exemple avec 5 : 5*4*3*2*1). On dit de complexité exponentielle. Au contraire si tu prend un autre algorithme qui fait au maximum opérations avec les k des constantes alors l'algorithme sera quadratique (la plus grande puissance de n est 2) donc polynomial. Wikipédia explique ça très bien.

Si la vitesse du voyageur est constante (ce qui est probablement le cas), Alors minimiser la distance est équivalent à minimiser le temps (puisque ). Dans la suite je parle en terme de distance mais peu importe.

J'ai effectivement omis de préciser les contraintes :
- on part du 0 et on revient au 0.
- on veut que la moyenne du temps d'attente de chaque point avant le passage du voyageur soit le plus court possible.

Cette partie du message est la partie importante, et que je ne pouvais pas deviner .
Je note la distance pour aller du point n-1 à n avec un chemin particulier

Si je prends un point m, la distance totale parcourue pour aller à ce point depuis le départ du voyageur est

Tu veux minimiser le temps moyen donc la distance moyenne donc soit soit ...

J'ai formalisé ton problème, je te laisse le résoudre pour que tu apprennes aussi (je suis là si tu as des questions)

(Dans ce genre de cas la première question à te poser est ais-je besoin d'un algorithme optimal ou une bonne approximation est elle suffisante. Si oui, quand puis-je considérer mon approximation comme suffisante?)

[Saryk]

Merci, ça aide beaucoup

Si je prends un point m, la distance totale parcourue pour aller à ce point depuis le départ du voyageur est

Si je comprends bien, on cherche donc à ordonner les points de façon à ce que (ou donc ) soit minimal.

EDIT : les "1000" s'affichent mal :/

Un algorithme exhaustif ferait toutes les permutations, soit opérations, et ce n'est clairement pas envisageable.
Je suppose aussi qu'il n'y a pas d'algorithme optimal en toutes circonstances ; dans le sens de ça doit dépendre de la configuration de départ.
Je ne sais cependant pas répondre aux questions sur les approximations

[dourouc05]

EDIT : les "1000" s'affichent mal :/

Juste une histoire de syntaxe LaTeX : quand tu mets plus d'un caractère en indice ou exposant, il faut marquer le début et la fin, donc d_{1000} au lieu de d_1000.

[emixam16]

En Latex Si tu veux afficher des blocs tu les met en crochet: par exemple x_{1000} donne . Sinon seul le 1er nombre est pris. (Edit: grillé )

Merci, ça aide beaucoup

Si je comprends bien, on cherche donc à ordonner les points de façon à ce que (ou donc ) soit minimal.

C'est exactement ça!

Un algorithme exhaustif ferait toutes les permutations, soit opérations, et ce n'est clairement pas envisageable.

Oui, je ne l'ai pas précisé mais pour des raisons évidentes tu ne t'en sortira pas en testant toutes les combinaisons (les joies de l'exponentiel).

Je suppose aussi qu'il n'y a pas d'algorithme optimal en toutes circonstances ; dans le sens de ça doit dépendre de la configuration de départ.

Si, il y a bien évidemment des algorithmes te donnant le résultat optimal. Exemple: Générer et tester toutes les combinaisons. Il faut juste un temps quasi-infini pour le faire tourner (environ combinaisons), mais c'est optimal. Ton travail c'est de trouver un algorithme plus intelligent qui te fasse arriver au même résultat (ou à une bonne approximation si on te l'autorise) en un temps plus ... humain!