Publication

The N-city travelling salesman problem: statistical mechanics and metropolis algorithm

1984
Journal Articles

Abstract

In any N-city travelling salesman problem there are (N-1)!/2 possible tours. We use the Metropolis algorithm to generate a sequence of such tours. This sequence may be viewed as the random evolution of a physical system in contact with a heat-bath. As the temperature is lowered, the tours gererated approach the optimal tour. It appears for large N one arrives within a few percent of the optimal solution in better than quadratic time.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

1984
Journal Articles

Abstract

Official source

Related concepts (25)

Travelling salesman problem

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research. The travelling purchaser problem and the vehicle routing problem are both generalizations of TSP.

Optimization problem

In mathematics, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables are continuous or discrete: An optimization problem with discrete variables is known as a discrete optimization, in which an object such as an integer, permutation or graph must be found from a countable set.

Computational problem

In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring "Given a positive integer n, find a nontrivial prime factor of n." is a computational problem. A computational problem can be viewed as a set of instances or cases together with a, possibly empty, set of solutions for every instance/case. For example, in the factoring problem, the instances are the integers n, and solutions are prime numbers p that are the nontrivial prime factors of n.

Related publications (9)

The N-city travelling salesman problem: statistical mechanics and metropolis algorithm

Chat with Graph Search

A Unified Framework for Modelling Modern Relational Network Data

Real-Time Optimizing Control of an Experimental Crosswind Power Kite

Models and Heuristics for the Tactical Berth Allocation Problem with Quay-Crane Assignment and Transshipment Quadratic Costs