Límites superiores de los recorridos del viajante de comercio en el peor de los casos en el cuadrado unitario

Question

El documento [1] demuestra que, si colocamos $N$ puntos en el cuadrado unitario, entonces la longitud $\ell$ del recorrido euclidiano TSP de esos puntos debe satisfacer $$\ell \leq \sqrt{2N} + 7/4.$$ Me pregunto si se puede demostrar también que la longitud debe satisfacer $$\ell \leq 2\sqrt{N}?$$ Evidentemente, bastará con demostrar que el resultado deseado es válido para $N\in\{3,\dots,8\}$ porque es obvio para $N=2$ y porque $\sqrt{2N}+7/4 < 2\sqrt{N}$ proporcionó $N>9$ . Me imagino que se puede hacer esto con algún tipo de cálculo de fuerza bruta, pero mi única preocupación es que pueda surgir alguna dificultad molesta cuando $N=4$ porque el límite propuesto es ajustado.

[1] Few, L. "El camino más corto y el camino más corto a través de n puntos". Mathematika 2.02 (1955): 141-144.

Answer 1

Parece posible. Los ejemplos que (para mí) parece extremo con $N=3,4,5,6$ están bien y la brecha está creciendo (a partir de $N=4$ ) por lo que tal vez la estimación sería suficiente para los dos últimos casos o tal vez no sería difícil de encontrar exactamente.

• Para $N=3$ uno tiene $2\sqrt3-(2+\sqrt{2}) \approx 0.04988805$
• Para $N=4$ uno tiene $2\sqrt4-4=0$
• Para $N=5$ uno tiene $2\sqrt5-(3+2\sqrt{1/2} \approx 0.05792239$ (esquinas y centro)
• Para $N=6$ uno tiene $2\sqrt{6}-4.5 \approx 0.398979$

Esto último es más bien una suposición. Es el resultado de elegir las cuatro esquinas y los dos puntos de la línea del medio para que los dos caminos mostrados tengan la misma longitud. Inesperadamente (para mí) eso pone los dos puntos internos en $(\frac{4 \pm 1}{8},\frac{1}{2}).$ Supongo que la escala $3-4-5$ triángulo rectángulo no es tan sorprendente.