Bài viết sưu tầm

Bài toán người bán hàng (Traveling Saleman Problem)

Bài toán yêu cầu tìm đường đi ngắn nhất cho nhân viên bán hàng (traveling saleman), nhân viên bán hàng xuất phát từ một thành phố, đi qua lần lượt tất cả các thành phố có trong lộ trình duy nhất một lần và quay về thành phố ban đầu với chi phí thấp nhất.

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 này được đưa ra vào thế kỷ thứ XVII bởi hai nhà toán học người Anh là Sir William Rowan Hamilton và Thomas Penyngton Kirkman, và được lưu lại trong giáo trình Lý thuyết đồ thị nổi tiếng của Oxford. Sau đó bài toán trở thành bài toán khó thách thức toàn thể các nhà toán học và tin học trên thế giới bởi độ phức tạp thuật toán tăng theo hàm số mũ (thuộc lớp bài toán toán NP-khó).

Các nhà khoa học bắt đầu tiếp cận bài toán, thử làm trên máy tính và công bố các kết quả giải bài toán này từ năm 1954 (49 đỉnh), và  năm 2004 bài toán giải được với số đỉnh là 24.978, và càng ngày càng tăng cao.