Goodness of cycles and Hamiltonian paths

Abstract

Introduction. The problem of finding an optimal Hamiltonian cycle on a set of complex plane points (TSP) is a well-known open problem. If the number of points is small, we can simply calculate all the possible cycles and stay with a shorter one, but this strategy is not viable when the number of points is large. Historically the problem has been addressed by building partitions of the plane containing a small number of vertices, in these subsets it is easy to determine optimal cycles and finally design appropriate strategies to paste the previous paths thus obtaining an approximation of the solution to the problem posed (see [4]) We have designed (see [1]) an algorithm that, in a reasonable time and in a personal computer, gives us a solution to the problem posed although the number of points is large. In this algorithm we propose a different strategy, we consider a partition of the set of points V in its different levels of convexity {V1, V2, ··· , Vp}, thinking that the geometry of the distribution of the points would facilitate the connection between the different elements of the partition. [...]