Por que o TSP não exige repetição de cidades?

9

Parece-me estranho que o TSP negue a possibilidade de cidades repetidas. O objetivo deste vendedor ambulante é ir o mais rápido possível e visitar todas as cidades, certo? E se for mais rápido viajar por uma cidade em que você já esteve?

danmcardle
fonte
2
Tenho certeza que é arbitrário. Somente em casos raros, permitir cidades repetidas faria alguma diferença (nunca no TSP métrico). Portanto, os problemas não são diferentes. O motivo é provavelmente histórico.
usar o seguinte código
8
Eu ouvi o vendedor vende produtos realmente ruins e seria imprudente para atender seus clientes antigos :)
SSCH

Respostas:

3

Não importa exatamente como você o define, porque é apenas uma maneira de modelar um problema do mundo real. No TSP, você apenas tem um conjunto de cidades e o custo da viagem entre cada par deles. Isso não exclui a possibilidade de que, na situação do mundo real que você está modelando, a melhor rota entre B e C possa passar por A. Se esse foi o caso, sim, a rota que é modelada como ABCA no TSP pode muito bem envolve realmente conduzir A por um tempo extra no caminho de B a C, mas esses detalhes são abstraídos no modelo TSP.

David Richerby
fonte
11
Um ponto válido, mas eu gostaria de salientar que o TSP é frequentemente usado em situações do mundo real. O requisito de não repetição é perdoado ao implementar aplicativos do mundo real?
Danmcardle
@danmcardle Depende da aplicação.
Tom van der Zanden
2

c2ccc

Arnaud Casteigts
fonte
1

AXAY,
AAXY
AXY.

XYAXYAAAAA

Algoritmos reais para TSP podem ter essa etapa de "pegar atalhos", por exemplo, o algoritmo de Christofides. Veja, por exemplo, esta descrição ou essa conta mais curta .

Yuval Filmus
fonte
4
A,X1,,Xnd(A,Xi)=1d(xi,xj)=100i,jAX1AX2AAXnA2n+1AX1XnA100n98
Certamente, mas (1) o OP parece interessado em aplicativos reais do TSP, que são métricos, e (2) TSP não métrico não é tão interessante (já que é muito difícil).
Yuval Filmus
2
O TSP do mundo real @YuvalFilmus não é uma métrica necessária. Algumas vezes viajam de A para B vai demorar mais tempo, em seguida, AC + CB, pois há tráfego na estrada de A para B.
Ilya gazman
11
(A,B)ABAB
0

Não há resposta geral para isso, exceto "as pessoas não são estúpidas". Eles aplicarão a solução adequada à sua situação. Raramente as pessoas estão preocupadas com o problema do vendedor ambulante. No caso clássico, um vendedor do mundo real estaria mais preocupado com o problema de maximizar sua renda durante um determinado período de tempo, dentro de um conjunto específico de restrições. Neste caso do problema, a distância total percorrida é apenas um dos vários fatores que levam a encontrar a resposta ideal.

J. Antonio Perez
fonte
0

Se repetições são permitidas, basta examinar todas as conexões X -> A -> Y, e se for menor que X -> Y, substitua o comprimento de X -> Y pelo comprimento de X -> A -> Y e resolva o problema resultante com o algoritmo padrão. Eu acho que você deve repetir o processo de substituição até que não haja alterações, porque se você encontrar uma conexão mais curta X -> Y, isso pode significar que agora X -> Y -> Z é mais curto que X -> Y.

Acompanhe as conexões que você alterou, faça as conexões na solução e, se a solução contiver X -> Y, substitua-a por X -> A -> Y.

PS. Acho que minha ideia é ótima, mas não tenho muita certeza no momento de que esteja correta. Como X -> A -> Y, em vez de X -> Y, não é apenas um atalho, mas também abrange a cidade A.

gnasher729
fonte