Bài toán Người bán hàng Vận trù học

Bài toán người bán hàng (TSP)

Giới thiệu:
Bài toán người bán hàng (tiếng Anh: travelling salesman problem – viết tắt TSP - NBS) là một bài toán Vận trù học 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 loạt 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.
Người biên soạn (NBS) đã có 2 Bài gửi trước dưới hình thức trương tự “Vẽ 1 nét”
Bài “Người đưa thư” và “Bài toán 7 cây cầu”. Nhiều bạn muốn tham khảo thêm , chúng tôi giới thiệu 1 bài sau thuộc dang bài toán mẫu













Giải :
1/- Nếu đúng như dữ kiện và câu hỏi của bài toán nêu trên thì có thể trả lời ngay: “Không thể thực hiện được”..Vì có 4 điểm mút lẻ (xin xem thêm bài “Vẽ 1 nét” hoăc “Bài toán 7 cây cầu” ). ĐS vô nghiệm

2/- Nếu câu hỏi đặt ra là: “Hãy tim đường đi 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 với quãng đường ngắn nhất”. Trường hợp này là “Bài toán tối ưu, thuộc Vận trù học”
Vì 4 điểm A, B, C, D tạo thành tứ giác ( với 2 đường chéo AC cắt nhau tại E)
Nếu phải đi lại 2 lần thì chọn 1 trong 2 đường chéo có độ dài nhỏ hơn để đi là đáp án tối ưu ( Hình 2 )
















3/- Nếu câu hỏi đặt ra là: “Hãy tim đường đi mà người bán hàng có thể thực hiện để đi hết tất cả các điểm và đi hết các đoạn đường sao cho quãng đường (số đo trên Hình 3) phải đi ngắn nhất”. Trường hợp này là “Bài toán “Vẽ 1 nét” ứng dụng thực tế.
Nếu phải đi lại 2 lần thì chọn 2 cạnh của tứ giác có độ dài nhỏ hơn để đi
tất cả các điểm và đi hết các đoạn đường ( Hình 3)













Bài Thực hành:
Giải bài toán trên với điều kiên “Đi hết 5 điểm và đi hết các đoạn đương như hình vẽ với thời gian nhanh nhất. Biêt tôc độ đi theo cạnh tứ giác chậm hơn đi theo đường chéo 1,5 lần” ( độ dài các đoạn vẫn như hình 3)