COMPOSITE BRANCH ALGORITHM TO SOLV SOME PROBLEMS OPTIMIZATION MATH INVOLVING HAMILTON CYCLES BASED ON THE TSP PROBLEM

Abstract

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.