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 131
- Downloads 0
ARTIFICIAL INTELLIGENT INTRUSION DETECTION SYSTEMS: PERSPECTIVES OF INNOVATIVE TECHNOLOGIES
The most popular development tools of the quantum cryptography technology are compared, the structure and the basic principles of its work is considered. In article the significance in the modern information society of t...
RESOURCE INTENSITY CALCULATION For TEXTS LANGUAGE IDENTIFICATION PROGRAMS
The article deals with the resource intensity calculation of texts language identification programs depending on their identification methods. The most commonly used methods are described, together with an indication of...
EFFECTIVE REALIZATION OF EXACT ALGORITHMS FOR SOLVING DISCRETE OPTIMIZATION PROBLEMS ON GRAPHIC ACCELERATORS
Most of the problems of discrete optimization belong to the class of NP-complete problems. This means that algorithms that can find their exact solution, in general, can work with exponential complexity relative to the l...
EXPERIMENTAL SOFTWARE FOR MODELING AND INTERPRETING EDUCATIONAL DATA ANALYSIS PROCESSES
Problems, tasks and processes of educational data mining are considered in this article. The objective is to create a fundamentally new information system of the University using the results educational data analysis. On...
INTELLECTUAL METHODS OF ANALYSIS OF GEOGRAPHIC INFORMATION INFRASTRUCTURE OF THE REGION
Fuzzy methods of exploration of geo-informational space as a system of systems are considered. The areas of application of digital specialized plan-schemes as fuzzy projections of geo-informational space are discussed. I...