Finding the Best Hamiltonian Cycle as a Solution to Applications of Maximizing the TSP
Hussein A. H. Al-Saeedi, Mushtak A. K. Shiker · 2024
In computational complexity theory, the solution decision export of the traveling salesman problem (TSP) of both Max and Min types belongs to the class of NP-hard problems. So that the running time of any TSP solving algorithm increases dramatically when the number of vertices in the graph increases. Max TSP aims to find the best Hamiltonian cycle that maximizes profits and revenues and this makes its applications multiple in life. In this study, Max TSP is studied in order to develop an algorithm to solve this problem, and through that, the second adjacency matrix algorithm (SAMA) was reached. SAMA is a new algorithm used to find the best Hamiltonian cycle as a solution to TSP when its objective function is maximization. It is able to find the best feasible solution when the problem graph includes any number of vertices and thus its limitation is generalized to$n$vertices in the graph. The results obtained by using SAMA representation for the optimal or near-optimal Hamiltonian cycle within a passable time, as it outperforms most algorithms and techniques that solve TSP in terms of performance excellence and quality of results. Among the reasons that made SAMA distinguished is the design of its clear steps that are compatible with the objective to be reached and its appropriate scientific approach to get rid of the graph edges that have a negative effect on the resulting Hamiltonian cycle.