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

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

Аннотация

Проведен статистический анализ сложности индивидуальных задач коммивояжера, определяемой как число вершин дерева решений, порожденного алгоритмом ветвей и границ. Получены приближенные представления зависимости параметров вероятностного распределения натурального логарифма сложности от размерности задачи. Линейная зависимость используется для построения оценки сверху квантилей натурального логарифма сложности уровня больше 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>. Дата доступа: 25 apr. 2024 doi: https://doi.org/10.25559/SITITO.2017.1.405.
Форматы библиографических ссылок
Выпуск
Том 13 № 1 (2017): Современные информационные технологии и ИТ-образование
Раздел
Теоретические вопросы информатики, прикладной математики, компьютерных наук
Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.

Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.

Наиболее читаемые статьи этого автора (авторов)