THE LANDSCAPE OF THE TRAVELING SALESMAN PROBLEM

被引：72

作者：

STADLER, PF

SCHNABL, W

机构：

[1] MAX PLANCK INST BIOPHYS CHEM,KARL FRIEDRICH BONHOEFFER INST,W-3400 GOTTINGEN,GERMANY

[2] IBM AUSTRIA,A-1020 VIENNA,AUSTRIA

[3] UNIV VIENNA,CTR COMP,A-1090 VIENNA,AUSTRIA

来源：

PHYSICS LETTERS A | 1992年 / 161卷 / 04期

关键词：

D O I：

10.1016/0375-9601(92)90557-3

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

The landscapes of traveling salesman problems are investigated by random walk techniques. The autocorrelation functions for different metrics on the space of tours are calculated. The landscape turns out to be AR (1) for symmetric TSPs. For asymmetric problems there can be a random contribution superimposed on an AR (1) behaviour.

引用

页码：337 / 344

页数：8

共 24 条

[1] LARGE TRAVELING SALESMAN PROBLEMS ARISING FROM EXPERIMENTS IN X-RAY CRYSTALLOGRAPHY - A PRELIMINARY-REPORT ON COMPUTATION
BLAND, RG
SHALLCROSS, DF
[J]. OPERATIONS RESEARCH LETTERS, 1989, 8 (03) : 125 - 128
[2] Bohr H., 1989, Complex Systems, V3, P9
[3] IC INSERTION - AN APPLICATION OF THE TRAVELING SALESMAN PROBLEM
CHAN, D
MERCIER, D
[J]. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 1989, 27 (10) : 1837 - 1841
[4] Feller W., 1972, INTRO PROBABILITY TH
[5] A COMPUTER-MODEL OF EVOLUTIONARY OPTIMIZATION
FONTANA, W
SCHUSTER, P
[J]. BIOPHYSICAL CHEMISTRY, 1987, 26 (2-3) : 123 - 147
[6] PHYSICAL ASPECTS OF EVOLUTIONARY OPTIMIZATION AND ADAPTATION
FONTANA, W
SCHNABL, W
SCHUSTER, P
[J]. PHYSICAL REVIEW A, 1989, 40 (06): : 3301 - 3321
[7] FONTANA W, 1991, IN PRESS MH CHEM
[8] FONTANA W, 1987, THESIS U WIEN
[9] Garey M.R., 1979, COMPUTERS INTRACTABI, V174
[10] GROTSCHEL M, 1984, 38 U AUGSB PREPR

← 1 2 3 →