- Hành trình
- Ngắn nhất tìm được
- Xuất phát
| Phương pháp | Độ dài | Dài hơn ngắn nhất | Số bước |
|---|---|---|---|
| - | - | - | |
| - | - | - | |
| - | - | - | |
| - | - | - | |
| - | - | - |
Bài toán người bán hàng
Một người bán hàng phải ghé thăm mỗi thành phố đúng một lần rồi trở về nhà. Thứ tự nào làm cho chuyến đi ngắn nhất? Câu hỏi thì dễ đặt ra, nhưng khi số thành phố tăng lên, việc trả lời bằng cách thử mọi thứ tự là vô vọng: chỉ 30 thành phố đã cho phép khoảng 4,4 × 10³⁰ hành trình khép kín. Hãy rải các thành phố lên bản đồ hoặc tự nhấp để đặt, rồi xem các quy tắc kinh nghiệm nhanh, những cải tiến khéo léo và một phương pháp chính xác dựng hành trình từng bước, và xem các phương pháp nhanh tiến gần đến mức nào. Hãy chọn cách bố trí các thành phố và số lượng thành phố, chọn một phương pháp rồi nhấn Giải để xem nó dựng một hành trình khép kín từng bước, hoặc nhấn Bước để đi từng nước một. Nhấp vào bản đồ để thêm một thành phố, hoặc nhấp vào một thành phố để xóa nó. So sánh tất cả chạy mọi phương pháp trên cùng các thành phố và cho thấy mỗi phương pháp cách hành trình ngắn nhất tìm được bao xa. Thành phố màu đỏ là nơi hành trình bắt đầu.
Cách nó hoạt động
- Hãy chọn một cách bố trí và số thành phố, hoặc nhấp vào bản đồ để tự đặt thành phố và nhấp vào một thành phố để xóa nó.
- Chọn một phương pháp rồi nhấn Giải để xem từng bước, hoặc nhấn Bước để đi từng nước một.
- Nhấn So sánh tất cả để chạy mọi phương pháp trên cùng các thành phố và xem mỗi hành trình dài hơn hành trình ngắn nhất tìm được bao nhiêu.
Vì sao bài toán khó
Với n thành phố có (n − 1)! / 2 hành trình khép kín khác nhau, vì việc bắt đầu từ đâu hay đi theo chiều nào không quan trọng. Con số đó là 12 với 5 thành phố, 181.440 với 10 thành phố và khoảng 6 × 10¹⁶ với 20 thành phố. Chưa có phương pháp nào được biết là tìm được hành trình ngắn nhất cho mọi bản đồ trong thời gian chỉ tăng như một lũy thừa của n; bài toán này là NP-khó. Phương pháp chính xác tốt nhất trong ứng dụng này, quy hoạch động Held–Karp từ năm 1962, vẫn cần khoảng n² · 2ⁿ bước, nên ở đây chỉ giới hạn ở 12 thành phố.
Hành trình tốt, nhanh chóng
Trên thực tế, những hành trình gần ngắn nhất được tìm ra rất 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 và thường cho kết quả dài hơn hành trình tốt nhất khoảng 25%. Chèn rẻ nhất mở rộng dần một vòng khép kín và thêm vào thành phố nào làm vòng dài ra ít nhất. 2-opt lấy một hành trình bất kỳ và liên tục thay hai cạnh bằng hai cạnh ngắn hơn, nhờ đó loại bỏ mọi chỗ cắt nhau và thường chỉ còn chênh khoảng 5%. Mô phỏng luyện kim thực hiện các nước đi 2-opt ngẫu nhiên và, khi còn “nóng”, chấp nhận cả một số nước làm hành trình dài hơn, nhờ vậy có thể thoát khỏi ngõ cụt trước khi ổn định.
Câu hỏi thường gặp
Có công thức nào cho đường đi ngắn nhất không?
Không. Hành trình ngắn nhất phụ thuộc vào vị trí chính xác của tất cả các thành phố, và chưa có phương pháp nào được biết là tìm được nó cho mọi bản đồ mà trong trường hợp xấu nhất không cần một khối lượng công việc tăng theo hàm mũ. Với vài trăm hay vài nghìn thành phố, các bộ giải chính xác chuyên dụng như Concorde vẫn chứng minh được hành trình tối ưu bằng cách kết hợp quy hoạch tuyến tính với kỹ thuật cắt tỉa khéo léo, và bài toán lớn nhất được giải chính xác cho đến nay có 85.900 điểm.
Vì sao 2-opt loại bỏ mọi chỗ cắt nhau?
Nếu hai cạnh của một hành trình cắt nhau, bốn thành phố mà chúng nối tạo thành một tứ giác có hai đường chéo chính là hai cạnh đó. Thay chúng bằng hai cạnh đối diện của tứ giác luôn ngắn hơn, theo bất đẳng thức tam giác, và đảo ngược đoạn hành trình ở giữa. 2-opt tiếp tục thực hiện những phép đổi như vậy cho đến khi không phép nào còn giúp ích, nên hành trình cuối cùng của nó không bao giờ tự cắt.
Nhiệt độ trong mô phỏng luyện kim là gì?
Nó điều khiển mức độ sẵn sàng của phương pháp trong việc chấp nhận một nước đi làm hành trình dài hơn. Một nước đi làm độ dài tăng thêm d được chấp nhận với xác suất e^(−d/T). Ở nhiệt độ T cao, gần như nước nào cũng được chấp nhận, giúp hành trình thoát khỏi một cách sắp xếp kém; khi T giảm, phương pháp trở nên tham lam và ổn định. Tên gọi xuất phát từ việc làm nguội kim loại thật chậm để các nguyên tử của nó tìm được một cách sắp xếp có năng lượng thấp.
Vì sao phương pháp chính xác chỉ giới hạn ở 12 thành phố?
Held–Karp lưu đường đi ngắn nhất cho mọi tập con các thành phố và mọi thành phố cuối có thể, tức khoảng n · 2ⁿ con số, và tính mỗi số bằng n phép so sánh. Với 12 thành phố đó là vài trăm nghìn bước; với 25 thành phố sẽ là hàng tỷ. Dù vậy, cách này vẫn nhanh hơn rất nhiều so với thử tất cả (n − 1)! / 2 hành trình: với 12 thành phố con số đó là gần 20 triệu.
Có dữ liệu nào được gửi lên máy chủ không?
Không. Các thành phố và cả năm phương pháp đều chạy trong trình duyệt của bạn. Những thành phố bạn nhấp để thêm được lưu trong bộ nhớ cục bộ của trình duyệt này.
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.
Tới trình chỉnh sửa