LISTA DE PROBLEMAS

PROBLEMA DEL VENDEDOR AMBULANTE , CONTINUACIÓN II

Casos especiales [ editar ]

Métrica [ editar ]

En el TSP métrico , también conocido como delta-TSP o Δ-TSP, las distancias interurbanas satisfacen la desigualdad del triángulo .

Una restricción muy natural del TSP es exigir que las distancias entre ciudades formen una métrica para satisfacer la desigualdad del triángulo ; es decir, la conexión directa de A a B nunca está más lejos que la ruta a través del intermedio C :

$${\ displaystyle d_ {AB} \ leq d_ {AC} + d_ {CB}}.

El borde se extiende y luego construye una métrica en el conjunto de vértices. Cuando las ciudades se ven como puntos en el plano, muchas funciones de distancia natural son métricas, y muchas instancias naturales de TSP satisfacen esta restricción.

Los siguientes son algunos ejemplos de TSP de métrica para varias métricas.

• En el TSP Euclidiano (ver abajo) la distancia entre dos ciudades es la distancia Euclidiana entre los puntos correspondientes.
• En el TSP rectilíneo, la distancia entre dos ciudades es la suma de los valores absolutos de las diferencias de sus coordenadas x e y . Esta métrica a menudo se denomina distancia de Manhattan o métrica de manzana.
• En la métrica máxima , la distancia entre dos puntos es el máximo de los valores absolutos de las diferencias de sus coordenadas x e y .

Las dos últimas métricas aparecen, por ejemplo, en el enrutamiento de una máquina que perfora un conjunto dado de agujeros en una placa de circuito impreso . La métrica de Manhattan corresponde a una máquina que ajusta primero una coordenada y luego la otra, por lo que el tiempo para moverse a un nuevo punto es la suma de ambos movimientos. La métrica máxima corresponde a una máquina que ajusta ambas coordenadas simultáneamente, por lo que el tiempo para moverse a un nuevo punto es el más lento de los dos movimientos.

En su definición, el TSP no permite que las ciudades sean visitadas dos veces, pero muchas aplicaciones no necesitan esta restricción. En tales casos, una instancia simétrica y no métrica se puede reducir a una instancia métrica. Esto reemplaza el gráfico original con un gráfico completo en el que la distancia entre ciudades$${\ displaystyle d_ {AB}}se reemplaza por la ruta más corta entre A y B en el gráfico original.

Euclidiana [ editar ]

Cuando los números de entrada pueden ser números reales arbitrarios, el TSP euclidiano es un caso particular de TSP métrico, ya que las distancias en un plano obedecen a la desigualdad del triángulo. Cuando los números de entrada deben ser enteros, comparar longitudes de recorridos implica comparar sumas de raíces cuadradas.

Al igual que el TSP general, el Euclidean TSP es NP-hard en cualquier caso. Con coordenadas racionales y métricas discretizadas (distancias redondeadas a un número entero), el problema es NP completo. ^[28] Con coordenadas racionales y la métrica euclidiana real, se sabe que el TSP euclidiano está en la Jerarquía de conteo, ^[29] una subclase de PSPACE. Con coordenadas reales arbitrarias, Euclidean TSP no puede estar en tales clases, ya que hay innumerables entradas posibles. Sin embargo, Euclidean TSP es probablemente la versión más fácil para la aproximación. ^[30] Por ejemplo, el árbol de expansión mínimo del gráfico asociado con una instancia del TSP euclidiano es un árbol de expansión mínimo euclidiano , por lo que puede calcularse en el O esperado ( n logn ) tiempo para n puntos (considerablemente menor que el número de aristas). Esto permite que el algoritmo simple de 2 aproximaciones para TSP con la desigualdad del triángulo anterior funcione más rápidamente.

En general, para cualquier c > 0, donde d es el número de dimensiones en el espacio euclidiano, existe un algoritmo de tiempo polinomial que encuentra un recorrido de longitud como máximo (1 + 1 / c ) veces el óptimo para instancias geométricas de TSP en

$${\ displaystyle O \ left (n (\ log n) ^ {(O (c {\ sqrt {d}})) ^ {d-1}} \ right),}

hora; Esto se llama un esquema de aproximación de tiempo polinomial (PTAS). ^[31] Sanjeev Arora y Joseph SB Mitchell recibieron el Premio Gödel en 2010 por su descubrimiento concurrente de un PTAS para el TSP Euclidiano.

En la práctica, se siguen utilizando heurísticas más simples con garantías más débiles.

Asimétrico [ editar ]

En la mayoría de los casos, la distancia entre dos nodos en la red TSP es la misma en ambas direcciones. El caso donde la distancia de A a B no es igual a la distancia de B a A se llama TSP asimétrica. Una aplicación práctica de un TSP asimétrico es la optimización de la ruta mediante el enrutamiento a nivel de la calle (que se hace asimétrico por calles de un solo sentido, vías de acceso, autopistas, etc.).

Conversión a simétrica [ editar ]

Resolver un gráfico TSP asimétrico puede ser algo complejo. La siguiente es una matriz de 3 x 3 que contiene todos los posibles pesos de ruta entre los nodos A , B y C . Una opción es convertir una matriz asimétrica de tamaño N en una matriz simétrica de tamaño 2 N . ^[32]

Pesos de trayectoria asimétrica

	UNA	si	do
UNA		1	2
si	6 6		3
do	5 5	4 4

Para duplicar el tamaño, cada uno de los nodos en el gráfico se duplica, creando un segundo nodo fantasma , vinculado al nodo original con un borde "fantasma" de muy bajo (posiblemente negativo) peso, aquí denotado - w . (Alternativamente, los bordes fantasma tienen un peso 0, y el peso w se agrega a todos los otros bordes). La matriz original de 3 × 3 que se muestra arriba es visible en la parte inferior izquierda y la transposición del original en la parte superior derecha. Ambas copias de la matriz han tenido sus diagonales reemplazadas por las rutas de salto de bajo costo, representadas por - w . En el nuevo gráfico, ningún borde vincula directamente los nodos originales y ningún borde vincula directamente los nodos fantasmas.

Pesos de trayectoria simétrica

	UNA	si	do	UNA'	SI'	DO'
UNA				- w	6 6	5 5
si				1	- w	4 4
do				2	3	- w
UNA'	- w	1	2
SI'	6 6	- w	3
DO'	5 5	4 4	- w

El peso - w de los bordes "fantasmas" que unen los nodos fantasmas a los nodos originales correspondientes debe ser lo suficientemente bajo para garantizar que todos los bordes fantasmas deben pertenecer a cualquier solución TSP simétrica óptima en el nuevo gráfico (w = 0 no siempre es lo suficientemente bajo ) Como consecuencia, en el recorrido simétrico óptimo, cada nodo original aparece junto a su nodo fantasma (por ejemplo, una posible ruta es$${\ displaystyle \ mathrm {A \ to A '\ to C \ to C' \ to B \ to B '\ to A}}) y al fusionar nuevamente los nodos original y fantasma obtenemos una solución (óptima) del problema asimétrico original (en nuestro ejemplo, $${\ displaystyle \ mathrm {A \ to C \ to B \ to A}})

Problema del analista [ editar ]

Hay un problema análogo en la teoría de la medida geométrica que pregunta lo siguiente: ¿bajo qué condiciones puede estar contenido un subconjunto E del espacio euclidiano en una curva rectificable (es decir, ¿cuándo hay una curva con longitud finita que visita cada punto en E )? Este problema se conoce como el problema del vendedor ambulante del analista.

Longitud de ruta para conjuntos aleatorios de puntos en un cuadrado [ editar ]

Suponer $${\ displaystyle X_ {1}, \ ldots, X_ {n}} son $${\ displaystyle n} variables aleatorias independientes con distribución uniforme en el cuadrado $${\ displaystyle [0,1] ^ {2}}, y deja $${\ displaystyle L_ {n} ^ {\ ast}}sea ​​la longitud de ruta más corta (es decir, la solución TSP) para este conjunto de puntos, de acuerdo con la distancia euclidiana habitual . Se sabe ^[33] que, casi seguramente,

$${\ displaystyle {\ frac {L_ {n} ^ {*}} {\ sqrt {n}}} \ rightarrow \ beta \ qquad {\ text {when}} n \ to \ infty,}

dónde $${\ displaystyle \ beta}es una constante positiva que no se conoce explícitamente. Ya que$${\ displaystyle L_ {n} ^ {*} \ leq 2 {\ sqrt {n}} + 2}(ver abajo), se sigue del teorema de convergencia acotada que$${\ displaystyle \ beta = \ lim _ {n \ to \ infty} \ mathbb {E} [L_ {n} ^ {*}] / {\ sqrt {n}}}, por lo tanto, los límites inferior y superior en $${\ displaystyle \ beta} seguir desde límites $${\ displaystyle \ mathbb {E} [L_ {n} ^ {*}]}.

El límite casi seguro $${\ displaystyle {\ frac {L_ {n} ^ {*}} {\ sqrt {n}}} \ rightarrow \ beta} como $${\ displaystyle n \ to \ infty} puede no existir si las ubicaciones independientes $${\ displaystyle X_ {1}, \ ldots, X_ {n}}son reemplazados por observaciones de un proceso ergódico estacionario con marginales uniformes. ^[34]

Límite superior [ editar ]

• Uno tiene $${\ displaystyle L ^ {*} \ leq 2 {\ sqrt {n}} + 2}, y por lo tanto $${\ displaystyle \ beta \ leq 2}, mediante el uso de un camino ingenuo que visita monotónicamente los puntos dentro de cada $${\ displaystyle {\ sqrt {n}}} rebanadas de ancho $${\ displaystyle 1 / {\ sqrt {n}}} en la plaza.
• Pocos ^[35] demostraron$${\ displaystyle L_ {n} ^ {*} \ leq {\ sqrt {2n}} + 1.75}por lo tanto $${\ displaystyle \ beta \ leq {\ sqrt {2}}}, posteriormente mejorado por Karloff (1987): $${\ displaystyle \ beta \ leq 0.984 {\ sqrt {2}}}.
• Algunos estudios informaron ^[36] un límite superior que$${\ displaystyle \ beta \ leq 0.92 \ dots}.
• Algunos estudios informaron ^[37] un límite superior que$${\ displaystyle \ beta \ leq 0.73 \ dots}.

Límite inferior [ editar ]

• Al observar eso $${\ displaystyle \ mathbb {E} [L_ {n} ^ {*}]} es mayor que $${\ displaystyle n} veces la distancia entre $${\ displaystyle X_ {0}} y el punto más cercano $${\ displaystyle X_ {i} \ neq X_ {0}}, uno obtiene (después de un cálculo corto)

$${\ displaystyle \ mathbb {E} [L_ {n} ^ {*}] \ geq {\ tfrac {1} {2}} {\ sqrt {n}}.}

• Se obtiene un mejor límite inferior ^[33] al observar que$${\ displaystyle \ mathbb {E} [L_ {n} ^ {*}]} es mayor que $${\ displaystyle {\ tfrac {1} {2}} n} veces la suma de las distancias entre $${\ displaystyle X_ {0}} y los puntos más cercanos y segundos más cercanos $${\ displaystyle X_ {i}, X_ {j} \ neq X_ {0}}, lo que da

$${\ displaystyle \ mathbb {E} [L_ {n} ^ {*}] \ geq \ left ({\ tfrac {1} {4}} + {\ tfrac {3} {8}} \ right) {\ sqrt {n}} = {\ tfrac {5} {8}} {\ sqrt {n}},}

• El mejor límite inferior actualmente ^[36] es

$${\ displaystyle \ mathbb {E} [L_ {n} ^ {*}] \ geq ({\ tfrac {5} {8}} + {\ tfrac {19} {5184}}) {\ sqrt {n}} ,}

• Held y Karp ^[38] dieron un algoritmo de tiempo polinómico que proporciona límites numéricos inferiores para$${\ displaystyle L_ {n} ^ {*}}, y por lo tanto para $${\ displaystyle \ beta (\ simeq L_ {n} ^ {*} / {\ sqrt {n}})}que parecen ser buenos hasta más o menos 1%. ^[39] En particular, David S. Johnson ^[40] obtuvo un límite inferior por experimento informático:

$${\ displaystyle L_ {n} ^ {*} \ gtrsim 0.7080 {\ sqrt {n}} + 0.522,}

donde 0.522 proviene de los puntos cercanos al límite cuadrado que tienen menos vecinos, y Christine L. Valenzuela y Antonia J. Jones ^[41] obtuvieron el siguiente límite inferior numérico:

$${\ displaystyle L_ {n} ^ {*} \ gtrsim 0.7078 {\ sqrt {n}} + 0.551}.

Complejidad computacional [ editar ]

Se ha demostrado que el problema es NP-duro (más precisamente, está completo para la clase de complejidad FP ^NP ; ver problema de función ) y la versión del problema de decisión ("dados los costos y un número x , decida si hay una ronda -trayecto ruta más barata que x ") es NP-complete . El problema del vendedor ambulante de cuello de botella también es NP-duro. El problema sigue siendo NP-duro incluso para el caso cuando las ciudades están en el avión con distancias euclidianas, así como en otros casos restrictivos. Eliminar la condición de visitar cada ciudad "solo una vez" no elimina la dureza NP, ya que se ve fácilmente que en el caso plano hay un recorrido óptimo que visita cada ciudad solo una vez (de lo contrario, por la desigualdad del triángulo , un atajo que omite una visita repetida no aumentaría la duración del recorrido).

Complejidad de aproximación [ editar ]

En el caso general, encontrar un recorrido de vendedor ambulante más corto es NPO- completo. ^[42] Si la medida de la distancia es métrica (y por lo tanto simétrica), el problema se vuelve APX- completo ^[43] y el algoritmo de Christofides se aproxima a 1.5. ^[44] El límite de inaplicabilidad más conocido es 123/122. ^[45]

Si las distancias están restringidas a 1 y 2 (pero aún son métricas), la relación de aproximación se convierte en 8/7. ^[46] En el caso asimétrico con desigualdad triangular , solo se conocen las garantías de rendimiento logarítmico, el mejor algoritmo actual logra una relación de rendimiento 0.814 log ( n ); ^[47] es una pregunta abierta si existe una aproximación de factor constante. El límite de inaplicabilidad más conocido es 75/74. ^[45]

El problema de maximización correspondiente de encontrar el recorrido de vendedor ambulante más largo es aproximado dentro de 63/38. ^[48] Si la función de distancia es simétrica, el recorrido más largo puede aproximarse dentro de 4/3 mediante un algoritmo determinista ^[49] y dentro de$${\ displaystyle {\ tfrac {1} {25}} (33+ \ varepsilon)}por un algoritmo aleatorio. ^[50]

Rendimiento humano y animal [ editar ]

El TSP, en particular la variante euclidiana del problema, ha atraído la atención de los investigadores en psicología cognitiva . Se ha observado que los humanos son capaces de producir soluciones casi óptimas rápidamente, de forma casi lineal, con un rendimiento que varía entre 1% menos eficiente para gráficos con 10-20 nodos y 11% más eficiente para gráficos con 120 nodos. ^[51] [52] La aparente facilidad con la que los humanos generan con precisión soluciones casi óptimas para el problema ha llevado a los investigadores a plantear la hipótesis de que los humanos usan una o más heurísticas, siendo las dos teorías más populares la hipótesis del casco convexo y el cruce. -Euritación heurística. ^{[53] [54] [55]}Sin embargo, la evidencia adicional sugiere que el rendimiento humano es bastante variado, y las diferencias individuales, así como la geometría del gráfico, parecen afectar el rendimiento en la tarea. ^{[56] [57] [58]} Sin embargo, los resultados sugieren que el rendimiento de la computadora en el TSP puede mejorarse mediante la comprensión y la emulación de los métodos utilizados por los humanos para estos problemas, ^[59] y también han conducido a nuevas ideas sobre los mecanismos humanos pensamiento. ^[60] El primer número del Journal of Problem Solving se dedicó al tema del desempeño humano en TSP, ^[61] y una revisión de 2011 enumeró docenas de artículos sobre el tema. ^[60]

Un estudio de 2011 sobre cognición animal titulado "Deja que la paloma conduzca el autobús", llamado así por el libro infantil ¡No dejes que la paloma conduzca el autobús!, examinaron la cognición espacial en palomas estudiando sus patrones de vuelo entre múltiples alimentadores en un laboratorio en relación con el problema del vendedor ambulante. En el primer experimento, se colocaron palomas en la esquina de una sala de laboratorio y se les permitió volar a comederos cercanos que contenían guisantes. Los investigadores encontraron que las palomas usaban la proximidad en gran medida para determinar qué alimentador seleccionarían a continuación. En el segundo experimento, los comederos se organizaron de tal manera que volar al comedero más cercano en cada oportunidad sería en gran medida ineficiente si las palomas necesitaran visitar cada comedero. Los resultados del segundo experimento indican que las palomas, aunque siguen favoreciendo las soluciones basadas en proximidad,^[62] Estos resultados son consistentes con otros experimentos realizados con no primates, que han demostrado que algunos no primates pudieron planificar rutas de viaje complejas. Esto sugiere que los no primates pueden poseer una capacidad cognitiva espacial relativamente sofisticada.

Cálculo natural [ editar ]

Cuando se presenta una configuración espacial de las fuentes de alimentos, el ameboide Physarum polycephalum adapta su morfología para crear una ruta eficiente entre las fuentes de alimentos que también se puede ver como una solución aproximada al TSP. ^[63] Se considera que presenta posibilidades interesantes y se ha estudiado en el área de la informática natural .

Benchmarks [ editar ]

Para la evaluación comparativa de los algoritmos de TSP, TSPLIB es una biblioteca de instancias de muestra del TSP y se mantienen los problemas relacionados, consulte la referencia externa de TSPLIB. Muchos de ellos son listas de ciudades reales y diseños de circuitos impresos reales .