Pourquoi le TSP n'exige-t-il aucune répétition des villes?

9

Il me semble étrange que le TSP nie la possibilité de villes répétées. Le but de ce vendeur itinérant est d'aller le plus vite possible et de visiter toutes les villes, non? Que se passe-t-il s'il est plus rapide de traverser une ville dans laquelle vous êtes déjà allé?

terminology traveling-salesman danmcardle
la source

2

Je suis sûr que c'est arbitraire. Ce n'est que dans de rares cas que permettre des villes répétées ferait une différence (jamais dans le TSP métrique). Les problèmes ne sont donc guère différents. La raison est probablement historique.

Karolis Juodelė

8

J'ai entendu dire que le vendeur vend des produits vraiment mauvais et qu'il serait imprudent de rencontrer ses anciens clients :)

ssch

3

Peu importe comment vous le définissez, c'est juste une façon de modéliser un problème réel. Dans TSP, vous n'avez qu'un ensemble de villes et le coût du voyage entre chaque paire d'entre elles. Cela n'exclut pas la possibilité que, dans la situation réelle que vous modélisez, la meilleure route entre B et C puisse passer par A. Si c'était le cas alors, oui, la route modélisée comme ABCA dans TSP peut très bien implique vraiment de traverser A un temps supplémentaire sur le chemin de B à C, mais de tels détails sont abstraits dans le modèle TSP.

David Richerby
la source

1

Un point valable, mais je voudrais souligner que le TSP est souvent utilisé dans des situations réelles. L'exigence de non-répétition est-elle pardonnée lors de la mise en œuvre d'applications réelles?

danmcardle

@danmcardle Cela dépend de l'application.

Tom van der Zanden

2

Je conviens que la contrainte semble étrange et, pour de nombreuses situations pratiques, elle n'est pas pertinente. Comme l'a souligné David dans sa réponse, si vous pouvez modifier vous-même la modélisation, cela n'a pas vraiment d'importance. Mais étant donné une instance non modifiable, cela fera une différence, car le TSP général avec cette contrainte n'est pas approximable dans un facteur constant, tandis que le relâchement de la contrainte de visite unique semble le rendre approximable dans le facteur 2 (même s'il n'est pas métrique ). Sauf si je manque quelque chose, par des arguments standard, vous pouvez d'abord construire un arbre couvrant minimum (de coût disons ), puis visiter cet arbre avec la technique de tournée euler. De toute évidence, le coût total de votre visite est alors de (deux fois chaque bord). Par contradiction, s'il existait une tournée de coût inférieur à $c$ $2 c$ , alors cette tournée pourrait être utilisée pour déduire un MST de coût inférieur à , ce qui est une contradiction. $c$ $c$

Arnaud Casteigts
la source

1

Étant donné toute tournée avec répétitions, vous pouvez proposer une visite plus courte qui ne répète aucune ville. Par exemple, considérons une visite guidée de la forme qui visite deux fois. Vous pouvez prendre un raccourci lors de votre deuxième visite à , allant directement de à :

\dots \to A \to \dots \to X \to A \to Y \to \dots,

$\cdots \to A \to \cdots \to X \to A \to Y \to \cdots,$

A

$A$

A

$A$

X

$X$

Y

$Y$

\dots \to A \to \dots \to X \to Y \to \dots .

$\cdots \to A \to \cdots \to X \to Y \to \cdots.$

Il est peut - être que le plus court chemin de à passe par , mais qui est déjà encapsulé dans le bord . Vous pouvez penser à une mention non comme « en passant par » mais plutôt « arrêter à » . Vous devez seulement vous arrêter à une fois, bien que vous puissiez passer par plusieurs fois. $X$ $Y$ $A$ $X \to Y$ $A$ $A$ $A$ $A$ $A$

Les algorithmes réels pour TSP pourraient avoir cette étape de "prise de raccourcis", par exemple l'algorithme de Christofides. Voir par exemple cette description ou ce compte plus court .

Yuval Filmus
la source

4

A, X_{1}, \dots, X_{n}

$A, X_1, \dots, X_n$

d (A, X_{i}) = 1

$d(A, X_i)=1$

d (x_{i}, x_{j}) = 100

$d(x_i,x_j)=100$

i, j

$i, j$

A X_{1} A X_{2} A \dots A X_{n} A

$AX_1AX_2A\dots AX_nA$

2 n + 1

$2n+1$

A X_{1} \dots X_{n} A

$AX_1\dots X_nA$

100 n - 98

$100n-98$

Certes, mais (1) l'OP semble intéressé par les applications réelles du TSP, qui sont métriques, et (2) le TSP non métrique n'est pas aussi intéressant (car c'est trop difficile).

Yuval Filmus

2

Les TSP du monde réel @YuvalFilmus ne sont pas des mesures nécessaires. Parfois, le trajet de A à B prendra plus de temps que AC + CB car il y a du trafic sur la route de A à B.

Ilya Gazman

1

(A, B)

$(A,B)$

A

$A$

B

$B$

A

$A$

B

$B$

0

Il n'y a pas de réponse générale à cela, sauf que "les gens ne sont pas stupides". Ils appliqueront la solution appropriée à leur situation. Les gens se préoccupent rarement du problème du vendeur itinérant lui-même. Eveb dans le cas classique, un vendeur du monde réel serait plus préoccupé par le problème de maximiser ses revenus sur une période de temps donnée dans un ensemble spécifique de contraintes. Dans ce cas du problème, la distance totale parcourue n'est que l'un des nombreux facteurs différents permettant de trouver la réponse optimale.

J. Antonio Perez
la source

0

Si les répétitions sont autorisées, alors vous allez simplement examiner toutes les connexions X -> A -> Y, et si cela est plus court que X -> Y, vous remplacez la longueur de X -> Y par la longueur de X -> A -> Y, et résoudre le problème résultant avec l'algorithme standard. Je pense que vous devez répéter le processus de remplacement jusqu'à ce qu'il n'y ait aucun changement, car si vous trouvez une connexion plus courte X -> Y, cela pourrait signifier que maintenant X -> Y -> Z est plus court que X -> Y.

Gardez une trace des connexions que vous avez modifiées, passez par les connexions dans la solution, et si la solution contient X -> Y, vous la remplacez par X -> A -> Y.

PS. Je pense que mon idée est excellente, mais je ne suis pas très sûr pour le moment qu'elle soit correcte. Parce que X -> A -> Y au lieu de X -> Y n'est pas seulement un raccourci, il couvre également la ville A.

gnasher729
la source

Pourquoi le TSP n'exige-t-il aucune répétition des villes?

Réponses: