Predicting the difficulty of TSP instances using MST
Lahari Sengupta, Pasi Fränti · 2019
The efforts needed to solve travelling salesman problems (TSP) obviously depend on the problem size. However, also other factors can predict the difficulty of a given problem instance. We present a measure based on the minimum spanning tree (MST). The measure counts the number of knot points, which branch the tree into multiple sub-trees. We show by experiments that the more there are knots in the tree, the more difficult the problem instance is to solve by both humans and computers.