• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Menu

Article

ОЦЕНКА ПАРАМЕТРОВ РАСПРЕДЕЛЕНИЯ ЛОГАРИФМА СЛОЖНОСТИ ЗАДАЧИ КОММИВОЯЖЕРА

The complexity of the individual traveling salesman problem was analyzed by means of mathematical statistics. The complexity is defined as a number of nodes of the decision tree created by the branch and bound algorithm. We obtained approximate representations for parameters of probability distribution of the natural logarithm of the complexity. These representations are functions of the dimension of the problem. The linear function is used to construct the upper estimation for the quantiles of the natural logarithm of the complexity, in cases when the level of the quantile is more than 0.5. We also applied this formula for the lower bound of the quantiles of levels less than 0.5. Then we used the normal distribution with the parameters and as an approximation of the distribution of the natural logarithm of the complexity. We combined a nonlinear function for the parameter and linear function for and obtained a lower bound for the quantiles of the level 0.95 of the natural logarithm of the complexity. The quality of the estimations was analyzed by the experiment. In our experiment the sample’s quantiles of the level 0.95 differ from the estimation less than 0.3% in the case when the dimension of the problem in range from 45 to 50.