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 128
- Downloads 0
PLAYING WITH A CHAIN OR PHYSICAL AND MATHEMATICAL INFORMATICS
The article describes an educational laboratory work within the framework of interdisciplinary connections at the intersection of informatics, mathematics and physics: the study of the sagging of a closed chain with diff...
ALGORITHMS FOR THE ROBUST PROPERTIES ANALYSIS OF A MULTI-PURPOSE CONTROL LAWS OF MOVING OBJECTS
The problems of analyzing robust properties for control systems of moving objects are of significant importance in modern control theory. This is because the mathematical models used in the synthesis of control laws are...
ARCHITECTURE AND RELIABILITY OF OPERATING SYSTEMS
Progress in the production technology of microprocessors significantly increased reliability and performance of the computer systems hardware. It cannot be told about the corresponding characteristics of the software and...
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...
DIGITAL ECONOMY TECHNOLOGIES IN SMART CITY PROJECTS: PARTICIPANTS AND PROSPECTS
Nowadays the smart city concepts focus on the quality improvement of a citizen’s life by using the ICT. Meanwhile, the consideration of possible participants of smart city projects and the assessment of their potential r...