LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

PROBLEMA DE VENDEDOR AMBULANTE , CONTINUACIÓN

Computando una solución [ editar ]

Las líneas de ataque tradicionales para los problemas NP-hard son las siguientes:

• Diseñar algoritmos exactos , que funcionan razonablemente rápido solo para problemas pequeños.
• Diseñar algoritmos "subóptimos" o heurísticos , es decir, algoritmos que ofrecen soluciones aproximadas en un tiempo razonable.
• Encontrar casos especiales para el problema ("subproblemas") para los cuales son posibles heurísticas mejores o exactas.

Algoritmos exactos [ editar ]

La solución más directa sería probar todas las permutaciones (combinaciones ordenadas) y ver cuál es la más barata (utilizando la búsqueda de fuerza bruta ). El tiempo de ejecución de este enfoque se encuentra dentro de un factor polinomial de$${\ displaystyle O (n!)}El factorial del número de ciudades, por lo que esta solución se vuelve impráctica incluso para solo 20 ciudades.

Una de las primeras aplicaciones de la programación dinámica es el algoritmo Held-Karp que resuelve el problema en el tiempo.$${\ displaystyle O (n ^ {2} 2 ^ {n})}. ^[16] Este límite también se ha alcanzado mediante Exclusión-Inclusión en un intento que precede al enfoque de programación dinámica.

Solución a un TSP simétrico con 7 ciudades mediante la búsqueda de fuerza bruta. Nota: Número de permutaciones: (7-1)! / 2 = 360

Mejorar estos límites de tiempo parece ser difícil. Por ejemplo, no se ha determinado si un algoritmo exacto para TSP que se ejecuta en el tiempo$${\ displaystyle O (1.9999 ^ {n})}existe ^[17]

Otros enfoques incluyen:

• Varios algoritmos de ramificación y enlace , que se pueden usar para procesar TSP que contienen 40–60 ciudades.

Solución de un TSP con 7 ciudades utilizando un algoritmo simple de ramificación y límite. Nota: el número de permutaciones es mucho menor que la búsqueda de fuerza bruta

• Algoritmos de mejora progresiva que utilizan técnicas que recuerdan a la programación lineal . Funciona bien para hasta 200 ciudades.
• Implementaciones de generación de corte de ramificación y unión y problemas específicos ( ramificación y corte ^[18] ); Este es el método de elección para resolver grandes instancias. Este enfoque mantiene el registro actual, resolviendo una instancia con 85,900 ciudades, consulte Applegate et al. (2006) .

Una solución exacta para 15,112 ciudades alemanas de TSPLIB se encontró en 2001 utilizando el método de corte de avión propuesto por George Dantzig , Ray Fulkerson y Selmer M. Johnson en 1954, basado en la programación lineal . Los cálculos se realizaron en una red de 110 procesadores ubicados en Rice University y Princeton University . El tiempo total de cómputo fue equivalente a 22.6 años en un solo procesador Alpha de500 MHz . En mayo de 2004, se resolvió el problema de los vendedores ambulantes de visitar las 24.978 ciudades de Suecia: se encontró un recorrido de aproximadamente 72.500 kilómetros y se demostró que no existe un recorrido más corto. ^[19]En marzo de 2005, el problema de los vendedores ambulantes de visitar los 33,810 puntos en una placa de circuito se resolvió utilizando el Solucionador TSP Concorde : se encontró un recorrido de 66,048,945 unidades de longitud y se demostró que no existe un recorrido más corto. El cómputo tomó aproximadamente 15.7 CPU-años (Cook et al. 2006). En abril de 2006, se resolvió una instancia con 85,900 puntos utilizando Concorde TSP Solver , con más de 136 CPU-años, ver Applegate et al. (2006) .

Algoritmos heurísticos y de aproximación. [ editar ]

Varios han ideado algoritmos heurísticos y de aproximación , que rápidamente producen buenas soluciones. Los métodos modernos pueden encontrar soluciones para problemas extremadamente grandes (millones de ciudades) dentro de un tiempo razonable, que están con una alta probabilidad a solo 2–3% de la solución óptima. ^[8]

Se reconocen varias categorías de heurísticas.

Heurísticas constructivas [ editar ]

El algoritmo de vecino más cercano para un TSP con 7 ciudades. La solución cambia a medida que se cambia el punto de partida.

El algoritmo del vecino más cercano (NN) (un algoritmo codicioso ) le permite al vendedor elegir la ciudad no visitada más cercana como su próximo movimiento. Este algoritmo produce rápidamente una ruta efectivamente corta. Para N ciudades distribuidas aleatoriamente en un plano, el algoritmo en promedio produce una ruta un 25% más larga que la ruta más corta posible. ^[20] Sin embargo, existen muchas distribuciones de ciudades especialmente dispuestas que hacen que el algoritmo NN proporcione la peor ruta. ^[21] Esto es cierto tanto para los TSP asimétricos como para los simétricos. ^[22] Rosenkrantz et al. ^[23] mostró que el algoritmo NN tiene el factor de aproximación$${\ displaystyle \ Theta (\ log | V |)}Por ejemplo satisfaciendo la desigualdad del triángulo. Una variación del algoritmo NN, llamado operador de fragmento más cercano (NF), que conecta un grupo (fragmento) de las ciudades no visitadas más cercanas, puede encontrar una ruta más corta con iteraciones sucesivas. ^[24] El operador NF también se puede aplicar en una solución inicial obtenida por el algoritmo NN para una mejora adicional en un modelo elitista, donde solo se aceptan mejores soluciones.

El recorrido bitónico de un conjunto de puntos es el polígono monótono de perímetro mínimo que tiene los puntos como sus vértices; Se puede calcular de manera eficiente mediante programación dinámica .

Otra heurística constructiva , Match Twice y Stitch (MTS), realiza dos coincidencias secuenciales , donde la segunda coincidencia se ejecuta después de eliminar todos los bordes de la primera coincidencia, para producir un conjunto de ciclos. Luego se cosen los ciclos para producir el recorrido final. ^[25]

Christofides algoritmo [ editar ]

El algoritmo de Christofides sigue un esquema similar pero combina el árbol de expansión mínimo con la solución de otro problema, la coincidencia perfecta de peso mínimo . Esto da un recorrido de TSP que es como máximo 1.5 veces el óptimo. El algoritmo de Christofides fue uno de los primeros algoritmos de aproximación , y fue en parte responsable de llamar la atención sobre los algoritmos de aproximación como un enfoque práctico para problemas intratables. De hecho, el término "algoritmo" no se extendió a los algoritmos de aproximación hasta más tarde; el algoritmo de Christofides fue referido inicialmente como la heurística de Christofides.

Este algoritmo ve las cosas de manera diferente al usar un resultado de la teoría de grafos que ayuda a mejorar el LB del TSP que se originó al duplicar el costo del árbol de expansión mínimo. Dado un gráfico eulerianopodemos encontrar un tour euleriano en$${\ displaystyle O (n)}hora. ^[5] Entonces, si tuviéramos un gráfico de Euler con ciudades desde un TSP como vértices, entonces podemos ver fácilmente que podríamos usar un método de este tipo para encontrar un recorrido euleriano para encontrar una solución de TSP. Por desigualdad triangular sabemos que la gira de TSP no puede ser más larga que la gira de Eulerian y, como tal, tenemos un LB para la TSP. Tal método se describe a continuación.

Usando un método abreviado heurístico en el gráfico creado por la coincidencia a continuación

1. Encuentra un árbol de expansión mínimo para el problema
2. Crea duplicados para cada borde para crear un gráfico euleriano.
3. Encuentra un tour euleriano para este gráfico
4. Convertir a TSP: si se visita una ciudad dos veces, cree un acceso directo desde la ciudad anterior a este en el recorrido hasta el siguiente.

Para mejorar el límite inferior, se necesita una mejor forma de crear un gráfico euleriano. Por desigualdad triangular, el mejor gráfico de Eulerian debe tener el mismo costo que el mejor recorrido de los vendedores ambulantes, por lo que encontrar los gráficos de Eulerian óptimos es al menos tan difícil como el TSP. Una forma de hacerlo es mediante el ajuste de peso mínimo usando algoritmos de$${\ displaystyle O (n ^ {3})}. ^[5]

Creando una coincidencia

Hacer un gráfico en un gráfico euleriano comienza con el árbol de expansión mínimo. Entonces todos los vértices de orden impar deben ser pareados. Por lo tanto, se debe agregar una coincidencia para los vértices de grados impares que aumenta el orden de cada vértice de grados impares en uno. ^[5] Esto nos deja con una gráfica en la que cada vértice es de orden par, lo que es, por lo tanto, euleriano. Adaptar el método anterior da el algoritmo de Christofides,

1. Encuentra un árbol de expansión mínimo para el problema
2. Cree una coincidencia para el problema con el conjunto de ciudades de orden impar.
3. Encuentra un tour euleriano para este gráfico
4. Convertir a TSP utilizando accesos directos.

Mejora iterativa [ editar ]

Un ejemplo de una iteración 2-opt

Intercambio por pares [ editar ]

La técnica de intercambio por pares o 2-opt implica eliminar iterativamente dos bordes y reemplazarlos con dos bordes diferentes que reconectan los fragmentos creados por la eliminación de bordes en un recorrido nuevo y más corto. De manera similar, la técnica 3-opt elimina 3 bordes y los vuelve a conectar para formar un recorrido más corto. Estos son casos especiales del método k -opt. Tenga en cuenta que la etiqueta Lin – Kernighan es un nombre inapropiado que se escucha a menudo para 2-opt. Lin – Kernighan es en realidad el método k-opt más general.

Para los casos de Euclides, las heurísticas de 2 opciones ofrecen en promedio soluciones que son aproximadamente un 5% mejores que el algoritmo de Christofides. Si comenzamos con una solución inicial hecha con un algoritmo codicioso , el número promedio de movimientos vuelve a disminuir en gran medida y es$${\ displaystyle O (n)}. Sin embargo, para inicios aleatorios, el número promedio de movimientos es$${\ displaystyle O (n \ log (n))}. Sin embargo, aunque en orden este es un pequeño aumento en el tamaño, el número inicial de movimientos para problemas pequeños es 10 veces más grande para un inicio aleatorio en comparación con el hecho de una heurística codiciosa. Esto se debe a que tales heurísticas de 2 opciones explotan partes "malas" de una solución como los cruces. Estos tipos de heurísticas se utilizan a menudo dentro de las heurísticas de problemas de enrutamiento de vehículos para reoptimizar las soluciones de enrutamiento. ^[20]

Heurística k -opt, o heurística de Lin – Kernighan [ editar ]

La heurística Lin – Kernighan es un caso especial de la V técnica -opt o variable-opt. Implica los siguientes pasos:

1. Dado un recorrido, borra k bordes desunidos mutuamente.
2. Vuelva a ensamblar los fragmentos restantes en un recorrido, sin dejar subtours desunidos (es decir, no conecte los extremos de un fragmento juntos). Esto, en efecto, simplifica el TSP en consideración en un problema mucho más simple.
3. Cada punto final de fragmento se puede conectar a 2 k  - 2 otras posibilidades: de 2 k de puntos finales de fragmento total disponibles, los dos puntos finales del fragmento en consideración no están permitidos. Este tipo de TSP de 2 k con restricciones puede resolverse con métodos de fuerza bruta para encontrar la recombinación de menor costo de los fragmentos originales.

El método más popular de k -opt es 3-opt, tal como lo introdujo Shen Lin de Bell Labs en 1965. Un caso especial de 3-opt es que los bordes no están separados (dos de los bordes están adyacentes entre sí) . En la práctica, a menudo es posible lograr una mejora sustancial en 2-opt sin el costo combinatorio del general 3-opt al restringir los 3 cambios a este subconjunto especial donde dos de los bordes eliminados son adyacentes. Esta llamada opción optativa de dos y media generalmente se ubica aproximadamente a mitad de camino entre la opción 2 y la opción 3, tanto en términos de la calidad de los tours logrados como en el tiempo requerido para lograrlos.

Heurística V- Opt [ editar ]

El método variable-opt está relacionado con, y una generalización del método k -opt. Mientras que los métodos k-opt eliminan un número fijo ( k ) de bordes del recorrido original, los métodos de opción variable no corrigen el tamaño del conjunto de bordes que se eliminará. En su lugar, crecen el conjunto a medida que el proceso de búsqueda continúa. El método más conocido en esta familia es el método Lin-Kernighan (mencionado anteriormente como un nombre inapropiado para 2-opt). Shen Lin y Brian Kernighan publicó su método por primera vez en 1972, y fue la heurística más confiable para resolver problemas de vendedores ambulantes durante casi dos décadas. David Johnson y su equipo de investigación desarrollaron métodos de opción variable más avanzados en los laboratorios Bell a finales de los años ochenta. Estos métodos (a veces llamados Lin – Kernighan – Johnson)) Aproveche el método Lin-Kernighan, agregue ideas de la búsqueda tabú y la computación evolutiva, . La técnica básica de Lin – Kernighan da resultados que se garantiza que sean al menos 3-opt. Los métodos Lin – Kernighan – Johnson calculan un recorrido Lin – Kernighan y luego perturban el recorrido por lo que se ha descrito como una mutación que elimina al menos cuatro bordes y vuelve a conectar el recorrido de una manera diferente, luego V optando por el nuevo recorrido. La mutación a menudo es suficiente para mover el recorrido desde el mínimo local identificado por Lin – Kernighan. Los métodos V -opt son ampliamente considerados como las heurísticas más poderosas para el problema, y ​​son capaces de abordar casos especiales, como el Problema del Ciclo de Hamilton y otros TSP no métricos en los que otras heurísticas fallan. Durante muchos años, Lin-Kernighan-Johnson identificó soluciones óptimas para todos los TSP en los que se conocía una solución óptima e identificó las soluciones más conocidas para todos los otros TSP en los que se había probado el método.

Mejora aleatoria [ editar ]

Los algoritmos de cadena optimizados de Markov que utilizan sub-algoritmos heurísticos de búsqueda local pueden encontrar una ruta extremadamente cerca de la ruta óptima para 700 a 800 ciudades.

TSP es una piedra de toque para muchas heurísticas generales diseñadas para optimización combinatoria, como algoritmos genéticos , recocido simulado , búsqueda de tabú , optimización de colonias de hormigas , dinámica de formación de ríos (ver inteligencia de enjambre ) y el método de entropía cruzada .

Optimización de colonias de hormigas [ editar ]

Artículo principal: Algoritmos de optimización de colonias de hormigas.

El investigador de inteligencia artificial Marco Dorigo describió en 1993 un método para generar heurísticamente "buenas soluciones" para el TSP utilizando una simulación de una colonia de hormigas llamada ACS ( sistema de colonias de hormigas ). ^[26] Modela el comportamiento observado en las hormigas reales para encontrar caminos cortos entre las fuentes de alimentos y su nido, un comportamiento emergente que resulta de la preferencia de cada hormiga de seguir las feromonas del rastro depositadas por otras hormigas.

ACS envía una gran cantidad de agentes ant virtuales para explorar muchas rutas posibles en el mapa. Cada hormiga elige de manera probabilística la siguiente ciudad para visitar basándose en una heurística que combina la distancia a la ciudad y la cantidad de feromona virtual depositada en el borde de la ciudad. Las hormigas exploran y depositan feromonas en cada borde que atraviesan, hasta que todas hayan completado un recorrido. En este punto, la hormiga que completó el recorrido más corto deposita la feromona virtual a lo largo de su ruta completa de recorrido ( actualización global del sendero ). La cantidad de feromona depositada es inversamente proporcional a la duración del recorrido: cuanto más corto es el recorrido, más se deposita.

Algoritmo de optimización de colonias de hormigas para un TSP con 7 ciudades: las líneas rojas y gruesas en el mapa de feromonas indican la presencia de más feromonas

Casos especiales [ editar ]

Métrica [ editar ]

En la métrica TSP , también conocida 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 C intermedio :

$${\ 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 más 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 la distancia de Manhattan o métrica de bloque de ciudad.
• 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 mediciones aparecen, por ejemplo, al enrutar 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 visitar ciudades dos veces, pero muchas aplicaciones no necesitan esta restricción. En tales casos, una instancia simétrica, no métrica se puede reducir a una 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 del 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 TSP euclidiano es NP-duro en ambos casos. Con coordenadas racionales y métrica discretizada (distancias redondeadas hasta un entero), el problema es NP-completo. ^[27] Con coordenadas racionales y la métrica euclidiana real, se sabe que el TSP euclidiano está en la Jerarquía de Recuento, ^[28] una subclase de PSPACE. Con coordenadas reales arbitrarias, el TSP euclidiano 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. ^[29] 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 O esperado ( n log n ) tiempo para n puntos (considerablemente menor que el número de bordes). 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, hay un algoritmo de tiempo polinómico que encuentra un recorrido de longitud como máximo (1 + 1 / c ) por 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). ^[30] Sanjeev Arora y Joseph SB Mitchell fueron galardonados con el Premio Gödel en 2010 por su descubrimiento simultáneo de un PTAS para el PST euclidiano.

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

Asimétrica [ 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étrico. Una aplicación práctica de un TSP asimétrico es la optimización de rutas utilizando rutas a nivel de calles (que se hacen asimétricas por calles de un solo sentido, carreteras 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 camino 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 . ^[31]

Pesos de trayectoria asimétricos

	UNA	segundo	do
UNA		1	2
segundo	6		3
do	5	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 peso muy bajo (posiblemente negativo), aquí denotado - w. (Alternativamente, los bordes fantasmas tienen un peso de 0 y el peso w se agrega a todos los demás 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. A ambas copias de la matriz se les han reemplazado las diagonales 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 fantasma.

Pesos de trayectoria simétrica

	UNA	segundo	do	UNA'	SEGUNDO'	DO'
UNA				- w	6	5
segundo				1	- w	4
do				2	3	- w
UNA'	- w	1	2
SEGUNDO'	6	- w	3
DO'	5	4	- w

El peso - w de los bordes "fantasmas" que conectan los nodos fantasma con los nodos originales correspondientes debe ser lo suficientemente bajo para garantizar que todos los bordes fantasma 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 los nodos originales y fantasmas nuevamente, obtenemos una solución (óptima) del problema asimétrico original (en nuestro ejemplo, $${\ displaystyle \ mathrm {A \ to C \ to B \ to A}}).

El problema de Analista [ editar ]

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

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 del camino más corto (es decir, la solución TSP) para este conjunto de puntos, de acuerdo con la distancia euclidiana habitual . Se sabe ^[32] 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 más abajo), se desprende del teorema de convergencia acotada que$${\ displaystyle \ beta = \ lim _ {n \ to \ infty} \ mathbb {E} [L_ {n} ^ {*}] / {\ sqrt {n}}}, por lo tanto, los límites inferiores y superiores en $${\ displaystyle \ beta} seguir desde los límites en $${\ 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}}Se reemplazan con observaciones de un proceso ergódico estacionario con marginales uniformes. ^[33]

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 monótonamente los puntos dentro de cada uno de $${\ displaystyle {\ sqrt {n}}} rebanadas de ancho $${\ displaystyle 1 / {\ sqrt {n}}} en la plaza.
• Pocos ^[34] probaron$${\ displaystyle L_ {n} ^ {*} \ leq {\ sqrt {2n}} + 1.75}de ahí $${\ displaystyle \ beta \ leq {\ sqrt {2}}}, posteriormente mejorado por Karloff (1987): $${\ displaystyle \ beta \ leq 0.984 {\ sqrt {2}}}.
• El límite superior actual ^[35] es $${\ displaystyle \ beta \ leq 0.92 \ puntos}.

Límite inferior [ editar ]

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

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

• Se obtiene un mejor límite inferior ^[32] 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 límite más bajo actualmente ^[35] es

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

• Held y Karp ^[36] dieron un algoritmo de tiempo polinomial que proporciona límites numéricos más bajos para$${\ displaystyle L_ {n} ^ {*}}, y asi para $${\ displaystyle \ beta (\ simeq L_ {n} ^ {*} / {\ sqrt {n}})}Que parecen ser buenas hasta más o menos el 1%. ^[37] En particular, David S. Johnson ^[38] obtuvo un límite inferior mediante un experimento por computadora:

$${\ 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 ^[39] obtuvieron el siguiente límite numérico inferior:

$${\ 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 complejidadFP ^NP ; vea el problema de la función ), y la versión del problema de decisión ("dados los costos y un número x , decida si hay una ronda -La ruta de viaje más barata que x ") es NP-completa . El problema del vendedor ambulante de cuellos de botella también es NP-duro. El problema sigue siendo NP-duro incluso en el caso de que las ciudades estén en el plano con distancias euclidianas. , así como en una serie de 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 omitir una visita repetida no aumentaría la duración del recorrido).

Complejidad de la aproximación [ editar ]

En el caso general, la búsqueda de una visita más corta a un vendedor viajero es NPO -completa. ^[40] Si la medida de la distancia es una métrica (y, por lo tanto, simétrica), el problema se vuelve APX completo ^[41] y el algoritmo de Christofides lo aproxima dentro de 1.5. ^[42] El límite de inoproximabilidad más conocido es 123/122.^[43]

Si las distancias se limitan a 1 y 2 (pero aún son métricas), la relación de aproximación se convierte en 8/7. ^[44]En el caso asimétrico con desigualdad de triángulos , solo se conocen las garantías logarítmicas de rendimiento, el mejor algoritmo actual alcanza una relación de rendimiento de 0,814 log ( n ); ^[45] es una pregunta abierta si existe una aproximación de factor constante. El límite de inoproximabilidad más conocido es 75/74. ^[43]

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

Rendimiento humano [ 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 seres humanos son capaces de producir soluciones casi óptimas rápidamente, de manera casi lineal, con un rendimiento que varía desde un 1% menos eficiente para gráficos con 10-20 nodos, y un 11% más eficiente para gráficos con 120 nodos. ^[49] [50] La aparente facilidad con la que los humanos generan con precisión soluciones casi óptimas para el problema ha llevado a los investigadores a suponer que los humanos usan una o más heurísticas, con las dos teorías más populares como la hipótesis del casco convexo y el cruce -Avio heurístico. ^{[51] [52] [53]}Sin embargo, la evidencia adicional sugiere que el rendimiento humano es bastante variado, y las diferencias individuales, así como la geometría gráfica, parecen afectar el rendimiento en la tarea. ^{[54] [55] [56]} Sin embargo, los resultados sugieren que el rendimiento de la computadora en el TSP puede mejorarse al comprender y emular los métodos utilizados por los humanos para estos problemas, ^[57] y también ha dado lugar a nuevos conocimientos sobre los mecanismos de los humanos. pensamiento. ^[58] El primer número del Journal of Problem Solving se dedicó al tema del desempeño humano en TSP, ^[59] y una revisión de 2011 enumeró docenas de artículos sobre el tema.