This is the question that comes to my mind when I play a game called QuickyRoute,which essentially a Hamilton graph problem,the game will randomly generate a number of points,you need to draw the undirected complete graph with the smallest sum of distances.
As the difficulty of the game increases, the more points, the harder it is to find the correct answer.I want to solve these problems through programming. Obviously there are at most half of n factorial possibilities.
But enumeration is not very convenient, Because this is a famous graph theory problem,I want to ask if there is a better algorithm idea or some excellent papers can refer to this game
The problem is actually equivalent to the traveling salesman problem, except we don't have to return to where we started. The general traveling salesman problem is an NP-hard problem in theoretical computer science. Furthermore, it is well-known that the traveling salesman problem cannot even be approximated within a constant factor.
However, it seems like the problem you have listed is actually a special case of the traveling salesman problem, known as the metric traveling salesman problem (i.e., an instance of the traveling salesman problem in which the triangle inequality holds). Unfortunately, the metric traveling salesman problem is still NP-hard, which means that you will probably not be able to find any efficient algorithms that compute an optimal solution when the number of vertices gets even moderately large. However, there are efficient polynomial-time approximation schemes (EPTAS) that can approximate solutions to the metric traveling salesman within a constant factor.
The best approximation heuristic currently known is Christofides algorithm, which was discovered in 1976. Christofides's algorithm is a $3/2$-approximation, which means that it guarantees that its solutions will be within a factor of $3/2$ of the optimal solution length.