Treffer: COMPOSITE BRANCH ALGORITHM TO SOLV SOME PROBLEMS OPTIMIZATION MATH INVOLVING HAMILTON CYCLES BASED ON THE TSP PROBLEM ; 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

The Traveling Sparrow Problem (TSP) is an important combinatorial optimization problem that requires finding the shortest path that visits all vertices exactly once. Because it belongs to the NP-hard group, TSP requires robust methods to find the optimal solution. The Branch and Bound (BnB) algorithm is an effective approach to this problem. BnB divides the search space, computes a lower bound for each branch, and eliminates infeasible branches, which reduces the number of trials compared to traditional backtracking. This paper presents in detail how to apply BnB to TSP, including algorithm description, illustrative examples, and experimental evaluation. The results show that BnB works well for small and medium-sized problems, but the processing time increases rapidly when the number of vertices is large. The author proposes to combine BnB with heuristic methods and storage optimization to improve the efficiency when solving large TSP problems in practice. ; 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ế.