РАСПРЕДЕЛЕНИЕ ЛОГАРИФМА СЛОЖНОСТИ ИНДИВИДУАЛЬНЫХ ЗАДАЧ КОММИВОЯЖЕРА ПРИ ФИКСИРОВАННОЙ ДЛИНЕ ВХОДА

Василий Адамович Головешкин; Галина Николаевна Жукова; Михаил Васильевич Ульянов; Михаил Игоревич Фомичев

Василий Адамович Головешкин Moscow Technological University MIREA
Галина Николаевна Жукова Moscow Polytechnic University
Михаил Васильевич Ульянов Institute of Control Sciences V. A. Trapeznikov Academy of Sciences
Михаил Игоревич Фомичев Higher School of Economics National Research University

Abstract

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.

Author Biographies

Василий Адамович Головешкин, Moscow Technological University MIREA

доктор технических наук, профессор

Галина Николаевна Жукова, Moscow Polytechnic University

кандидат физико-математических наук, доцент

Михаил Васильевич Ульянов, Institute of Control Sciences V. A. Trapeznikov Academy of Sciences

доктор технических наук, профессор, ведущий научный сотрудник

Михаил Игоревич Фомичев, Higher School of Economics National Research University

студент магистратуры факультета компьютерных наук

References

1. Dantzig G. B., Fulkerson R., Johnson S. Solution of a large scale traveling salesman problem. Technical Report P-510. RAND Corporation, Santa Monica, California, USA. – 1954.
2. Dantzig, G. B., Fulkerson D. R., Johnson S. M. «On a linearprogramming, combinatorial approach to the traveling-salesman problem» // Operations Research 1959. №7, pp. 58–66.
3. Eastman, W. L. Linear Programming with Pattern Constraints. Ph.D. Thesis. Department of Economics, Harvard University, Cambridge, Massachusetts, USA. – 1958.
4. Jonhnson N.L., Kotz S., and Balakrishnan N. Continuous Univariate Distributions. Vol. 2, Wiley, 1995.
5. Knuth, D. E. «Estimating the efficiency of backtracking programs» // Mathematics of Computing, 1975. Vol. 29, pp. 121–136.
6. Land, A. H., Doig A. G. «An automatic method of solving discrete programming problems» // Econometrica 1960. №28, pp. 497–520.
7. Little, J. D. C., Murty K. G., Sweeney D.W., Karel C. «An algorithm for the traveling salesman problem» // Operations Research, 1963. №11, pp. 972–989.
8. Moors J. J. A. A quantile alternative for kurtosis// The Statistician, 1988. Vol. 37, pp. 25–32.
9. Moors J. J. A., Coenen V. M. J., Heuts R. M. J. «Limiting distributions of moment- and quantile-based measures for skewness and kurtosis». School of Economics and Management, Tilburg University, Res. Mem. FEW 620, 1993.
10. Moors J. J. A., Wagemakers R. Th. A., Coenen V. M. J., Heuts R. M. J., Janssens M. J. B. T. «Characterizing systems of distributions by quantile measures» // Statistica Neerlandica, 1996. Vol. 50, № 3, pp. 417–430.
11. Pearson, K. «Contributions to the Mathematical Theory of Evolution. III. Regression, Heredity and Panmixia» // Philosophical Transactions of the Royal Society of London, 1896. 187, pp. 253–318.
12. Головешкин В.А., Жукова Г.Н., Ульянов М.В., Фомичев М.И. «Сравнение ресурсных характеристик традиционного и модифицированного метода ветвей и границ для TSP» // Современные информационные технологии и ИТ-образование, 2015. Т. 2, № 11. С. 151-159.
13. Крамер Г. Математические методы статистики. — М.: Мир, 1975. — 648 с.
14. Ульянов М.В., Фомичев М.И. «Ресурсные характеристики способов организации дерева решений в методе ветвей и границ для задачи коммивояжера» // Бизнес – информатика, 2015. № 4 (34). С. 38–46.
15. Ульянов М.В. Ресурсно-эффективные компьютерные алгоритмы. Разработка и анализ. — М.: ФИЗМАТЛИТ, 2008. —304 с.