THE ESTIMATIONS OF THE PARAMETERS OF THE DISTRIBUTION OF THE LOGARITHM OF THE COMPLEXITY OF TSP
Journal Title: Современные информационные технологии и ИТ-образование - Year 2017, Vol 13, Issue 1
Abstract
The complexity of the individual traveling salesman problem was analyzed by means of mathematical statistics. The complexity is defined as a number of nodes of the decision tree created by the branch and bound algorithm. We obtained approximate representations for parameters of probability distribution of the natural logarithm of the complexity. These representations are functions of the dimension of the problem. The linear function is used to construct the upper estimation for the quantiles of the natural logarithm of the complexity, in cases when the level of the quantile is more than 0.5. We also applied this formula for the lower bound of the quantiles of levels less than 0.5. Then we used the normal distribution with the parameters and as an approximation of the distribution of the natural logarithm of the complexity. We combined a nonlinear function for the parameter and linear function for and obtained a lower bound for the quantiles of the level 0.95 of the natural logarithm of the complexity. The quality of the estimations was analyzed by the experiment. In our experiment the sample’s quantiles of the level 0.95 differ from the estimation less than 0.3% in the case when the dimension of the problem in range from 45 to 50.
Authors and Affiliations
Vasily Goloveshkin, Galina Zhukova, Mikhail Ulyanov
Keywords
Related Articles
- EP ID EP320796
- DOI 10.25559/SITITO.2017.1.405
- Views 123
- Downloads 0
GENERIC COORDINATE SYSTEMS IN THE COMPUTER GEOMETRY COURSE
The article presents an approach to describe generic coordinate systems as a part of the course “Computer Geometry and Geometric Modeling”, which is taught to third-year students majoring in mathematics at the Lobachevsk...
DESIGN-THINKING: PRACTICE OF CUSTOMER EXPERIENCE RESEARCH
The purpose of our research is to find new tools for analysing hidden client needs (pains), regulating the sequence of reasoning when making decisions during the creation of innovative projects. We propose an approach of...
MODELING OF THE PROCESS OF PREPARING FUTURE TEACHERS OF INFORMATICS TO RESOURCE-SAVING ACTIVITIES BASED ON EUROPEAN EXPERIENCE
The article describes the model for the preparation of future teachers of informatics for resource-saving activities, the stages of modeling are considered. The developed model, which is a structural interconnection of t...
RISK ESTIMATION FOR VK.COM ACCOUNTS EXPOSED TO SUICIDE-THEMED QUESTS
The former report regards the problem of internet terrorism prevention. The main focus is given to suicide-themed quest «Blue Whale» (also known as «Siniy Kit») in vk.com social network and method for exposed accounts lo...
MOTIVATION OF STUDENT IN IT-DISCIPLINES
Method of systematic literature analysis for 2012-2017 about motivation of the learners in IT disciplines was applied. The growth trend in the number of publications about the motivation of students and the learners of I...