РАСПРЕДЕЛЕНИЕ ЛОГАРИФМА СЛОЖНОСТИ ИНДИВИДУАЛЬНЫХ ЗАДАЧ КОММИВОЯЖЕРА ПРИ ФИКСИРОВАННОЙ ДЛИНЕ ВХОДА
Аннотация
На основе статистического анализа сложности индивидуальной задачи коммивояжера, решаемой методом ветвей и границ, показано, что распределение логарифма сложности удовлетворительно аппроксимируется нормальным распределением. Коэффициенты линейной регрессии выборки логарифма сложности на стандартное нормальное распределение использовались для оценки значений параметров аппроксимирующего нормального распределения. Даны оценки границ 90% интервала сложности.
Литература
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 с.
Это произведение доступно по лицензии 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.
