The Estimation of the Individual Travelling Salesman Problem Complexity Extreme Values

This article is about the probability distribution of the maximum of the logarithm of the complexity of an individual travelling salesman problem. The complexity is defined as a number of nodes of the decision tree, which was created by the branch and bound algorithm. We applied our earlier results that the distribution of the logarithm of the complexity of travelling salesman problem can be approximated by the normal distribution. In combination with the representation of the distribution of maximum of normally distributed random variables, we obtain the approximation for the distribution of the maximum of the complexity in cases of infinitely large samples. The accuracy of the approximation was visualized on the graph. In order to simplify the approximation for comparatively small samples, we used the normal distribution with the parameters equal to the expectation and standard deviation of approximation for infinitely large samples. This allowed us to obtain representations for the normal distribution, which approximates the distribution of the maximum of the natural logarithm of the complexity in series of \(m\) travelling salesman problem of size \(n\). The quality of the representations was analysed by the experiment. On the graph, we showed the quantiles of the theoretical distribution of the maximum of the logarithm of the complexity and the sample’s quantiles in the case of samples of 500 and 1000 travelling salesman problem.