THE EUCLIDEAN TRAVELING SALESMAN PROBLEM AND A SPACE-FILLING CURVE

被引：19

作者：

NORMAN, MG ^{[1
]}

MOSCATO, P ^{[1
]}

机构：

[1] NATL UNIV LA PLATA,CETAD,RA-1900 LA PLATA,ARGENTINA

来源：

CHAOS SOLITONS & FRACTALS | 1995年 / 6卷

关键词：

D O I：

10.1016/0960-0779(95)80046-J

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We elucidate the relationship between space-filling curves and the Euclidean Traveling(2) Salesman Problem (TSP) by reference to a particular space-filling curve whose scaling behaviour is strongly related to the conjectured scaling behaviour of the optimal TSP tour. We suggest that space-filling curves can be used to generate testbed TSPs: sets of points which in the limit cover a planar surface and for which tours of minimum length are known.

引用

页码：389 / 397

页数：9

共 15 条

[1]

[Anonymous], 1992, CHAOS FRACTALS NEW F

[2]

Beardwood J, 1959, P CAMBRIDGE PHILOS S, V55, P299, DOI [DOI 10.1017/S0305004100034095, 10.1017/S0305004100034095]

[3]

Bennett C. H., 1990, SFI STUDIES SCI COMP, VVIII

[4]

BENTLEY JL, 1990, 1ST P ANN ACM SIAM S, P91

[5] THE N-CITY TRAVELING SALESMAN PROBLEM - STATISTICAL-MECHANICS AND THE METROPOLIS ALGORITHM [J].

BONOMI, E ;

LUTTON, JL .

SIAM REVIEW, 1984, 26 (04) :551-568

[6]

Garey M.R., 1979, COMPUTERS INTRACTABI, V174

[7]

Herman G. T., 1975, DEV SYSTEMS LANGUAGE

[8]

HILBERT D, 1891, MATH ANN, V38, P468

[9] COMPLEXITY OF SOME PROBLEMS CONCERNING L-SYSTEMS [J].

JONES, ND ;

SKYUM, S .

MATHEMATICAL SYSTEMS THEORY, 1979, 13 (01) :29-43

[10] A NOTE ON THE COMPLEXITY OF GENERAL D0L MEMBERSHIP [J].

JONES, ND ;

SKYUM, S .

SIAM JOURNAL ON COMPUTING, 1981, 10 (01) :114-117

← 1 2 →