THUẬT TOÁN NHÁNH CẬN GIẢI MỘT SỐ BÀI TOÁN TỐI ƯU LIÊN QUAN ĐẾN CHU TRÌNH HAMILTON DỰA TRÊN BÀI TOÁN TSP

Tóm tắt

Bài toán Người du lịch (TSP) là một bài toán tối ưu tổ hợp quan trọng, yêu cầu tìm chu trình ngắn nhất đi qua tất cả các đỉnh đúng một lần. Do thuộc nhóm NP-khó, TSP đòi hỏi các phương pháp giải mạnh để tìm lời giải tối ưu. Thuật toán nhánh cận (Branch and Bound – BnB) là một cách tiếp cận hiệu quả cho bài toán này. BnB chia nhỏ không gian tìm kiếm, tính cận dưới cho từng nhánh và loại bỏ các nhánh không khả thi, giúp giảm số phép thử so với quay lui truyền thống. Bài viết trình bày chi tiết cách áp dụng BnB vào TSP, bao gồm mô tả thuật toán, ví dụ minh họa và đánh giá thực nghiệm. Kết quả cho thấy BnB hoạt động tốt với bài toán có quy mô nhỏ và vừa, nhưng thời gian xử lý tăng nhanh khi số lượng đỉnh lớn. Tác giả đề xuất kết hợp BnB với các phương pháp heuristic và tối ưu lưu trữ để nâng cao hiệu quả khi giải các bài toán TSP lớn trong thực tế.