Bài toán người bán hàng (Travelling Salesman Problem-TSP)
• Có n thành phố (được đánh số từ 1 đến n), một người bán hàng xuất phát từ một
thành phố, muốn đi qua tất cả các thành phố khác, mỗi thành phố một lần rồi quay về
thành phố xuất phát. Giả thiết biết được chi phí đi từ thành phố i đến thành phố j là
cij.
• Hãy tìm một hành trình cho người bán hàng sao cho tổng chi phí theo hành trình này
là thấp nhất.
• TSP là bài toán thuộc lớp bài toán NP-khó.
TH2-01.CPP
Giải bài toán người bán hàng bằng thuật toán quay lui (hoặc nhánh cận)
TH2-02.CPP
Giải bài toán người bán hàng bằng thuật toán quy hoạch động