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 条

[11] KAUFFMAN S, 1988, SFI STUDIES SERIES S
[12] CONFIGURATION SPACE ANALYSIS OF TRAVELING SALESMAN PROBLEMS
KIRKPATRICK, S
TOULOUSE, G
[J]. JOURNAL DE PHYSIQUE, 1985, 46 (08): : 1277 - 1292
[13] Lawler E. L., 1985, WILEY INTERSCIENCE S
[14] EFFECTIVE HEURISTIC ALGORITHM FOR TRAVELING-SALESMAN PROBLEM
LIN, S
KERNIGHAN, BW
[J]. OPERATIONS RESEARCH, 1973, 21 (02) : 498 - 516
[15] EXACT SOLUTION OF LARGE ASYMMETRIC TRAVELING SALESMAN PROBLEMS
MILLER, DL
PEKNY, JF
[J]. SCIENCE, 1991, 251 (4995) : 754 - 761
[16] Papoulis A., 1984, PROBABILITY RANDOM V
[17] Perelson AS, 1991, MOL EVOLUTION RUGGED
[18] SOLVABLE MODEL OF A SPIN-GLASS
SHERRINGTON, D
KIRKPATRICK, S
[J]. PHYSICAL REVIEW LETTERS, 1975, 35 (26) : 1792 - 1796
[19] SORKIN G, 1990, 6TH P ANN MIT C ADV, P331
[20] SORKIN GB, 1988, IBM RC13674 RES REP

← 1 2 3 →