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 130
- Downloads 0
CORPUS OF SIGNS IN WRITING AS A TOOL TO INVESTIGATE THE PECULIARITIES OF HOW SIGNS FORM UP (ON THE EXAMPLE OF THE RUSSIAN SIGN LANGUAGE)
We investigate the peculiarities of how gestures are formed in Sign Languages; deaf people use these gestures to communicate with each other. These peculiarities make it problematic to describe the Sign Languages linguis...
SYNTHESIS OF FAULT ESTIMATION OBSERVER, BASED ON SPECTRAL MIMO H2 OPTIMIZATION
This paper is devoted to slowly varying additive fault detection with implementation of the observer-filter to be designed. Sensitivity of the observer to the external disturbance is to be minimized by the choice of its...
SOLUTION OF THE PROBLEM OF HIGH-PRECISION POSITIONING OF AUTOMOBILE TRANSPORT ON THE BASIS OF THE USE OF ELECTRONIC MAPS
The solution of the problem of positioning of moving objects is now increasingly carried out using electronic maps, allowing approximating with high accuracy the trajectory of the object by a set of orthodromic trajector...
COMPARISON OF METHODS OF CONSTRUCTION OF APPROXIMATE ANALYTICAL SOLUTIONS OF DIFFERENTIAL EQUATIONS CONSIDERING ON THE EXAMPLE OF ELEMENTARY FUNCTIONS
Compares methods of constructing multilayer approximate solutions of differential equations based on classical approximate methods on the example of the exponent and cosine. In contrast to classical numerical methods, th...
ANALYTICAL MODELING AND SIMULATION OF RELIABILITY OF A CLOSED HOMOGENEOUS SYSTEM WITH AN ARBITRARY NUMBER OF DATA SOURCES AND LIMITED RESOURCES FOR THEIR PROCESSING
Continuous development of computer networks and data transmission systems underlines the growing need for adequate mathematical models and methods for analyzing the performance and reliability metrics of these systems, t...