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

  • Василий Адамович Головешкин Московский технологический университет МИРЭА
  • Галина Николаевна Жукова Московский политехнический университет
  • Михаил Васильевич Ульянов Институт проблем управления им. В.А. Трапезникова РАН
  • Михаил Игоревич Фомичев Национальный исследовательский университет "Высшая школа экономики"

Аннотация

Проведен статистический анализ сложности индивидуальных задач коммивояжера, определяемой как число вершин дерева решений, порожденного алгоритмом ветвей и границ. Получены приближенные представления зависимости параметров вероятностного распределения натурального логарифма сложности от размерности задачи. Линейная зависимость используется для построения оценки сверху квантилей натурального логарифма сложности уровня больше 0.5 и снизу для квантилей уровня меньше 0.5. Нелинейная зависимость параметра масштаба  нормального распределения, аппроксимирующего распределение натурального логарифма сложности, и линейная зависимость параметра сдвига позволяют получить оценку снизу для квантилей натурального логарифма сложности уровня 0.95. Проведен экспериментальный анализ качества полученных оценок, показано, что относительное отклонение предполагаемых значений квантилей натурального логарифма сложности уровня 0.95 от выборочных не превышает 0.3%  в случае размерности задачи от 45 до 50.

Сведения об авторах

Василий Адамович Головешкин, Московский технологический университет МИРЭА

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

Галина Николаевна Жукова, Московский политехнический университет

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

Михаил Васильевич Ульянов, Институт проблем управления им. В.А. Трапезникова РАН

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

Михаил Игоревич Фомичев, Национальный исследовательский университет "Высшая школа экономики"

магистрант

Литература

1. Knuth, D. E. «Estimating the efficiency of backtracking programs» // Mathematics of Computing, 1975. Vol. 29, pp. 121–136.
2. 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.
3. 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.
4. Eastman, W. L. Linear Programming with Pattern Constraints. Ph.D. Thesis. Department of Economics, Harvard University, Cambridge, Massachusetts, USA. – 1958.
5. Land, A. H., Doig A. G. «An automatic method of solving discrete programming problems» // Econometrica 1960. №28, pp. 497–520.
6. 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.
7. Ul'janov M.V. Resursno-jeffektivnye komp'juternye algoritmy. Razrabotka i analiz. — M.: FIZMATLIT, 2008. — 304 s.
8. Ul'janov M.V., Fomichev M.I. «Resursnye harakteristiki sposobov organizacii dereva reshenij v metode vetvej i granic dlja zadachi kommivojazhera» // Biznes – informatika, 2015. № 4 (34). S. 38–46.
9. Moors J. J. A. A quantile alternative for kurtosis// The Statistician, 1988. Vol. 37, pp. 25–32.
10. 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.
11. 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.
12. Jonhnson N.L., Kotz S., and Balakrishnan N. Continuous Univariate Distributions. Vol. 2, Wiley, 1995.
13. Goloveshkin V.A., Zhukova G.N., Ul'janov M.V., Fomichjov M.I. Ispol'zovanie kvantil'nyh kojefficientov asimmetrii i jekscessa dlja ocenki slozhnosti reshenija zadachi kommivojazhera. International Journal of Open Information Technologies. 2016. T. 4. № 12. S. 7-12.
14. Kramer G. Matematicheskie metody statistiki. — M.: Mir, 1975. — 648 s.
15. 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.
16. Goloveshkin V.A., Zhukova G.N., Ul'janov M.V., Fomichev M.I. «Sravnenie resursnyh harakteristik tradicionnogo i modificirovannogo metoda vetvej i granic dlja TSP» // Sovremennye informacionnye tehnologii i IT-obrazovanie, 2015. T. 2, № 11. S. 151-159.
17. Goloveshkin V.A., Zhukova G.N., Ul'janov M.V., Fomichjov M.I. Ob odnom obobshhjonnom predstavlenii klassov individual'nyh zadach kommivojazhjora// Avtomatizacija. Sovremennye tehnologii. 2016. № 10. S. 22-29.
Опубликована
2017-05-30
Как цитировать
ГОЛОВЕШКИН, Василий Адамович et al. ОЦЕНКА ПАРАМЕТРОВ РАСПРЕДЕЛЕНИЯ ЛОГАРИФМА СЛОЖНОСТИ ЗАДАЧИ КОММИВОЯЖЕРА. Международный научный журнал «Современные информационные технологии и ИТ-образование», [S.l.], v. 13, n. 1, p. 19-24, may 2017. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/193>. Дата доступа: 24 july 2017
Раздел
Теоретические вопросы информатики, прикладной математики, компьютерных наук