Predicting the difficulty of TSP instances using MST
- Resource Type
- Conference
- Authors
- Sengupta, Lahari; Franti, Pasi
- Source
- 2019 IEEE 17th International Conference on Industrial Informatics (INDIN) Industrial Informatics (INDIN), 2019 IEEE 17th International Conference on. 1:847-852 Jul, 2019
- Subject
- Components, Circuits, Devices and Systems
Computing and Processing
Power, Energy and Industry Applications
Robotics and Control Systems
Signal Processing and Analysis
Travelling salesman problem
open loop TSP
MST
human performance
instance complexity
- Language
- ISSN
- 2378-363X
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.