Numéro
J. Phys. France
Volume 47, Numéro 8, août 1986
Page(s) 1285 - 1296
DOI https://doi.org/10.1051/jphys:019860047080128500
J. Phys. France 47, 1285-1296 (1986)
DOI: 10.1051/jphys:019860047080128500

A replica analysis of the travelling salesman problem

M. Mézard et G. Parisi

Dipartimento di Fisica, Universita' di Roma I, Piazzale Aldo Moro 2, 00185 Roma, Italy


Abstract
We propose and analyse a replica symmetric solution for random link travelling salesman problems. This gives reasonable analytical estimates for thermodynamic quantities such as the length of the shortest path.


Résumé
Nous proposons et analysons une solution symétrique dans les répliques des problèmes de voyageurs de commerce à liens indépendants. Elle fournit des estimations analytiques raisonnables pour les quantités thermodynamiques comme la longueur du chemin le plus court.

PACS
0540 - Fluctuation phenomena, random processes, noise, and Brownian motion.
0550 - Lattice theory and statistics (Ising, Potts, etc.).

Key words
lattice theory and statistics -- random processes