Giải thích bài toán người bán hàng
Hãy đưa cho một người bán hàng danh sách các thành phố và yêu cầu chuyến đi ngắn nhất ghé thăm mỗi thành phố một lần rồi trở về nhà. Ai cũng có thể kiểm tra một lộ trình được đề xuất, và ai cũng có thể cải thiện một lộ trình tồi chỉ bằng mắt, vậy mà chưa ai biết một phương pháp nhanh luôn tìm ra lộ trình tốt nhất. Bài toán người bán hàng đã trở thành ví dụ tiêu biểu cho một bài toán khó, và những phương pháp được tạo ra để chinh phục nó ngày nay đang lên kế hoạch giao hàng, khoan bảng mạch và lắp ráp bộ gen.
Bài toán
Một hành trình ghé thăm mỗi thành phố đúng một lần và kết thúc tại nơi xuất phát; độ dài của nó là tổng các khoảng cách dọc đường. Nhiệm vụ là tìm hành trình ngắn nhất. Trong phiên bản ở đây, khoảng cách là các đường thẳng trên bản đồ, nên đi từ A đến C không bao giờ dài hơn đi qua B: đây là bài toán người bán hàng metric. Câu đố này được nhà toán học Karl Menger bàn đến vào khoảng năm 1930, và cái tên trở nên phổ biến trong những thập niên sau đó, khi các nhà toán học tại RAND Corporation bắt tay nghiên cứu nó.
Sự bùng nổ của số hành trình
Hãy cố định thành phố xuất phát. Có n − 1 lựa chọn cho thành phố tiếp theo, n − 2 cho thành phố sau đó, và cứ thế, mà mỗi hành trình lại có thể đi theo hai chiều, nên có (n − 1)! / 2 hành trình. Với 10 thành phố con số đó là 181.440, dễ dàng với máy tính. Với 20 thành phố là khoảng 6 × 10¹⁶, và với 70 thành phố nó vượt quá số nguyên tử trong vũ trụ quan sát được. Máy tính nhanh hơn cũng không giúp được nhiều: mỗi thành phố thêm vào nhân khối lượng công việc lên khoảng n lần.
NP-khó
Năm 1972, Richard Karp chỉ ra rằng câu hỏi liệu một đồ thị có hành trình khép kín đi qua mọi đỉnh hay không, tức một chu trình Hamilton, thuộc về một họ các bài toán NP-đầy đủ đều khó như nhau. Bài toán người bán hàng chứa câu hỏi đó, nên nó là NP-khó. Một phương pháp nhanh cho nó sẽ cho ra các phương pháp nhanh cho hàng nghìn bài toán khác trong lập lịch, hậu cần và mật mã học. Liệu có tồn tại phương pháp như vậy hay không chính là câu hỏi P so với NP, một trong các Bài toán Thiên niên kỷ.
Một phương pháp chính xác: Held–Karp
Năm 1962, Michael Held và Richard Karp, cùng với Richard Bellman một cách độc lập, đã dùng quy hoạch động. Với mỗi tập thành phố S và mỗi thành phố j thuộc S, hãy tính đường đi ngắn nhất bắt đầu từ thành phố nhà, ghé thăm đúng các thành phố của S và kết thúc tại j. Mỗi giá trị được suy ra từ các giá trị của S không có j, nên bảng được điền từ các tập nhỏ đến các tập lớn, và hành trình ngắn nhất xuất hiện ở cuối. Phương pháp cần khoảng n² · 2ⁿ bước thay vì n!, với 30 thành phố đó là khác biệt giữa vài phút và tuổi của vũ trụ, nhưng nó vẫn tăng theo hàm mũ.
Các quy tắc dựng nhanh
Láng giềng gần nhất luôn đi tới thành phố gần nhất chưa ghé thăm. Cách này đơn giản và nhanh, nhưng có xu hướng bỏ sót vài thành phố mà cuối cùng phải đi đường vòng dài để ghé, nên hành trình của nó thường dài hơn hành trình tốt nhất khoảng 25%. Các phương pháp chèn thì ngược lại, luôn giữ một vòng khép kín và lần lượt thêm từng thành phố còn lại vào chỗ tốn ít nhất. Năm 1976, Nicos Christofides tìm ra một cách dựng được bảo đảm không quá 1,5 lần giá trị tối ưu trên mọi bản đồ metric, một giới hạn gần như không bị vượt qua suốt hơn bốn mươi năm.
Cải thiện hành trình: 2-opt
Tìm kiếm cục bộ bắt đầu từ một hành trình bất kỳ và liên tục thực hiện những thay đổi nhỏ giúp rút ngắn nó. Nước đi kinh điển 2-opt bỏ đi hai cạnh rồi nối lại hai đoạn theo cách ngược lại, làm đảo chiều đoạn nằm giữa. Mỗi khi hai cạnh cắt nhau, nước đi này gỡ chỗ cắt và tiết kiệm độ dài, nên một hành trình mà 2-opt không cải thiện được nữa thì không bao giờ tự cắt. Trên các bản đồ ngẫu nhiên, hành trình của 2-opt thường dài hơn giá trị tối ưu khoảng 5%. Những nước đi mạnh hơn hoán đổi ba cạnh, hay phương pháp độ sâu biến đổi của Lin và Kernighan năm 1973, còn tiến gần hơn nữa.
Mô phỏng luyện kim
Tìm kiếm cục bộ có thể mắc kẹt ở một hành trình mà mọi nước đi đơn lẻ đều làm nó tệ hơn, dù tồn tại một hành trình tốt hơn nhiều. Mô phỏng luyện kim, được Scott Kirkpatrick, Daniel Gelatt và Mario Vecchi áp dụng cho bài toán này năm 1983, vay mượn ý tưởng từ ngành luyện kim: nó chấp nhận một nước đi tệ hơn với xác suất phụ thuộc vào nhiệt độ, lúc đầu cao rồi giảm dần. Lúc đầu hành trình lang thang tự do; về cuối chỉ những cải thiện mới được chấp nhận. Nếu làm nguội đủ chậm, phương pháp này tìm được những hành trình rất tốt một cách đáng tin cậy.
Tự khám phá
Hãy mở bản minh họa bài toán người bán hàng để đặt tối đa 200 thành phố một cách ngẫu nhiên, trên đường tròn, thành cụm, trên lưới hoặc ở bất cứ đâu bạn nhấp. Xem láng giềng gần nhất bỏ sót những thành phố cuối, xem 2-opt gỡ từng chỗ cắt nhau, theo dõi nhiệt độ của mô phỏng luyện kim khi nó nguội dần, và để Held–Karp chứng minh hành trình ngắn nhất cho tối đa 12 thành phố. So sánh tất cả chạy mọi phương pháp trên cùng một bản đồ và cho thấy mỗi hành trình dài hơn hành trình ngắn nhất tìm được bao nhiêu.
Câu hỏi thường gặp
Bài toán người bán hàng được dùng ở đâu?
Ở bất cứ nơi nào cần ghé thăm nhiều địa điểm theo một thứ tự hiệu quả: các tuyến giao hàng và thu gom, đường đi của mũi khoan hay tia laser trên bảng mạch, thứ tự kính thiên văn quan sát các ngôi sao, thứ tự lấy hàng trong kho, và, với các khoảng cách khác, thứ tự các đoạn khi lắp ráp một trình tự DNA.
Bài toán lớn nhất từng được giải chính xác là bao nhiêu?
Năm 1954, George Dantzig, Ray Fulkerson và Selmer Johnson đã chứng minh hành trình ngắn nhất qua 49 thành phố ở Hoa Kỳ. Năm 2006, bộ giải Concorde của David Applegate, Robert Bixby, Vašek Chvátal và William Cook đã chứng minh hành trình tối ưu qua 85.900 điểm lấy từ một thiết kế vi mạch, sau nhiều năm thời gian máy tính.
Hành trình ngắn nhất có luôn không có chỗ cắt nhau không?
Có, trên một bản đồ phẳng với khoảng cách đường thẳng. Nếu hai cạnh cắt nhau, việc thay chúng bằng hai cạnh của tứ giác mà chúng tạo thành sẽ rút ngắn hành trình, nên một hành trình có chỗ cắt nhau không thể là ngắn nhất.
Các phương pháp heuristic có luôn cho cùng một hành trình không?
Láng giềng gần nhất, chèn rẻ nhất và 2-opt như được dùng ở đây là tất định: trên cùng các thành phố, chúng cho cùng một hành trình. Mô phỏng luyện kim bắt đầu từ một hành trình ngẫu nhiên và thực hiện các nước đi ngẫu nhiên, nên hai lần chạy có thể kết thúc với các hành trình khác nhau, thường có độ dài gần như bằng nhau.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Mở bản minh họa bài toán người bán hàng