Versiones no soportadas:2.6 2.5 2.4 2.3
Unsupported versions:
Vendedor Viajante - Familia de funciones¶
pgr_TSP -Cuando la entrada se da como información de una celda de matriz.
pgr_TSPeuclidean - Cuando lo que entra son coordenadas.
Información general¶
Definición del Problema¶
The travelling salesperson problem (TSP) asks the following question:
Dada una lista de ciudades y las distancias entre cada par de ciudades, que corresponde con la ruta más corta posible que para visite cada ciudad exactamente una vez y regrese a la ciudad de origen?
Origen¶
- El problema de los vendedores ambulantes fue estudiado en el siglo 18 por matemáticos
Sir William Rowam Hamilton and Thomas Penyngton Kirkman.
Una discusión sobre el trabajo de Hamilton & Kirkman se puede encontrar en el libro Graph Theory (Biggs et al. 1976).
ISBN-13: 978-0198539162
ISBN-10: 0198539169
Se cree que la forma general del TSP ha sido estudiada por primera vez por Kalr Menger en Viena y Harvard. El problema fue promovido más tarde por Hassler, Whitney & Merrill en Princeton. Una descripción detallada sobre la conexión entre Menger & Whitney, y el desarrollo del TSP se puede encontrar en On the history of combinatorial optimization (till 1960)
Para calcular el número de recorridos diferentes a través de
Dada una ciudad de partida,
Hay
opción para la segunda ciudad,Y
opciones para la tercera ciudad, etc.Multiplicando estos juntos obtenemos
.Now since the travel costs do not depend on the direction taken around the tour:
este número por 2
.
General Characteristics¶
Este problema es un problema de optimización NP-duro.
Metric Algorithm is used
Implementation generates solutions that are twice as long as the optimal tour in the worst case when:
Graph is undirected
Graph is fully connected
Graph where traveling costs on edges obey the triangle inequality.
On an undirected graph:
The traveling costs are symmetric:
Traveling costs from
u
tov
are just as much as traveling fromv
tou
Ver también¶
Referencias
Metric Algorithm from Boost library
Índices y tablas