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!

[Saryk]

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.

Merci, je le saurai

[tbc92]

J'aimerais que quelqu'un m'explique cette phrase, clairement, simplement : on détermine, plutôt qu'une distance, que l'écart entre deux points correspond à un temps.

[Saryk]

J'aimerais que quelqu'un m'explique cette phrase, clairement, simplement : on détermine, plutôt qu'une distance, que l'écart entre deux points correspond à un temps.

Effectivement, ça n'a pas de sens verbatim. J'ai éditépour corriger "détermine" en "définit".
Je ne l'ai préciséque pour justifier le temps d'attente minimal avant le passage du voyageur, mais comme l'a très bien fait remarquer Emixam16, cela revient à compter la distance.

[emixam16]

Allez, je vais t'aider a construire une solution. Je l'ai fait en 2 minutes, il y a surement des points améliorables, mais ça te montre une manière de réflechir.

Étape 1: solution de base.

Je note G le point le plus à gauche, D le plus à droite et O l'origine.
3 Cas :
- La solution optimale est de faire le chemin
- La solution optimale est de faire le chemin
- La solution optimale est une autre solution.

Avec la formule que je t'ai donnée il est très simple de déterminer la meilleur solution entre les deux premières. A ce stade tu sais au moins de quel coté partir (le point m1)

La solution 3 est relativement rare car elle implique un changement de coté ce qui fait une pénalité de la distance du point jusqu'à l'origine (un deuxième changement sera nécessaire pour aller chercher les points restant).

Tu pourrais t’arrêter là et avoir une solution pas si déguelasse.

Étape 2 : Raffinement

On veut savoir quand un changement de côté sera rentable. C'est à dire que la coût est inférieure au gains en distance.

Tu peux estimer le coût => Si le changement est au point m, un changement de coté pénalisera les n-m points restants d'une distance d. S'il restait l points de ce coté, ces points devront être retraversés par la suite (comme les changements de coté sont rares et de plus en plus couteux, j'approxime qu'il n'y en a jamais plus d'un(vraisemblable)), donc je dois ajouter à la pénalité la distance d' entre le prochain point du même coté et le point le plus éloigné de l'autre coté (A ou B) multiple par le nombre de points restants de ce coté. Soit

Le gain est estimable en faisant la distance si changement de coté (d1) - la distance si pas de changement de coté (d2) * le nombre de points restants (n-m). Soit

Donc au final changement de coté ssi . Et franchement ça ne doit pas arriver tout les jours, surtout avec une distribution normale. En tout cas si ça arrivait ça serait dans les premiers points.

A toi de jouer

[tbc92]

@Saryk : ce n'est pas le verbe déterminer au lieu de définir qui m'embête, j'avais compris cette partie là comme il faut. C'est la suite qui m'embête.
De ce que je comprends, on oppose DISTANCE et ECART. On n'utilise pas la distance entre les points, mais on utilise l'écart. Et on dit que le temps pour aller d'un point à un autre est proportionnel à l'écart entre ces 2 points. En tout cas, c'est comme ça que je le comprends.
Mais pourquoi insister sur le fait qu'on n'utilise pas la distance. Pour moi Ecart ou distance, je n'arrive pas à faire la différence dans ce contexte.
Soit cette phrase cache une idée qui m'échappe, soit elle ne sert à rien. Bizarre.

Je vas partir du principe que Ecart ou distance, c'est pareil, donc que cette phrase ne sert à rien.

@emixam16.
On n'a pas 2 cas, mais 4 cas.
0 --> G --> D --> 0 ------> 0, -1, -2, -3, 3, 2, 1, 0
0 --> D --> D --> 0 ------> 0, 1, 2, 3, -3, -2, -1, 0
0 --> G --> 0 --> D --> 0 ------> 0, -1, -2, -3, 1, 2, 3, 0
0 --> D --> 0 --> G --> 0 ------> 0, 1, 2, 3, -1, -2, -3, 0

Et avec une distribution normale centrée en 0, la meilleure solution est la 3 ou la 4, pas la 1 ni la 2.
Et pour choisir entre la solution 3 et la solution 4, on va calculer max(valeurs positives) et min(valeurs negatives), ains que le nombre de valeurs positives et le nombre de valeurs négatives, et à mon avis sauf cas très atypiques, ces 4 nombres doivent suffire pour trouver le meilleur parcours.

[emixam16]

On n'a pas 2 cas, mais 4 cas.
0 --> G --> D --> 0 ------> 0, -1, -2, -3, 3, 2, 1, 0
0 --> D --> D --> 0 ------> 0, 1, 2, 3, -3, -2, -1, 0
0 --> G --> 0 --> D --> 0 ------> 0, -1, -2, -3, 1, 2, 3, 0
0 --> D --> 0 --> G --> 0 ------> 0, 1, 2, 3, -1, -2, -3, 0

Évidemment c'est aux deux derniers cas que je pensais (puisqu'on passe forcément par 0 pour aller de G à D je n'ai pas vu l'intérêt à le préciser!). Pour repréciser, quand je dis 0->G->D->0 j'entends, partir de zéro, aller jusqu'à G en passant par tous les points possible, aller vers D en passant par tous les points possible (y compris zéro) et retourner à 0 (à vide forcément).

Tes deux premiers cas sont donc compris dons mon cas poubelle "La solution optimale est une autre solution".

Et pour choisir entre la solution 3 et la solution 4, on va calculer max(valeurs positives) et min(valeurs negatives), ains que le nombre de valeurs positives et le nombre de valeurs négatives,

J'ai déjà détaillé le calcul de la meilleure solution entre les deux basiques dans mon post.

et à mon avis sauf cas très atypiques, ces 4 nombres doivent suffire pour trouver le meilleur parcours.

Ces cas sont peu courants mais pas si rare que ça non plus. Il suffit que la distance à l'origine soit d'un ordre de grandeur différent entre un sous-ensemble des points et le reste des points.

Exemple: Soient les points {{-1},{-0.1},{0.1},{1}}. Il est plus rapide de faire {0}->{-0.1}->{0.1}->{1}->{-1}->{0} que {0}->{-0.1}->{-1}->{0.1}->{1}->{0} avec les contraintes définies dans le problème.

Ce cas se présente de manière fréquente au centre de la distribution normale où on peut avoir un saut entre les points.

Mais ça tombe bien je t'ai déjà expliqué comment intégrer ce cas au raisonnement. Je n'ai pas ultra formalisé, mais je pense largement assez pour comprendre.

@Saryk Tu as tous les éléments pour résoudre ton problème, essaye de faire une implémentation

[wiwaxia]

Bonjour,

L'avis de tbc92 confirme mon impression: le problème est dès le départ mal posé.
La notion de distance euclidienne séparant deux points (1, 2), qui dans un repère orthonormé part de la relation de Pythagore

d₁₂ = ((X₂ - X₁)² + (Y₂ - Y₁)²)^1/2

devient sur un axe: d₁₂ = ((X₂ - X₁)²)^1/2 = Abs(X₂ - X₁) .

Il s'agit donc de trouver l'ordre de succession des (N) points conduisant à la valeur minimale de la somme:
S = Somme(Abs(X_j - X_i)) .
La solution est évidente: il suffit pour cela de classer la liste des abscisses selon l'ordre croissant ou décroissant, ce qui dans les 2 cas donne le même parcours total: S = 2*(X_max - X_min) .

Insérons en effet dans la chaîne deux nouveaux points points (i, j) entre deux autres (m, n) déjà ordonnés: les abscisses se présentent dans l'ordre:

X_m < X_i < X_j < X_n ;

deux possibilités se présentent alors pour la somme partielle associée:

# Sa = Abs(X_i - X_m) + Abs(X_j - X_i) + Abs(X_n - X_j) = (X_i - X_m) + (X_j - X_i) + (X_n - X_j) = X_n - X_m ,

# Sb = Abs(X_j - X_m) + Abs(X_i - X_j) + Abs(X_n - X_i) = (X_j - X_m) - (X_i - X_j) + (X_n - X_i) = (X_n - X_m) + 2*(X_j - X_i) ,

qui conduisent aux résultat inégaux: Sa < Sb .
Le minimum recherché correspond à la séquence monotone des 4 termes (X_m < X_i < X_j < X_n) .

La solution proposée est l'analogue de la suppression systématique des croisements que présente la ligne brisée du parcours dans un plan.

[tbc92]

@wiwaxia
Dans le problème classique du voyageur de commerce, l'objectif est que le temps total de la tournée soit minimum.
Ici, c'est différent. On accepte que la durée totale soit supérieure à ce minimum, ce qu'on veut minimiser, c'est la moyenne des temps de passage.

[wiwaxia]

OK, j'ai compris.
Il s'agit de trouver la séquence des (N + 1) points (origine comprise) minimisant la somme
S = Somme_k=0^N-1(N - k)*Abs(X_k - X_{k + 1})
au lieu de Somme_k=0^N-1Abs(X_k - X_{k + 1}) .

Il est possible d'établir une expression approchée de la somme en cause dans le cas d'un très grand nombre de points, et pour des séquences très particulières.
Considérons la liste des (N) points préalablement ordonnée dans le sens croissant, et son partage en 6 sous-ensembles connexes de même effectif N' = N / 6 , et délimités par 7 bornes (A₁ = X_min , A₂ , A₃ , A_{4 (très proche de l'origine O)} , A₅ , A₆ , A₇ = X_max) .

On envisage l'énumération des valeurs de chaque tranche, sans le sens croissant ou décroissant.
Chaque tranche contient (N') termes de valeur moyenne (A_t+1 - A_t)/N' ;
les coefficients correspondants varient de (N) à (5N/6) pour la première tranche, de (5N/6) à 4N/6) pour la suivants, etc ... et présentent par conséquent les valeurs moyennes successives:

( 11N/12 , 9N/12 , 7N/12 , 5N/12 , 3N/12 , N/12 )

.
On obtiendra finalement pour l'expression approchée de la somme:
S ~ (11N/12)*N'(A_i+1 - A_i)/N' + (9N/12)*N'(A_j+1 - A_j)/N' + (7N/12)*N'(A_k+1 - A_k)/N' + ...
soit finalement: S ~ (N/12)*(11*(A_i+1 - A_i) + 9*(A_j+1 - A_j) + 7*(A_k+1 - A_k) + ... +(A_n+1 - A_n)) .

On voit immédiatement la nécessité de faire intervenir en priorité les domaines les plus étroits, si l'on recherche les plus faibles sommes.
Un énumération "aveugle" de toutes les combinaisons possibles des tranches conduira à effectuer 6!*2⁶ = 46080 - ce qui est beaucoup, mais accessible.
Un distribution normale des points centrée sur l'origine se traduira par une forte concentration centrale du nuage de points: on aura donc:

(A₄ - A₃) ~ (A₅ - A₄) < (A₃ - A₂) ~ (A₆ - A₅) < (A₂ - A₁) ~ (A₇ - A₆)

;
Une somme peu élevée sera donc obtenue en introduisant prioritairement dans la combinaison linéaire:
# (T3, T4) ou (T4, T3) dans un sens ou dans l'autre, soit 2³ = 8 possibilités;
# (T2, T5) ou (T5, T2) dans un sens ou dans l'autre, soit encore 8 possibilités;
# (T1, T6) ou (T6, T1) idem donc 8 possibilités;
et pour l'ensemble des combinaisons: 8³ = 512 soit 90 fois moins qu'auparavant.

Voilà une méthode susceptible de conduire à des valeurs relativement basses, sinon optimales: on envisagera, à l'intérieur de chaque tranche, toutes les abscisses successives, dans l'ordre croissant ou décroissant.
On peut envisager plusieurs variantes, par exemple 3 tranches inférieures, d'effectifs N' = N°/3 et 3 autres d'effectifs (N - N°)/3 , la variable (N°) ne s'écartant pas trop de la valeur médiane (N/2).

La singularité de ce problème, c'est que l'existence d'une solution optimale complexe est liée à la présence d'une zone de forte concentration; une répartition uniforme des points sur l'axe admettrait comme solution triviale la suite monotone des (N) abscisses, dans le sens croissant ou décroissant.

[emixam16]

@wiwaxia Je suis désolé mais même en relisant plusieurs fois je n'ai compris à ton post. J'ai l'impression que tu ne part pas de zéro (contrainte) donc que ton explication est fausse mais peut-être ais-je mal saisi. Mais de toute façon j'ai déjà donné une solution quasi-optimale au problème!

Je vais récapituler pour que ce soit clair pour tout le monde

Je cherche comment adresser une version modifiéedu problème du commis voyageur (Travelling salesman problem en anglais)

Contraintes
- 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.
- 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.
- 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.


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

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 . (Relation 1)


Construisons une solution:

Étape 1: solution de base.

Je note G le point le plus à gauche, D le plus à droite et O l'origine.
3 Cas :
- La solution optimale est de faire le chemin
- La solution optimale est de faire le chemin
- La solution optimale est une autre solution.


A noter: quand je dis j'entends, partir de zéro, aller jusqu'à G en passant par tous les points possible, aller vers D en passant par tous les points possible (y compris zéro) et retourner à 0 (à vide forcément).

Avec la formule que je t'ai donnée il est très simple de déterminer la meilleur solution entre les deux premières. A ce stade tu sais au moins de quel coté partir (le point m1)


Cette approximation est de qualité acceptable mais pas optimale car elle ne gère pas les cas où un changement de coté est rentable, c'est à dire ou la distance à l'origine soit d'un ordre de grandeur différent entre un sous-ensemble des points et le reste des points. Ce cas se présente de manière fréquente au centre de la distribution normale.

Exemple : Soient les points {{-1},{-0.1},{0.1},{1}}. Il est plus rapide de faire {0}->{-0.1}->{0.1}->{1}->{-1}->{0} que {0}->{-0.1}->{-1}->{0.1}->{1}->{0} avec les contraintes définies dans le problème. Donc le cas 1 et 2 n'est pas toujours optimal, on doit raffiner la solution.

Étape 2 : Raffinement de la solution

On veut savoir quand un changement de côté sera rentable. C'est à dire que la coût est inférieure au gains en distance.

Tu peux estimer le coût => Si le changement est au point m, un changement de coté pénalisera les n-m points restants d'une distance d (cf. relation 1). S'il restait l points de ce coté, ces points devront être retraversés par la suite (comme les changements de coté sont rares et de plus en plus couteux, j'approxime qu'il n'y en a jamais plus d'un(c'est la seule approximation de ma réponse et elle est vraisemblable pour une distribution normale)), donc je dois ajouter à la pénalité la distance d' entre le prochain point du même coté et le point le plus éloigné de l'autre coté (A ou B) multiple par le nombre de points restants de ce coté. Soit

Le gain est estimable en faisant la distance si changement de coté (d1) - la distance si pas de changement de coté (d2) * le nombre de points restants (n-m). Soit

Donc au final changement de coté ssi (Relation 2).


Étape 3 : Construction d'algorithme qui résout le problème

On peut alors résoudre le problème avec le pseudocode suivant. (Oui, je prend les fonctions qui m'arrangent, et alors?)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
fonction genereSolution(Point[] points)
| (triéNégatif, triéPositif) = monSuperTri(points) // triéNégatif contient les points triés de 0 à -min. triéPositif contient les points triés de 0 à max.
| Solution1 = genereSolution(triéNégatif + triéPositif) // le + concatène les ensembles
| Solution2 = genereSolution(triéPositif triéNégatif )
| bestSolution= max(Solution1.getScore(), Solution2.getScore()) // getScore utilise la relation 1.
| 
| firstPointOtherSide = bestSolution.firstPointOtherSide() 
| for( i in 0 : bestSolution.lenghtSideDeparture()-1)
| | if( bestSolution.crossoverScore() > bestSolution.noCrossoverScore()) // Utilise la relation 2
| | | bestSolution.applyCrossover() // On fait un changement de coté donc on réorganise bestSolution (le point i+1 est le premier point restant de l'autre coté, le point i+2 est le 2ème point restant de l'autre coté et ainsi de suite)
| return bestSolution

J'espère être clair

Bonne journée.

[wiwaxia]

J'ai proposé une solution à un problème intéressant, qui me paraissait inédit.
L'expression approchée de la somme fait ressortir le rôle de l'accumulation des points dans la partie centrale, et débouche sur un algorithme; il serait intéressant de le tester.

Je ne conteste en rien la validité de ton procédé, et son aptitude à produire un meilleur résultat.

PS: Je me soucie généralement peu du temps d'exécution des programmes (quoique je ne pousse pas l'inconscience jusqu'à entreprendre N! calculs), et j'ai repensé à la demande initialement exprimée:

- 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.

La somme est ici calculée sur 6 blocs de frontières prédéterminées: le temps d'exécution est donc proportionnel à (N) - Ouf !
L'algorithme glouton évoqué ne paraît pas dépourvu d'intérêt, mais le critère de choix n'est pas assez étendu: c'est une option qu'il conviendrait d'examiner de plus près. Le temps de calcul, ici proportionnel à (N²), est probablement plus long..