主题
Search

旅行商常数

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

令 L(n,d) 为 n 个点在 d-D 超立方体中的最短 巡回 路径长度。那么存在一个最小常数 alpha(d) 使得对于超立方体中所有最优 巡回 路径，

limsup_(n->infty)(L(n,d))/(n^((d-1)/d)sqrt(d))<=alpha(d),
(1)

以及一个常数 beta(d) 使得对于超立方体中几乎所有最优巡回路径，

lim_(n->infty)(L(n,d))/(n^((d-1)/d)sqrt(d))=beta(d).
(2)

这些常数满足以下不等式

0.44194<gamma_2=5/(16)sqrt(2)<=beta(2)
(3)
<=delta<0.6508<0.75983<3^(-1/4)<=alpha(2)
(4)
<=phi<0.98398
(5)
0.37313<gamma_3<=beta(3)<=12^(1/6)6^(-1/2)<0.61772<0.64805
(6)
<2^(1/6)3^(-1/2)<=alpha(3)<=psi<0.90422
(7)
0.34207<gamma_4<=beta(4)<=12^(1/8)6^(-1/2)<0.55696
(8)
<0.59460<2^(-3/4)<=alpha(4)<=0.8364
(9)

(Fejes Tóth 1940, Verblunsky 1951, Few 1955, Beardwood et al. 1959), 其中

gamma_d=(Gamma(3+1/d)[Gamma(1/2d+1)]^(1/d))/(2sqrt(pi)(d^(1/2)+d^(-1/2))),
(10)

Gamma(z) 是 伽马函数，delta 是一个包含 斯特鲁夫函数 和 第二类贝塞尔函数的表达式，

phi=(280(3-sqrt(3)))/(840-280sqrt(3)+4sqrt(5)-sqrt(10))
(11)

(OEIS A086306; Karloff 1989), 并且

psi=1/23^(-2/3)(4+3ln3)^(2/3)
(12)

(OEIS A086307; Goddyn 1990)。

在 极限 d->infty 中，

0.24197<lim_(d->infty)gamma_d=1/(sqrt(2pie))<=liminf_(d->infty)beta(d)
(13)
<=limsup_(d->infty)beta(d)<=lim_(d->infty)12^(1/(2d))6^(-1/2)
(14)
=1/(sqrt(6))<0.40825
(15)

并且

0.24197<1/(sqrt(2pie))<=lim_(d->infty)alpha(d)<=(2(3-sqrt(3))theta)/(sqrt(2pie))<0.4052,
(16)

其中

1/2<=theta=lim_(d->infty)[theta(d)]^(1/d)<=0.6602,
(17)

并且 theta(d) 是 d-D 空间中最佳 球体堆积 密度 (Goddyn 1990, Moran 1984, Kabatyanskii and Levenshtein 1978)。Steele 和 Snyder (1989) 证明了极限 alpha(d) 存在。

现在考虑常数

kappa=lim_(n->infty)(L(n,2))/(sqrt(n))=beta(2)sqrt(2),
(18)

因此

5/8=gamma_2sqrt(2)<=kappa<=deltasqrt(2)<0.9204.
(19)

非严格数值估计给出 kappa approx 0.7124 (Johnson et al. 1996) 和 kappa approx 0.7120 (Percus and Martin 1996)。

某种自回避 空间填充函数 是通过一组 n 个点的最优 巡回 路径，其中 n 可以任意大。它的长度为

lambda=lim_(m->infty)(L_m)/(sqrt(n_m))=(4(1+2sqrt(2))sqrt(51))/(153)=0.7147827...
(20)

(OEIS A073008), 其中 L_m 是第 m 次迭代时曲线的长度，n_m 是点集大小 (Norman 和 Moscato 1995)。

另请参阅

旅行商问题

使用 Wolfram|Alpha 探索

参考文献

Applegate, D. L.; Bixby, R. E.; Chvátal, V.; Cook, W.; Espinoza, D. G.; Goycoolea, M.; and Helsgaun, K. "通过 85,900 个城市的最优 TSP 巡回路径的验证。" Oper. Res. Lett. 37, 11-15, 2009.Beardwood, J.; Halton, J. H.; and Hammersley, J. M. "通过多个点的最短路径。" Proc. Cambridge Phil. Soc. 55, 299-327, 1959.Chartrand, G. "销售员问题：哈密顿图导论。" §3.2 in Introductory Graph Theory. New York: Dover, pp. 67-76, 1985.Fejes Tóth, L. "关于一个几何定理。" Math. Zeit. 46, 83-85, 1940.Few, L. "通过 n 个点的最短路径和最短道路。" Mathematika 2, 141-144, 1955.Finch, S. R. "旅行商常数。" §8.5 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 497-503, 2003.Flood, M. "旅行商问题。" Operations Res. 4, 61-75, 1956.Goddyn, L. A. "量化器和最坏情况欧几里得旅行商问题。" J. Combin. Th. Ser. B 50, 65-81, 1990.Johnson, D. S.; McGeoch, L. A.; and Rothberg, E. E. "Held-Karp 旅行商界限的渐近实验分析。" In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. Held in San Francisco, California, January 22-24, 1995. Philadelphia, PA: ACM, pp. 341-350, 1996.Kabatyanskii, G. A. and Levenshtein, V. I. "球体和空间堆积的界限。" Problems Inform. Transm. 14, 1-17, 1978.Karloff, H. J. "欧几里得旅行商巡回路径可以有多长？" SIAM J. Disc. Math. 2, 91-99, 1989.Moran, S. "有界直径集合中最优 TSP 电路的长度。" J. Combin. Th. Ser. B 37, 113-141, 1984.Moscato, P. "旅行商常数的分形实例。" http://www.ing.unlp.edu.ar/cetad/mos/FRACTAL_TSP_home.html.Norman, M. G. and Moscato, P. "欧几里得旅行商问题和空间填充曲线。" Chaos Solitons Fractals 6, 389-397, 1995.Percus, A. G. and Martin, O. C. "欧几里得旅行商问题中的有限尺寸和维度依赖性。" Phys. Rev. Lett. 76, 1188-1191, 1996.Sloane, N. J. A. "整数序列在线百科全书"中的序列 A073008, A086306, 和 A086307。Steele, J. M. and Snyder, T. L. "组合优化中一些经典问题的最坏情况增长率。" SIAM J. Comput. 18, 278-287, 1989.Verblunsky, S. "通过多个点的最短路径。" Proc. Amer. Math. Soc. 2, 904-913, 1951.

在 Wolfram|Alpha 中被引用

旅行商常数

引用为

Weisstein, Eric W. "旅行商常数。" 来自 MathWorld--Wolfram 网络资源。 https://mathworld.net.cn/TravelingSalesmanConstants.html

主题分类