Статья

Название статьи ПОЛИНОМИАЛЬНАЯ СЛОЖНОСТЬ ПАРАЛЛЕЛЬНОЙ ФОРМЫ МЕТОДА ВЕТВЕЙ И ГРАНИЦ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА
Автор Я.Е. Ромм, Е.Г. Назарьянц
Рубрика РАЗДЕЛ I. МОДЕЛИРОВАНИЕ И ПРОЕКТИРОВАНИЕ
Месяц, год 04, 2015
Индекс УДК 681.3.06: 681.323(519.6)
DOI
Аннотация Работа содержит параллельное преобразование алгоритма Дж. Литтла реализации метода ветвей и границ для решения задачи коммивояжера на основе идентификации экстремумов при помощи максимально параллельной сортировки подсчетом по матрицам сравнений. Приводится описание и программа сортировки с оценкой временной сложности. Описан метод и реализующие его программные операторы идентификации локальных экстремумов. Предложенный параллельный алгоритм цикличен, даны две оценки его временной сложности T(n4/6-n3/4)=O(nlog2n) и T(n4/6-n3/4)=O(n5log2n) для случаев без возвратов к оборванным ветвям и с возвратом к одной из них (без учета вложений). При одновременной обработке всех обрываемых ветвей без учета вложений временная сложность по сравнению с обработкой одной оборванной ветви не увеличивается за счет роста числа процессоров, и имеет место оценка T(n6/6)=O(n5log2n). Оценки с учетом числа процессоров используют абстрактную модель неветвящихся параллельных программ, при этом не учитывается архитектура параллельной вычислительной системы и время обмена. Выполнено численное моделирование предложенного параллельного алгоритма с помощью его последовательной реализации на персональном компьютере. Представлены результаты численного эксперимента, которые подтверждают правильность работы предложенной параллельной модификации алгоритма Дж. Литтла. Дано сравнение полученных результатов с известными результатами применения различных алгоритмов и программ параллельной реализации метода ветвей и границ для решения задачи коммивояжёра. Существенным отличием предложенного способа решения задачи коммивояжера от известных является объединение параллельной сортировки и собственно метода ветвей и границ, позволяющее получить полиномиальные оценки временной сложности алгоритма.

Скачать в PDF

Ключевые слова Задача коммивояжера; параллельная форма метода ветвей и границ; полиномиальная оценка временной сложности; параллельная сортировка подсчетом.
Библиографический список 1. Сергиенко И.В., Емец О.А., Емец А.О. Задачи оптимизации с интервальной неопределенностью: метод ветвей и границ // Кибернетика и системный анализ. – 2013. – № 5. – С. 38-51.
2. Овезгельдыев А.О., Морозов А.В. Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута // Кибернетика и системный анализ. – 2013. – № 5. – С. 112-124.
3. Gaurav Bhardwaj, Manish Pandey. Parallel Implementation of the Max_Min Ant System for the Travelling Salesman Problem on GPU // International Journal of Computer Applications. – August 2014. –Vol. 99, No. 16. – P. 9-13.
4. Gaurav Bhardwaj, Manish Pandey. Parallel Implementation of Travelling Salesman Problem using Ant Colony Optimization // International Journal of Computer Applications Technology and Research. – 2014. – Vol. 3, Issue 6. – P. 385-389.
5. Little J., Murty K., Sweeney D., Karel C. An algorithm for the travelling salesman problem // Operations research. – 1963. – Vol. 11. – P. 972-989.
6. Wirth N. Algorithms and Data Structures. – August 2004. – P. 183.
7. Ромм Я.Е., Назарьянц Е.Г. Преобразование метода ветвей и границ для решения задачи коммивояжера на основе максимально параллельной сортировки. – Таганрог: ТГПИ., 2013. – 25 с. Деп. в ВИНИТИ 30.09.2013, № 279-В2013.
8. Солодовников В.И. Верхние оценки сложности решения систем линейных уравнений // В кн.: Теория сложности вычислений. I: Записки научных семинаров ЛОМИ АН СССР. – Л., 1982. – Т. 118. – С. 159-187.
9. Гаврилкевич М.В., Солодовников В.И. Эффективные алгоритмы решения задач линейной алгебры над полем из двух элементов // Обозрение прикладной и промышленной математики. – 1995. – Т. 2, № 3. – С. 399-439.
10. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. I // Кибернетика и системный анализ. – 1994. – № 5. – С. 3-23.
11. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. II // Кибернетика и системный анализ. – 1995. – № 4. – С. 13-37.
12. Ромм Я.Е., Заика И.В. Численная оптимизация на основе алгоритмов сортировки с приложением к дифференциальным и нелинейным уравнениям общего вида // Кибернетика и системный анализ. – 2011. – № 2. – С. 165-180.
13. Ромм Я.Е., Дзюба А.С., Назарьянц Е.Г. Преобразование и численное моделирование метода ветвей и границ для решения задачи коммивояжера на основе максимально параллельной сортировки. – Таганрог: ТГПИ, 2014. – 49 с. Деп. в ВИНИТИ 30.09.2014, № 279-В2013.
14. Колпаков Р.М., Посыпкин М.А., Сигал И.Х. О нижней оценке вычислительной сложности одной параллельной реализации метода ветвей и границ // Автоматика и телемеханика. – 2010. – № 10. – С. 156-166.
15. Richard Wiener. Branch and Bound Implementations for the Traveling Salesperson Problem // Journal of Object Technology. – March-April 2003. – Part. 1, № 2. – P. 65-86.
16. Leo Liberti. Branch-and-Bound for the Travelling Salesman Problem // LIX, Ecole Polytechnique, F-91128 Palaiseau. – March 15, 2011. – P. 1-8.
17. Посыпкин М.А, Сигал И.Х. Верхняя оценка для ускорения в одной параллельной реализации метода ветвей и границ решения задач дискретной оптимизации // Труды третьей международной конференции «параллельные вычисления и задачи управления», Москва 2-4 октября 2006. РАСО’2006. – С. 897-908.
18. Сигал И.Х., Бабинская Я.Л., Посыпкин М.А. Параллельная реализация метода ветвей и границ в задаче коммивояжера на базе библиотеки BNB-Solver // Труды ИСА РАН. – 2006. – Т. 25. – С. 26-36.
19. Посыпкин М.А, Сигал И.Х. Применение параллельных эвристических алгоритмов для ускорения параллельного метода ветвей и границ // Журнал вычислительной математики и математической физики. – 2007. – Т. 47, № 9. – С. 1524-1537.
20. Bazylevych R., Kuz B., Kutelmakh R. Parallel Approaches for Solving Large-scale Travelling Salesman Problem // Second International Conference "Cluster Computing" CC. – June 3-5, 2013. – P. 30-34.
21. Dimitrijevic V., Milosavljevic M., Markoviс M. Branch and bound algorithm for solving a generalized traveling salesman problem // Univ. Beograd. Publ. Elektrotehn. Fak. Ser. – Mat. 7 (1996). – P. 31-35.

Comments are closed.