Bài toán người bán hàng

Bách khoa toàn thư mở Wikipedia

Nếu người bán hàng xuất phát từ điểm A, và nếu khoảng cách giữa hai điểm bất kì được biết thì đâu là đường đi ngắn nhất mà người bán hàng có thể thực hiện được sao cho đi hết tất cả các điểm mỗi điểm một lần để quay về lại điểm A ban đầu?

Bài toán người bán hàng (tiếng Anh: travelling salesman problem - TSP) là một bài toán thuộc tối ưu rời rạc hay tổ hợp. Đây là một minh họa điển hình cho lớp bài toán trong lý thuyết độ phức tạp tính toán thuộc loại tương đối khó giải.

[sửa] Phát biểu

Có một người giao hàng cần đi giao hàng tại n thành phố. Xuất phát từ một thành phố nào đó, đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu. Mỗi thành phố chỉ đến một lần, khoảng cách từ một thành phố đến các thành phố khác là xác định được. Hãy tìm một chu trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh là nhỏ nhất.

[sửa] Xem thêm

[sửa] Liên kết ngoài

Tiếng Anh:

Demo applet of a genetic algorithm solving TSP and VRPTW online
TSPLIB
lalena.com: TSP Solution in C#.NET (downloadable or run as applet) using Genetic Algorithms
Travelling Salesman Problem at Georgia Tech
Private web page with 2 algorithms & demo program to download
Example of finding approximate solution of TSP problem using a genetic algorithm
A Java implementation of a TSP-solution using JGAP (Java Genetic Algorithms Package). The technique used is a Genetic Algorithm.
Solution of the Travelling Salesman Problem using a Kohonen Map
Kohonen Neural Network applied to the Traveling Salesman Problem (using three dimensions).
Most TSP loop families grow polynomially Private web page shows that a method exists for obtaining a set of optimal "travelling salesman" routes that is a member of a family that grows no faster than about 2ⁿIn2. However, even for large n, the method yields a polynomial rate for most sets of fields of nodes.
VisualBots - Freeware multi-agent simulator in Microsoft Excel. Sample programs include genetic algorithm, ACO, and simulated annealing solutions to TSP.
Work-in-progress attempted proof on private web page of polynomial calculation time on the 2-D undirected graph.
Links to TSP source codes
http://www.delphiforfun.org/Programs/traveling_salesman.htm The Travelling Salesman Problem (TSP) requires that we find the shortest path visiting each of a given set of cities and returning to the starting point.
CONCORDE Home of the CONCORDE TSP Solver, an ANSI C library dedicated to solving the TSP problem.