Những ai từng tham gia vào ngành kinh doanh sẽ hiểu rằng việc di chuyển từ thành phố này đến thành phố khác là một phần quan trọng trong công việc. Tuy nhiên, đôi khi việc tìm đường đi ngắn nhất để ghé thăm một số lượng lớn thành phố lại trở nên đáng ghen tỵ. Đó chính là thách thức mà bài toán người bán hàng (TSP) đặt ra.
Bài toán người bán hàng (TSP)
Bài toán người bán hàng đòi hỏi tìm một tuyến đường ngắn nhất đi qua tất cả các thành phố một lần duy nhất và quay trở lại thành phố xuất phát. Điều này khác biệt so với vòng Hamilton, nơi mục tiêu là tìm một tuyến đường đi qua mọi thành phố một lần duy nhất. Bài toán TSP rất nổi tiếng và thuộc loại NP-khó, tức là chưa có giải pháp thời gian đa thức cho bài toán này.
Dưới đây là một số giải pháp khác nhau cho bài toán người bán hàng.
Giải pháp ngây thơ
- Chọn thành phố 1 làm điểm bắt đầu và kết thúc.
- Tạo ra tất cả các hoán vị (n-1)! của các thành phố.
- Tính toán chi phí cho mỗi hoán vị và theo dõi hoán vị có chi phí nhỏ nhất.
- Trả về hoán vị có chi phí nhỏ nhất.
Độ phức tạp thời gian: ?(n!)
Lập trình động
Ý tưởng giải quyết bài toán bằng phương pháp lập trình động như sau:
- Đặt tất cả các thành phố trong tập hợp {1, 2, 3, ..., n}, với 1 là điểm bắt đầu và kết thúc. Đối với mỗi thành phố I (khác 1), chúng ta tìm đường đi có chi phí nhỏ nhất từ 1 đến I và đi qua tất cả các thành phố đúng một lần. Gọi chi phí của đường đi này là cost(i), và chi phí của chu trình tương ứng là cost(i) + dist(i, 1), trong đó dist(i, 1) là khoảng cách từ I đến 1. Cuối cùng, chúng ta trả về giá trị nhỏ nhất trong tất cả các giá trị [cost(i) + dist(i, 1)].
Dưới đây là giải pháp lập trình động sử dụng phương pháp đệ quy từ trên xuống và ghi nhớ:
def tsp_dp(mask, pos):
if mask == (1 << n) - 1:
return dist[pos][0]
if dp[mask][pos] != -1:
return dp[mask][pos]
ans = float('inf')
for i in range(1, n):
if mask&(1<Độ phức tạp thời gian: O(n^22^n), trong đó O(n2^n) là số lượng tối đa các bài toán con/ trạng thái duy nhất và O(n) cho quá trình chuyển đổi (qua vòng lặp như trong mã code) trong mỗi trạng thái.
Không gian phụ: O(n*2^n), trong đó n là số lượng đỉnh/ thành phố.
Tuy giải pháp này có thời gian chạy ít hơn O(n!), nhưng vẫn không thể khả thi ngay cả với một số lượng các đỉnh nhỏ hơn một chút. Tiếp theo, chúng ta sẽ nghiên cứu các thuật toán xấp xỉ cho bài toán người bán hàng.
Kết luận
Bài toán người bán hàng là một trong những bài toán kinh điển trong lĩnh vực trí tuệ nhân tạo và tối ưu hóa. Mặc dù chưa có giải pháp tối ưu cho bài toán này, nhưng lập trình động đang được sử dụng để tìm giải pháp gần đúng. Hi vọng với sự phát triển của khoa học và công nghệ, chúng ta sẽ có thể giải quyết bài toán người bán hàng một cách hiệu quả hơn trong tương lai.
Tiếp theo: Bài toán người bán hàng | Phần 2
Tham khảo:
- http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
- http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf
Mua khóa học, hoàn thành 90% trong 90 ngày và tiết kiệm 90% chi phí. Nhấn vào đây để khám phá
