Vì sao không thử hết các cách đi
Với n điểm, số vòng đi khác nhau xấp xỉ (n−1)!/2. Với 70 điểm, con số này lớn hơn số nguyên tử trong vũ trụ quan sát được. Không máy nào thử hết được, nên ta cần thuật toán cho lời giải tốt trong thời gian ngắn.
Bước một: tham lam
Đứng ở kho, luôn đi tới điểm gần nhất chưa ghé. Nhanh và dễ hiểu. Nhược điểm: về cuối, những điểm bị bỏ sót nằm rải rác, buộc lộ trình chạy ngang qua những đoạn đã đi và tạo ra các đường cắt chéo.
while (tour.length < n) {
const c = tour[tour.length - 1];
let best = -1, bd = Infinity;
for (let j = 0; j < n; j++) if (!used[j]) {
const d = dist(c, j);
if (d < bd) { bd = d; best = j; }
}
used[best] = 1; tour.push(best);
}Bước hai: gỡ nút
Một lộ trình có hai đoạn cắt nhau luôn có thể rút ngắn: đảo ngược phần lộ trình nằm giữa hai đoạn đó. Thuật toán 2‑opt thử mọi cặp đoạn. Nếu đổi giúp ngắn hơn thì đổi, lặp lại cho tới khi không còn cặp nào cải thiện được.
for (let i = 1; i < n - 1; i++) for (let j = i + 1; j < n; j++) {
const a = t[i - 1], b = t[i], c = t[j], d = t[(j + 1) % n];
if (dist(a, c) + dist(b, d) < dist(a, b) + dist(c, d)) {
reverse(t, i, j); // gỡ một nút
improved = true;
}
}Dùng vào đâu
- Giao hàng và thu gom
- Lịch tuần tra, kiểm tra hiện trường
- Thứ tự khoan, cắt trên máy công nghiệp
- Bất kỳ việc gì phải ghé nhiều điểm rồi quay về
Trong thí nghiệm trên trang, hoạt hình được làm chậm để mắt người theo kịp. Con số "thời gian máy tính thật" hiển thị bên cạnh mới là tốc độ thật của thuật toán.