Один метод построения циклов в графе
Аннотация
Задачи нахождения циклов в графе – неотъемлемая составная часть геоинформационных, логистических, и навигационных информационных систем. Задачи нахождения гамильтоновых и эйлеровых циклов, задача коммивояжера настолько важны в современных информационных системах, обеспечивающих решение задач в различных предметных областях от традиционных транспортных до научных проблем в химии и биологии, что этому посвящено большое число публикаций. Современная особенность задач нахождения циклов в графе заключается в необходимости обработки больших и сверхбольших данных (Big Data). Методы, которые дают точное решение, сводятся к алгоритмам с экспоненциальной вычислительной сложностью. Для уменьшения сложности предлагаются эвристические методы, например, генетические алгоритмы. Предложен многомерно-матричный подход к обработке больших графов, ориентированный на построение всех возможных циклов независимо от способа вычисления их свойств (например, стоимости, гамильтоновости и прочих). Этот подход обеспечивает эффективное распараллеливание алгоритмов построения всех циклов и использование технологии in database для построения всех циклов, что возможно в силу изоморфизма алгебры многомерных матриц и реляционной алгебры для рассматриваемого класса задач.
Литература
2. Boroznov V.O. Research of the task solution of the traveling salesman. Vestnik of Astrakhan State Technical University. Series: Management, Computer Sciences and Informatics. 2009; (2):147-151. Available at: https://elibrary.ru/item.asp?id=12929954 (accessed 20.08.2021). (In Russ., abstract in Eng.)
3. Ozden S.G., Smith A.E., Gue K.R. Solving large batches of traveling salesman problems with parallel and distributed computing. Computers & Operations Research. 2017; 85:87-96. (In Eng.) doi: https://doi.org/10.1016/j.cor.2017.04.001
4. Ageyev D., Ignatenko A., Wehbe F. Design of Information and Telecommunication Systems with the Usage of the Multi-Layer Graph Model. Proceedings of the XIIth International Conference The Experience of Designing and Application of CAD Systems in Microelectronics (CADSM). Lviv-Polyana, Ukraine; 2013. p. 1-4. (In Eng.) doi: https://doi.org/10.48550/arXiv.1307.1730
5. Margolis B.I., Muzanna M.M. Synthesis gas telemedicine networks. Software & Systems. 2014; (1):162-168. Available at: https://elibrary.ru/item.asp?id=22807997 (accessed 20.08.2021). (In Russ., abstract in Eng.)
6. Spivak S.I., Ismagilova A.S., Khamitova I.A. Graph-theoretical method for determining routes of complex chemical reactions. Doklady Physical Chemistry. 2010; 434:169-171. (In Eng.) doi: https://doi.org/10.1134/S0012501610100040
7. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman's problem. Exact methods. Avtomatika i Telemekhanika = Automation and Remote Control. 1989; (10):3-29. Available at: http://mi.mathnet.ru/at6433 (accessed 20.08.2021). (In Russ., abstract in Eng.)
8. Masum A.K.M., Shahjalal M., Faruque F., Sarker I.H. Solving the Vehicle Routing Problem using Genetic Algorithm. International Journal of Advanced Computer Science and Applications. 2011; 2(7):126-131. (In Eng.) doi: http://dx.doi.org/10.14569/IJACSA.2011.020719
9. Miller J.A., Ramaswamy L., Kochut K.J., Fard A. Research Directions for Big Data Graph Analytics. 2015 IEEE International Congress on Big Data. IEEE Press, New York, NY, USA; 2015. p. 785-794. (In Eng.) doi: https://doi.org/10.1109/BigDataCongress.2015.132
10. Qiu X., Cen W., Qian Z., Peng Y., Zhang Y., Lin X., Zhou J. Real-time constrained cycle detection in large dynamic graphs. Proceedings of the VLDB Endowment. 2018; 11(12):1876-1888. (In Eng.) doi: https://doi.org/10.14778/3229863.3229874
11. Prokopenkov V. Polynomial algorithm for finding a Hamiltonian cycle on a graph. Вісник Національного технічного університету «ХПІ». Серія: Стратегічне управління, управління портфелями, програмами та проектами = Bulletin of the National Technical University "KhPI". Series: Strategic management, portfolio, program and project management. 2021; (1):55-65. (In Russ., abstract in Eng.) doi: https://doi.org/10.20998/2413-3000.2021.3.8
12. Munerman V.I., Samoylova T.A. Algebraic approach to algorithmization of routing problems. Highly available systems. 2018; 14(5):50-56. (In Russ., abstract in Eng.) doi: https://doi.org/10.18127/j20729472-201805-08
13. Grigoryeva G., Khodchenkov V. Implementation of Operations of a Quantum Computer in the Language of the Algebra of Multidimensional Matrices. 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus). IEEE Press, St. Petersburg, Moscow, Russia; 2021. p. 2181-2184. (In Eng.) doi: https://doi.org/10.1109/ElConRus51938.2021.9396119
14. Munerman V.I. Construction of hardware-software complexes architecture to improve massively data processing. Highly available systems. 2015; 11(2):13-18. Available at: https://www.elibrary.ru/item.asp?id=23819273 (accessed 20.08.2021). (In Russ., abstract in Eng.)
15. Munerman V.I., Munerman D.V. About the correspondence of data models and calculation models. Sistemy komp’yuternoj matematiki i ih prilozheniya = Computer Mathematics Systems and Their Applications. 2021; (22):146-152. Available at: https://www.elibrary.ru/item.asp?id=46649891 (accessed 20.08.2021). (In Russ., abstract in Eng.)
16. Emelchenkov E.P., Munerman V.I., Munerman D.V., Samoilova T.A. The object oriented approach to designing data models. Sovremennye informacionnye tehnologii i IT-obrazovanie = Modern Information Technologies and IT-Education. 2020; 16(3):564-574. (In Russ., abstract in Eng.) doi: https://doi.org/10.25559/SITITO.16.202003.564-574
17. Treschev I.A. Construction of multiflow supplements for unparalleling of excess algorithms. Informatika i sistemy upravleniya = Information Science and Control Systems'. 2008; (1):151-159. Available at: https://www.elibrary.ru/item.asp?id=10366217 (accessed 20.08.2021). (In Russ.)
18. Younis A.A., Sunderraman R., Metzler M., Bourgeois A.G. Developing parallel programming and soft skills: A project based learning approach. Journal of Parallel and Distributed Computing. 2021; 158:151-163. (In Eng.) doi: https://doi.org/10.1016/j.jpdc.2021.07.015
19. Zakharov V.N., Munerman V.I. Parallel'nyj algoritm umnozhenija mnogomernyh matric [Parallel algorithm for multiplying multidimensional matrices]. Sovremennye informacionnye tehnologii i IT-obrazovanie = Modern Information Technologies and IT-Education. 2015; 11(2):384-390. Available at: https://www.elibrary.ru/item.asp?id=26167519 (accessed 20.08.2021). (In Russ.)
20. Iljin P.L., Munerman V.I. Recursive computation of the multidimensional matrix determinant. Sistemy komp’yuternoj matematiki i ih prilozheniya = Computer Mathematics Systems and Their Applications. 2019; (20-1):162-167. Available at: https://www.elibrary.ru/item.asp?id=39103176 (accessed 20.08.2021). (In Russ., abstract in Eng.)
21. Munerman V., Munerman D., Samoilova T. The Heuristic Algorithm For Symmetric Horizontal Data Distribution. 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus). IEEE Press, St. Petersburg, Moscow, 2021. p. 2161-2165. (In Eng.) doi: https://doi.org/10.1109/ElConRus51938.2021.9396510
22. Tian T., Gong D., Kuo F.-C., Liu H. Genetic algorithm based test data generation for MPI parallel programs with blocking communication. Journal of Systems and Software. 2019; 155(C):130-144. (In Eng.) doi: https://doi.org/10.1016/j.jss.2019.04.049
23. Ben Y., Sun Y., Li Q., Zang X. A novel cooperative navigation algorithm based on factor graph with cycles for AUVs. Ocean Engineering. 2021; 241:110024. (In Eng.) doi: https://doi.org/10.1016/j.oceaneng.2021.110024
24. Alam K.S., Shishir T.A., Azharul Hasan K.M. Efficient Partitioning Algorithm for Parallel Multidimensional Matrix Operations by Linearization. In: Senjyu T., Mahalle P.N., Perumal T., Joshi A. (eds.) Information and Communication Technology for Intelligent Systems. ICTIS 2020. Smart Innovation, Systems and Technologies. Vol. 195. Springer, Singapore; 2021. p. 141-149. (In Eng.) doi: https://doi.org/10.1007/978-981-15-7078-0_13
25. Sokolov N.P. Functions of multidimensional matrices and their applications for the solutions of linear systems of partial differential equations. Ukrainian Mathematical Journal. 1970; 22(6):657-674. (In Eng.) doi: https://doi.org/10.1007/BF01086271
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
