APPLICATIONS OF BRANCH-BOUND ALGORITHM TO SOLVE SOME OPTIMAL PROBLEMS RELATED TO THE HAMILTONIAN CYCLE BASED ON THE TSP

Abstract

The Traveling Salesman Problem (TSP) is the most prominent of the combinatorial optimization problems that belongs to NP-Hard. The best algorithm for solving TSP is the branch-bound algorithm with exponential-time complexity. This paper presents how to use the branch-bound algorithm to solve some of the combinatorial optimization problems related to the Hamiltonian cycle based on the TSP.

Keywords

• bài toán người du lịch
• bài toán tối ưu tổ hợp
• chu trình hamilton
• đường hamilton
• np-đầy đủ
• np-khó
• thuật toán nhánh-cận.