• 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. С. 131-137.
Фомичев М. И., Ульянов М. В., Головешкин В. А., Жукова Г. Н.

It is shown that the logarithm of the complexity (number of nodes in the decision tree of a branch and bound algorithm) of the individual traveling salesman problem is approximately normally distributed. We use a linear regression model (logarithm of the complexity — standard normal distribution) to estimate parameters of normal distribution, which fit the sample. Borders of the interval, which contains 90% of the sample of the logarithm of the complexity, are also given.