Bài toán người bán hàng
Bách khoa toàn thư mở Wikipedia
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.