Thuật toán láng giềng gần nhất

Bài này nói về một thuật toán gần đúng để giải bài toán người bán hàng. Về giải thuật phân loại, xin xem Láng giềng gần nhất (nhận dạng mẫu).

Thuật toán Láng giềng gần nhất là một trong những thuật toán đầu tiên được dùng để tìm lời giải cho bài toán người bán hàng, và thường cho kết quả chênh lệch trong phạm vi 20% so với đường đi tối ưu. Nó chạy nhanh hơn rất nhiều so với việc kiểm tra mọi tuyến đường và một số thuật toán khác.

Các bước của thuật toán:

1. Chọn một nút bất kỳ làm nút xuất phát và đây là nút hiện hành
2. Đánh dấu nút hiện hành là đã được đi qua
3. Tìm một nút chưa đi qua có khoảng cách đến nút hiện hành là ngắn nhất, đánh dấu nút này là nút hiện hành mới
4. Nếu chưa đi qua tất cả các nút thì quay lại bước 2

Thứ tự mà các nút được đi qua chính là kết quả của thuật toán.

Thuật toán láng giềng gần nhất dễ cài đặt và chạy nhanh, nhưng đôi khi nó có thể bỏ qua các tuyến đường ngắn hơn mà mắt thường dễ nhận ra. Kết quả của thuật toán này cần được kiểm tra trước khi sử dụng để phòng trường hợp một tuyến đường ngắn hơn bị bỏ qua.

Trong trường hợp xấu nhất, thuật toán này có thể tính toán ra các tuyến đường dài gấp r lần tuyến đường tối ưu. Trong đó, r là một tỷ lệ tùy ý, nghĩa là, với mỗi hằng số r, tồn tại một bài toán người bán hàng sao cho độ dài của tuyến đường là kết quả của thuật toán láng giềng gần nhất lớn hơn hoặc bằng r lần độ dài tuyến đường tối ưu.

Tham khảo