ОПТИМИЗАЦИЯ ПРОГРАММНОГО КОДА НА ПРИМЕРЕ АЛГОРИТМА ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА

EDX: KQAAFR

В статье рассматриваются методы оптимизации программного кода, реализующего алгоритм соединения циклов для решения задачи коммивояжера. Особое внимание уделено параллелизации вычислений с использованием технологий ОрепМР и MPI, а также оптимизации структуры данных и управления памятью для повышения эффективности алгоритма. Применение предложенных методов к задачам большой размерности продемонстрировало значительное сокращение времени выполнения и более эффективное использование вычислительных ресурсов. Предложенные подходы к оптимизации могут быть применены к широкому кругу задач комбинаторной оптимизации, где важны быстродействие и рациональное распределение ресурсов.

Ключевые слова: задача коммивояжера, комбинаторная оптимизация, оптимизация про-граммного кода, оптимизация производительности, параллельные вычисления, инструментирование и профилирование.

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

1.            Jarrah A., Bataineh A. S. A., Almomany A. The optimisation of travelling salesman problem based on parallel ant colony algorithm // International Journal of Computer Applications in Technology. 2022. V. 69. N 4. P. 309-321.

2.            Rhee Y. Gpu-based parallel ant colony system for traveling salesman problem // Journal of The Korea Society of Computer and Information. 2022. V. 27. N 2. P. 1-8.

3.            Wang Z. et al. A fine-grained fast parallel genetic algorithm based on a ternary optical computer for solving traveling salesman problem // The Journal of Supercomputing. 2023. V. 79. N о. P. 4760-4790.

4.            Peng C. Parallel genetic algorithm for travelling salesman problem // In: International conference on automation control, algorithm, and intelligent bionics (ACAIB 2022). 2022. V. 12253, P. 259-267.

5.            Alhenawi E. et al. Solving Traveling Salesman Problem Using Parallel River Formation Dynamics Optimization Algorithm on Multi-core Architecture Using Apache Spark // International Journal of Computational Intelligence Systems. 2024. V. 17. N 1. P. 4.

6.            Qiao Y. et al. A hybridized parallel bats algorithm for combinatorial problem of traveling salesman // Journal of Intelligent & Fuzzy Systems. 2020. T 38. N 5. P. 5811-5820.

7.            Король 3. А. Анкудинов К. А., Королькова Л. H. Исследование методов оптимизации про-граммного кода для повышения производительности // Инновационные направления развития в образовании, экономике, технике и технологиях. 2023. С. 257-260.

8.            Тайк А. М. Лупин С. А., Федяшин Д. А. Использование библиотеки MPI для параллельной реализации алгоритма полного перебора вариантов // Программные продукты и системы. 2023. Т. 36. № 4. С. 607-614.

9.            Panyukov А. V., Leonova Y. F. Algorithm for approximate solution of the travelling salesman problem // Optimization Problems and Their Applications (OPTA-2018). 2018. P. 31. (in Russian).

10.          Leonova Yu. F. Cycles merging algorithm for an approximate solution of the traveling salesman problem // Abstracts of the XIX All-Russian Conference of Young Scientists on Mathematical Modeling and Information Technologies, Novosibirsk: ICT SB RAS. 2018. P. 28.

11.          Panyukov A.V., Leonova Yu. F. Cycle Merging Algorithm for MAX TSP Problems // XVIII International Conference “Mathematical Optimization Theory and Operations Research” (MOTOR 2019), Ekaterinburg, Russia: Publisher “UMC UrFU”. 2019. P. 57.

12.          Panyukov A.V., Leonova Yu.F. Cycle merging algorithm for the maximal metric traveling salesman problem // Bulletin of the South Ural State University, V. 10, N 4: a series of Computational Mathematics and Informatics. Chelyabinsk: Publishing House of SUSU. 2021. P. 26-36. (in Russian) DOI: 10.14529/cmse210402.

13.          Свидетельство о государственной регистрации программы для ЭВМ № 2021669214 Россий¬ская Федерация. Программа для реализации алгоритма соединения циклов для решения задачи коммивояжера : № 2021668239: заявл. 16.11.2021 : опубл. 25.11.2021 / Ю. Ф. Леонова, А. В. Паню- ков ; заявитель Федеральное государственное автономное образовательное учреждение высшего образования «Южно-Уральский государственный университет». EDN RPNSPO.

14.          Гантерот К. Оптимизация программ на C++. Проверенные методы повышения произво-дительности. 1-е изд. М.: Вильямс, 2017. 400 с.

15.          Панюков А. В., Телегин В. А. Техника программной реализации потоковых алгоритмов // Вестник Южно-Уральского государственного университета. Серия: Математическое модели-рование и программирование. 2008. № 27 (127). С. 78-99.

16.          Леонова Ю. Ф. Parallel implementation of the cycle merging algorithm for solving the traveling salesman problem [Электрон, pec.]: https://github.com/YuliyaLeonova/CycleMergingAlgorithm. git, last accessed 2025/05/19.

17.          Intel VTune Profiler. [Электрон, pec.]: https://www.intel.com/content/www/us/en/ developer/tools/oneapi/vtune-profiler.html/gs.hf jczc, last accessed 2024/11/11.

18.          Мейерс С. Эффективный и современный C++. 42 рекомендации по использованию C++11 и С++14. М.: Вильямс, 2018. 304 с.

19.          std::mersenne_twister_engine. [Электрон, pec.]: https: //en. cppref erence . com/w/срр/ numeric/random/mersenne_twister_engine .html, last accessed 2024/11/02.

20.          Best Practices in the Parallel Patterns Library. [Электрон, pec.]: https://learn.microsoft. com/en-us/cpp/parallel/concrt/best-practices-in-the-parallel-patterns-library?view= msvc-170, last accessed 2024/10/15.