Васильчиков Владимир Васильевич, кандидат технических наук, зав. кафедрой вычислительных и программных систем
ул. Советская, 14, г. Ярославль, 150000
Vasilchikov Vladimir Vasilyevich, PhD,
P.G. Demidov Yaroslavl State University, Sovetskaya str., 14, Yaroslavl, 150000
В данной работе рассматриваются способы ускорения решения NP-полной задачи коммивояжера. Классический алгоритм Литтла, относящийся к категории "методов ветвей и границ" , позволяет ее решать как для ориентированных, так и для неориентированных графов. Однако для неориентированных графов его работу можно ускорить за счет исключения рассмотрения фактически ранее рассмотренных вариантов. В работе предлагаются изменения, которые следует внести в ключевые операции алгоритма для ускорения его работы. Приводятся результаты численного эксперимента, показавшего значительное ускорение решения задачи с использованием усовершенствованного алгоритма. Другой ресурс для ускорения – это разработка параллельного алгоритма. Для задач подобного рода весьма сложно сразу разбить вычисления на достаточное количество сравнимых по трудоемкости подзадач. Параллелизм у них выявляется динамически во время вычислений. Для таких задач разумным представляется использование рекурсивно-параллельной организации вычислений. В нашем случае хорошим выбором оказалась разработанная автором библиотека RPM_ParLib, позволяющая создавать эффективные параллельные программы для вычислений на локальной сети в среде .NET Framework на любом поддерживаемом ею языке программирования. Мы при разработке программы использовали язык C#. Были написаны параллельные программы для реализации как исходного, так и модифицированного алгоритмов, проведено их сравнение. Эксперименты проводились для графов с количеством вершин до 45 с количеством компьютеров в сети до 16. Дополнительно исследовалось ускорение, которого можно достичь за счет распараллеливания базового алгоритма Литтла для ориентированных графов. Результаты этих серий экспериментов также приводятся в работе.
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.
The authors declare that there are no conflicts of interest present.