• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Student
Title
Supervisor
Faculty
Educational Programme
Final Grade
Year of Graduation
Nataliia Chichileva
Research on Dependencies of Complexity of Symmetric TSP Solving by Vertex-Penalty Minimum Spanning Tree Method Based on Penalty Function Parameter
Software Engineering
(Bachelor’s programme)
2018
The object of investigation is the symmetric traveling salesman problem. The subject of the study is the algorithm for solving the traveling salesman problem by the method of vertex fining. The aim of the study is the complexity of the algorithm for order matrices of symmetric traveling salesman problem.

Research objectives: for different methods of vertex fining, determine the following parameters:

• mathematical expectation and variance of the number of iterations for a given class of equivalent problems;

• mathematical expectation and variance of ECM calculation time;

• mathematical expectation and variance of the number of iterations for problems of a given dimension from different equivalence classes;

• mathematical expectation and variance of computer time.

Methods of research:

• Methods of graph theory;

• Methods of experiment planning;

• Methods of mathematical statistics.

Scientific novelty in front of all traveling salesman tasks on the basis of factorization of classes of symmetric traveling salesman problems.

Results of work for a given class of equivalent traveling salesman tasks and for problems of a given dimension from different classes.

Student Theses at HSE must be completed in accordance with the University Rules and regulations specified by each educational programme.

Summaries of all theses must be published and made freely available on the HSE website.

The full text of a thesis can be published in open access on the HSE website only if the authoring student (copyright holder) agrees, or, if the thesis was written by a team of students, if all the co-authors (copyright holders) agree. After a thesis is published on the HSE website, it obtains the status of an online publication.

Student theses are objects of copyright and their use is subject to limitations in accordance with the Russian Federation’s law on intellectual property.

In the event that a thesis is quoted or otherwise used, reference to the author’s name and the source of quotation is required.

Search all student theses