RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Model. Anal. Inform. Sist.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Model. Anal. Inform. Sist., 2016, Volume 23, Number 4, Pages 401–411 (Mi mais511)  

This article is cited in 1 scientific paper (total in 1 paper)

On the optimization and parallelizing Little algorithm for solving the Traveling Salesman Problem

V. V. Vasilchikov

P.G. Demidov Yaroslavl State University, Sovetskaya str., 14, Yaroslavl, 150000, Russia

Abstract: The paper describes some ways to accelerate solving the NP-complete Traveling Salesman Problem. The classic Little algorithm belonging to the category of “branch and bound methods” can solve it both for directed and undirected graphs. However, for undirected graphs its operation can be accelerated by eliminating the consideration of branches examined earlier. The paper proposes changes to be made in the key operations of the algorithm to speed up its execution. It also describes the results of an experiment that demonstrated a significant acceleration of solving the problem by using an advanced algorithm. Another way to speed up the work is to parallelize the algorithm. For problems of this kind it is difficult to break the task into a sufficient number of subtasks having comparable complexity. Their parallelism arises dynamically during the execution. For such problems, it seems reasonable to use parallel-recursive algorithms. In our case the use of the library RPM_ParLib developed by the author was a good choice. It allows us to develop effective applications for parallel computing on a local network using any .NET-compatible programming language. We used C# to develop the programs. Parallel applications were developed as for basic and modified algorithms, the comparing of their speed was made. Experiments were performed for the graphs with the number of vertexes up to 45 and with the number of network computers up to 16. We also investigated the acceleration that can be achieved by parallelizing the basic Little algorithm for directed graphs. The results of these experiments are also presented in the paper.

Keywords: Traveling Salesman Problem, Little algorithm, parallel algorithm, recursion, .NET.

Funding Agency Grant Number
Ministry of Education and Science of the Russian Federation АААА-А16-116070610022-6
This work was supported by initiative program VIP-004 (state registration number АААА-А16-116070610022-6).


DOI: https://doi.org/10.18255/1818-1015-2016-4-401-411

Full text: PDF file (1074 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.688: 519.85
Received: 31.05.2016

Citation: V. V. Vasilchikov, “On the optimization and parallelizing Little algorithm for solving the Traveling Salesman Problem”, Model. Anal. Inform. Sist., 23:4 (2016), 401–411

Citation in format AMSBIB
\Bibitem{Vas16}
\by V.~V.~Vasilchikov
\paper On the optimization and parallelizing Little algorithm for solving the Traveling Salesman Problem
\jour Model. Anal. Inform. Sist.
\yr 2016
\vol 23
\issue 4
\pages 401--411
\mathnet{http://mi.mathnet.ru/mais511}
\crossref{https://doi.org/10.18255/1818-1015-2016-4-401-411}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3549343}
\elib{http://elibrary.ru/item.asp?id=26561560}


Linking options:
  • http://mi.mathnet.ru/eng/mais511
  • http://mi.mathnet.ru/eng/mais/v23/i4/p401

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. V. V. Vasilchikov, “O rekursivno-parallelnom algoritme resheniya zadachi o ryukzake”, Model. i analiz inform. sistem, 25:2 (2018), 155–164  mathnet  crossref  elib
  • Моделирование и анализ информационных систем
    Number of views:
    This page:154
    Full text:54
    References:12

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020