The estimation of the complexity of solving a particular travelling salesman problem by quantile-based measures for skewness and kurtosis
Vasiliy A. Goloveshkin, Galina Zhukova, Mikhail Ulyanov, М. И. Фомичев · International journal of open information technologies · 2016
The complexity of solving a particular travelling saleman problem is studied. Complexity is a number of nodes of the decision tree, when a particular problem is being solved by the branch and bound algorithm. A probability distribution of the logarithm of the complexity of a particular TSP is approximately normal. Parameters of the linear transformation of a sample of the logarithm of the complexity into a standard normally distributed sample are obtained by the method of least squares for the sample quantiles. The formulas for the parameters are also given.