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¶
En el problema del vendedor viajante (TSP) hace la siguiente pregunta:
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 y 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 \(n\) ciudades:
Dada una ciudad de partida,
Hay \(n-1\) opción para la segunda ciudad,
Y \(n-2\) opciones para la tercera ciudad, etc.
Multiplicando estos juntos obtenemos \((n-1)! = (n-1) (n-2) . . 1\).
Ahora, dado que los costos de viaje no dependen de la dirección tomada alrededor del recorrido:
este número por 2
\((n-1)!/2\).
Características generales¶
Este problema es un problema de optimización NP-duro.
Se utiliza el algoritmo métrico
La implementación genera soluciones que son el doble de largas que el recorrido óptimo en el peor de los casos cuando:
El grafo es no dirigido
El grafo está completamente conectado
Grafo donde los costos de viaje en los segmentos cumplen con la desigualdad del triángulo.
En un grafo no dirigido:
Los costos del viaje son simétricos:
Los costos del viaje de
u
av
son tanto como viajar dev
au
Ver también¶
Referencias
Algoritmo Metrico de la Librería Boost
Índices y tablas