• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
  • HSE University
  • Publications of HSE
  • Articles
  • Использование квантильных коэффициентов асимметрии и эксцесса для оценки сложности решения задачи коммивояжера

Article

Использование квантильных коэффициентов асимметрии и эксцесса для оценки сложности решения задачи коммивояжера

International Journal of Open Information Technologies. 2016. Т. 4. № 12. С. 7-12.

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.