Об оптимизации и распараллеливании алгоритма Литтла для решения задачи коммивояжера

В данной работе рассматриваются способы ускорения решения NP-полной задачи коммивояжера. Классический алгоритм Литтла, относящийся к категории "методов ветвей и границ" , позволяет ее решать как для ориентированных, так и для неориентированных графов. Однако для неориентированных графов его работу можно ускорить за счет исключения рассмотрения фактически ранее рассмотренных вариантов. В работе предлагаются изменения, которые следует внести в ключевые операции алгоритма для ускорения его работы. Приводятся результаты численного эксперимента, показавшего значительное ускорение решения задачи с использованием усовершенствованного алгоритма. Другой ресурс для ускорения – это разработка параллельного алгоритма. Для задач подобного рода весьма сложно сразу разбить вычисления на достаточное количество сравнимых по трудоемкости подзадач. Параллелизм у них выявляется динамически во время вычислений. Для таких задач разумным представляется использование рекурсивно-параллельной организации вычислений. В нашем случае хорошим выбором оказалась разработанная автором библиотека RPM_ParLib, позволяющая создавать эффективные параллельные программы для вычислений на локальной сети в среде .NET Framework на любом поддерживаемом ею языке программирования. Мы при разработке программы использовали язык C#. Были написаны параллельные программы для реализации как исходного, так и модифицированного алгоритмов, проведено их сравнение. Эксперименты проводились для графов с количеством вершин до 45 с количеством компьютеров в сети до 16. Дополнительно исследовалось ускорение, которого можно достичь за счет распараллеливания базового алгоритма Литтла для ориентированных графов. Результаты этих серий экспериментов также приводятся в работе. 

1. Гэри М. Джонсон Д., Вычислительные машины и труднорешаемые задачи, Мир, Москва, 1982.

2. Land A. H. Doig A. G., “An Autmatic Method of Solving Discrete Programming Problems”, Econometrica, 28 (1960), 497–520. DOI: 10.2307/1910129.

3. John D. C. Little, Katta G. Murty, Dura W. Sweeney, Caroline Karel, “An Algorithm for the Traveling Salesman Problem”, Operations Research, 11:6 (1963), 972–989. DOI: 10.1287/opre.11.6.972.

4. Кофман А., Введение в прикладную комбинаторику, Наука, Москва, 1975.

5. Рейнгольд Э. Нивергельт Ю. Део Н., Комбинаторные алгоритмы. Теория и практика, Мир, Москва, 1980.

6. Кормен Т. Лейзерсон Ч. Ривест Р. Штайн К., Алгоритмы: построение и анализ, Вильямс, Москва, 2006.

7. Петрунин С. В., “Использование метода последовательной сепарации для решения задачи коммивояжёра”, Научный вестник МТГУ ГА, 2009, № 146, 105–108.

8. Костюк Ю. Л., “Эффективная реализация алгоритма решения задачи коммивояжёра методом ветвей и границ”, Прикладная дискретная математика, 2013, № 2, 78–90.

9. Сигал И. Х., Бабинская Я. Л., Посыпкин М. А., “Параллельная реализация метода ветвей и границ в задаче коммивояжера на базе библиотеки BNB-Solver”, Труды ИСА РАН, 25 (2006), 26–36.

10. Васильчиков В. В., Средства параллельного программирования для вычислительных систем с динамической балансировкой загрузки, ЯрГУ, Ярославль, 2001.

11. Васильчиков В. В., Коммуникационный модуль для организации полносвязного соединения компьютеров в локальной сети с использованием .NET Framework, Свидетельство о государственной регистрации программы для ЭВМ № 2013619925, 2013.

12. Васильчиков В. В., Библиотека поддержки рекурсивно-параллельного программирования для .NET Framework, Свидетельство о государственной регистрации программы для ЭВМ № 2013619926, 2013.

13. Васильчиков В. В., “О поддержке рекурсивно-параллельного программирования в .NET Framework”, Модел. и анализ информ. систем, 21:2 (2014), 15–25.