1. SISN
  2. Всі випуски
  3. Випуск 17, 2025
  4. Аналіз швидкодії методу k-means для декомпозиції задачі комівояжера великих розмірностей

Аналіз швидкодії методу k-means для декомпозиції задачі комівояжера великих розмірностей

SISN.
2025;
Випуск 17
: cc. 138 - 145
https://doi.org/10.23939/sisn2025.17.138
Автори:
  1. Роман Кутельмах
1
Національний університет «Львівська політехніка» кафедра програмного забезпечення, Львів, Україна

Декомпозиція задачі базується на кластеризації вхідної множини точок відомим методом k- means та алгоритмі розширення часткового розв’язку у кластерах. Саме k-means застосовано для поділу множини вхідних даних для задачі комівояжера великих розмірностей на менші підзадачі. Обгрунтовано доцільність його використання для зменшення розмірності. На основі проведених експериментів запропоновано застосування ієрархічної версії алгоритму для задач розмірністю більше мільйона точок, проаналізовано доцільність застосування алгоритму k-means для відомих тестових задач комівояжера великих та дуже великих розмірностей. Вхідними даними служать задачі з колекцій TSPLIB та DIMACS TSP Challenge. Проведено експерименти для задач розмірністю від 100 тисяч до 10 мільйонів точок. Згідно з одержаними результатами експериментів (час роботи алгоритму кластеризації задачі на 10 мільйонів точок становить трохи більше 8 хвилин), зроблено висновок про можливість застосування такої кластеризації для декомпозиції задачі.

кластеризація
алгоритм
велика розмірність
k-means
задача комівояжера
підзадача
поділ графу
  1. 1,331,906,450 stars Gaia DR2 (2023). https://www.math.uwaterloo.ca/tsp/star/gaia2.html
  2. Applegate, D., Bixby, R., Chvátal, V., & Cook, W. (2006). The traveling salesman problem: A computational study.Princeton University Press.
  3. Arthur, D., & Vassilvitskii, S. (2007). k-means++: The advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms (pp. 1027–1035). Society for Industrial and Applied Mathematics.
  4. Bentley, J. L. (1990). Experiments on traveling salesman heuristics. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (pp. 91–99).
  5. Bosch R. (2022), Opt Art. From mathematical optimization to visual design. Kharkiv. Fabula.
  6. Darte, A., & Vivien, F. (1995). Revisiting the decomposition of Karp, Miller, and Winograd. Parallel Processing Letters, 5(1), 13–25. https://doi.org/10.1109/ASAP.1995.522901
  7. DIMACS TSP Challenge (2001). http://archive.dimacs.rutgers.edu/Challenges/TSP/
  8. Drori, I., Kates, B. J., Sickinger, W. R., Kharkar, A. G., Dietrich, B., Shporer, A., & Udell, M. (2020). GalaxyTSP: A new billion-node benchmark for TSP. In Proceedings of the 1st Workshop on Learning Meets Combinatorial Algorithms @ NeurIPS 2020 (pp. 1–7). Vancouver, Canada.
  9. Fränti, P., & Virmajoki, O. (2006). Iterative shrinking method for clustering problems. Pattern Recognition, 39(5), 761–775.
  10. Gagolewski, M., Cena, A., Bartoszuk, M., & Brzozowski, L. (2024). Clustering with minimum spanning trees: How good can it be? Journal of Classification, 1–23. https://doi.org/10.1007/s00357-024-09483-1
  11. Guibas, L. J., & Stolfi, J. (1985). Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Transactions on Graphics, 4(2), 75–123.
  12. Jothi, R., Mohanty, S. K., & Ojha, A. (2018). Fast approximate minimum spanning tree based clustering algorithm. Neurocomputing, 272, 542–557. https://doi.org/10.1016/j.neucom.2017.07.038
  13. Kernighan, B. W., & Lin, S. (1970). An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49(2), 291–307. https://doi.org/10.1002/j.1538-7305.1970.tb01770.x
  14. Khamis, A. (2024). Optimization algorithms: AI techniques for design, planning, and control problems. Manning.
  15. KmeansPlusPlus (2017). GitHub. https://github.com/ieyjzhou/KmeansPlusPlus
  16. Kutelmakh, R. K. (2024). Solving NP-Hardness. Efficient Solution to the Traveling Salesman Problem (Prof. Balylevych R. P., Ed.). Lviv. Lviv Polytechnic Publishing House.
  17. Kutelmakh, R., Bazylevych, R., & Prasad, B. (2023). Solving large scale uniform traveling salesman problem by using partial solution expansion method. In 2023 IEEE 18th International Conference on Computer Science and Information Technologies (CSIT) (pp. 1–4). Lviv, Ukraine. https://doi.org/10.1109/CSIT61576.2023.10324172
  18. Mona Lisa TSP Challenge (2008). https://www.math.uwaterloo.ca/tsp/data/ml/monalisa.html
  19. Star Tours (2023). https://www.math.uwaterloo.ca/tsp/star/index.html
  20. Taillard, É., & Helsgaun, K. (2019). Popmusic for the travelling salesman problem.  European Journal of Operational Research, 272(2), 420–429. https://doi.org/10.1016/j.ejor.2018.06.039
  21. TSPLIB (1995). http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/