|
Vestnik of Astrakhan State Technical University. Series: Management, Computer Sciences and Informatics, 2009, Number 2, Pages 147–151
(Mi vagtu262)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
COMPUTER SOFTWARE AND COMPUTING EQUIPMENT
Research of the task solution of the traveling salesman
V. O. Boroznov Astrakhan State Technical University
Abstract:
The review of the most widespread algorithms used for the task solution of the traveling salesman such as: exact (exhaustive algorithm, method of paths and limits), heuristic (method of distant inclusion, BV-method) and search (Genetic algorithms, Ant Colony System — ACS-Q) is given. The comparative analysis of the algorithms, concerning the quality of the received solutions and their “speed” has shown: heuristic algorithms are undeniable “leaders” in speed with good ratio quality/time; the exact methods are poorly suitable for the solution of tasks of the large dimensions (are not capable to solve a task for reasonable time); the algorithms of search are the compromise between heuristics and exact methods, but they require selection of parameters. The temporary estimations given to algorithms, allow to estimate time of the task solution and to choose the most suitable method, when the speed is a critical parameter.
Keywords:
traveling salesman’s task, exact algorithms, heuristic algorithms, search algorithms, assessment of time complexity, the speed of combinatorial algorithms.
Received: 07.10.2009
Citation:
V. O. Boroznov, “Research of the task solution of the traveling salesman”, Vestn. Astrakhan State Technical Univ. Ser. Management, Computer Sciences and Informatics, 2009, no. 2, 147–151
Linking options:
https://www.mathnet.ru/eng/vagtu262 https://www.mathnet.ru/eng/vagtu/y2009/i2/p147
|
Statistics & downloads: |
Abstract page: | 1185 | Full-text PDF : | 414 | References: | 56 | First page: | 1 |
|