主題
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)。

另請參閱

旅行商問題

使用 探索

參考文獻

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.

在 中被引用

旅行商常數

引用為

Weisstein, Eric W. "旅行商常數。" 來自 網路資源。 https://mathworld.tw/TravelingSalesmanConstants.html

主題分類