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


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

Полный текст:


Аннотация

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


Об авторе

В. В. Васильчиков
Ярославский государственный университет им. П.Г. Демидова, Ярославль
Россия

Васильчиков Владимир Васильевич,  кандидат технических наук, зав. кафедрой вычислительных и программных систем

ул. Советская, 14, г. Ярославль, 150000



Список литературы

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.


Дополнительные файлы

Для цитирования: Васильчиков В.В. Об оптимизации и распараллеливании алгоритма Литтла для решения задачи коммивояжера. Моделирование и анализ информационных систем. 2016;23(4):401-411. https://doi.org/10.18255/1818-1015-2016-4-401-411

For citation: Vasilchikov V.V. On the Optimization and Parallelizing Little Algorithm for Solving the Traveling Salesman Problem. Modeling and Analysis of Information Systems. 2016;23(4):401-411. (In Russ.) https://doi.org/10.18255/1818-1015-2016-4-401-411

Просмотров: 444

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)