Tiểu Luận Bài Toán đường đi người giao hàng

Bài toán đường đi người giao hàng (TSP - Traveling Salesman Problem) được phát biểu như sau: 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.
Đây là một bài toán kinh điển và nổi tiếng. Bài toán này có nhiều phương pháp để giải và một trong những phương pháp đó là dùng kỹ thuật quy hoạch động. Kỹ thuật quy hoạch động là kỹ thuật giải quyết vấn đề bằng cách chia vấn đề thành các vấn đề con. Đây là một phương pháp tính nghiệm của các bài toán từ nhỏ đến lớn và ghi lại các kết quả đã tính được. Khi tính nghiệm của bài toán lớn thông qua nghiệm của các bài toán con, ta chỉ việc sử dụng các kết quả đã được ghi lại. Điều đó giúp ta tránh được phải tính nhiều lần nghiệm của cùng một bài toán con. Thuật toán được thiết kế bằng kỹ thuật quy hoạch động sẽ là thuật toán lặp. Để thuận tiện cho việc sử dụng lại nghiệm của các bài toán con, chúng ta lưu lại các nghiệm đã tính vào một bảng (thông thưòng là mảng 1 chiều hoặc 2 chiều).
Tóm lại, để giải một bài toán bằng quy hoạch động, chúng ta cần thực hiện các bước sau:
· Đưa ra cách tính nghiệm của các bài toán con đơn giản nhất.
· Tìm ra các công thức (hoặc các quy tắc) xây dựng nghiệm của bài toán thông qua nghiệm của các bài toán con.
· Thiết kế bảng để lưu nghiệm của các bài toán con.
· Tính nghiệm của các bài toán con từ nhỏ đến lớn và lưu vào bảng.
· Xây dựng nghiệm của bài toán từ bảng.