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

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

Аннотация

На основе статистического анализа сложности индивидуальной задачи коммивояжера, решаемой методом ветвей и границ, показано, что распределение логарифма сложности удовлетворительно аппроксимируется нормальным распределением. Коэффициенты линейной регрессии выборки логарифма сложности на стандартное нормальное распределение использовались для оценки значений параметров аппроксимирующего нормального распределения. Даны оценки границ 90% интервала сложности.

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

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

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

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

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

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

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

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

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

Литература

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 с.
Опубликована
2016-11-26
Как цитировать
ГОЛОВЕШКИН, Василий Адамович et al. РАСПРЕДЕЛЕНИЕ ЛОГАРИФМА СЛОЖНОСТИ ИНДИВИДУАЛЬНЫХ ЗАДАЧ КОММИВОЯЖЕРА ПРИ ФИКСИРОВАННОЙ ДЛИНЕ ВХОДА. Международный научный журнал «Современные информационные технологии и ИТ-образование», [S.l.], v. 12, n. 3-2, p. 131-137, nov. 2016. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/135>. Дата доступа: 26 oct. 2021
Раздел
Исследования и разработки в области новых ИТ и их приложений