Параллельная реализация алгоритма построения всех маршрутов в графе средствами реляционной алгебры
Аннотация
В статье описывается способ оптимизации алгоритма построения всех маршрутов в графе средствами реляционной алгебры. Задача, решаемая предлагаемым методом, относится к классу NP-полных. Данный факт свидетельствует о необходимости поиска эффективного решения для снижения вычислительной сложности данной задачи. Последовательная реализация алгоритма основана на методе построения маршрутов с применением операции (1, 0)-свернутого произведения многомерных матриц и формализована в понятиях реляционной алгебры. Описываемый алгоритм, реализованный с применением технологии in memory, позволяет выполнять операции непосредственно по ключам исходных данных без предварительного приведения их к матричной форме. В следствии гомоморфизма реляционной алгебры и алгебры многомерных матриц, которая обладает естественным параллелизмом, имеется возможность увеличить эффективность алгоритма распределением данных по нескольким процессорам. В статье приводится доказательство изоморфизма обеих алгебр в рамках поставленной задачи. Подход, предложенный в статье, позволяет выполнять параллельные вычисления как на локальной машине (выделение отдельных потоков для фрагментов исходных данных), так и на масштабировать их на ПК, объединенные в локальную сеть. В качестве показателя эффективности, предлагаемого алгоритма, выбрано время, требующееся на построение всех возможных маршрутов в графе. Приведен сравнительный анализ последовательной и параллельной реализаций методов, выполняющихся на одной ЭВМ, средствами реляционной базы данных Microsoft SQL Server.
Литература
2. Beliacov S.L., Kolomiytsev Y.A., Rozenberg I.N., Savelyeva M.N. Model' reshenija zadachi marshrutizacii v intellektual'noj geoinformacionnoj sisteme [Model for solving routing problem in the intellectual geoinformation system]. Izvestiya SFedU. Engineering Sciences. 2011;(5):113-119. (In Russ., abstract in Eng.) EDN: NTZLVP
3. Ageyev D., Ignatenko A., Wehbe F. Design of Information and Telecommunication Systems with the Usage of the Multi-Layer Graph Model. In: 2013 12th International Conference on the Experience of Designing and Application of CAD Systems in Microelectronics (CADSM). Lviv, Ukraine: IEEE Press; 2013. p. 1-4. Available at: https://ieeexplore.ieee.org/document/6543168 (accessed 16.07.2023).
4. Margolis B.I., Muzanna M.M. Sintez magistral'nyh telekommunikacionnyh setej [Synthesis gas telemedicine networks]. Software & Systems. 2014;(1):162-168. (In Russ., abstract in Eng.) EDN: TFCUKN
5. Miller J.A., Ramaswamy L., Kochut K.J., Fard A. Research Directions for Big Data Graph Analytics. In: 2015 IEEE International Congress on Big Data. New York, NY, USA: IEEE Press; 2015. P. 785-794. https://doi.org/10.1109/BigDataCongress.2015.132
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. https://doi.org/10.1134/S0012501610100040
7. Kozlov S.V. Interpretation of invariants of the theory of counts in the context of use of compliance of Galois at creation and support of information systems. International Journal of Open Information Technologies. 2016;4(7);38-44. (In Russ., abstract in Eng.) EDN: WCMIYL
8. Kozlov S.V. Intellektual'naja sistema podderzhki prinjatija reshenij "Advanced Tester" [Intelligent Decision Support System "Advanced Tester"]. In: Komp'juternaja integracija proizvodstva i IPI-tehnologii = International Conference on Computer Integration of Manufacturing and CALS Technologies. Orenburg: OSU; 2021. p. 127-131. (In Russ., abstract in Eng.) EDN: CWGXOC
9. Masum K., Faruque F, Shahjalal M., Sarker H. Solving the Vehicle Routing Problem using Genetic Algorithm. International Journal of Advanced Computer Science and Applications. 2011;2(7):126-131. https://doi.org/10.14569/IJACSA.2011.020719
10. Semenov Yu.N., Semenova O.S. The use of clustering methods in the organization long-distance transport of goods. Bulletin of the Kuzbass State Technical University. 2016;(6):201-206. (In Russ., abstract in Eng.) EDN: XVKNBV
11. Munerman V.I., Samoylova T.A. Algebraic approach to algorithmization of routing problems. Sistemy vysokoy dostupnosti = Systems Highly Available. 2018;14(5):50-56. (In Russ., abstract in Eng.) EDN: YUVFSX
12. Munerman V.I., Munerman D.V., Sinitsyn I.N. Arhitektura vychislitel'nyh kompleksov dlya realizacii zaprosov v sistemah massovoj obrabotki dannyh [Architecture of Computing Systems for Processing Queries in Large‑Scale Data Processing Systems]. Sistemy komp’yuternoj matematiki i ih prilozheniya = Computer Mathematics Systems and Their Applications. 2015;(16):85-87. (In Russ., abstract in Eng.) EDN: UBGCOL
13. Munerman V.I. Construction of Hardware-Software Complexes Architecture to Improve Massively Data Processing. Sistemy vysokoy dostupnosti = Systems Highly Available. 2014;10(4):3-16. (In Russ., abstract in Eng.) EDN: TFQJWX
14. Munerman V., Munerman D. An Axiomatic Approach to the Data Models Formalization for Mass Data Processing. In: 2020 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus). St. Petersburg and Moscow, Russia: IEEE Press; 2020. p. 1996-2000. https://doi.org/10.1109/EIConRus49466.2020.9039205
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. (In Russ., abstract in Eng.) EDN: PVXDHB
16. Munerman V.I., Munerman D.V. The Proof of the Data Models Correspondence Example. Sistemy komp’yuternoj matematiki i ih prilozheniya = Computer Mathematics Systems and Their Applications. 2023;(24):166-171. (In Russ., abstract in Eng.) EDN: KGMBPQ
17. Morozov S.A., Munerman V.I., Simakov V.A. Experimental analysis of multidimensional matrix approach to constructing routings in a graph. Proc. Univ. Electronics. 2022;275676-686. (In Russ., abstract in Eng.) https://doi.org/10.24151/1561-5405-2022-27-5-676-686
18. Makarov D.I., Munerman V.I., Munerman D.V. Arhitektura programmno-apparatnogo kompleksa dlya raspredelennoj obrabotki dannyh na baze kontejnernoj tekhnologii [Architecture of a Hardware‑Software Complex for Distributed Data Processing Based on Container Technology]. Sistemy komp’yuternoj matematiki i ih prilozheniya = Computer Mathematics Systems and Their Applications. 2018;(19):187-193. (In Russ., abstract in Eng.) EDN: XRVLGX
19. Munerman V.I., Munerman D.V. Parallel Implementation of Symmetric Horizontal Distribution of Data on the Network Technologies Basis. Modern Information Technologies and IT-Education. 2017;13(3):38-43. (In Russ., abstract in Eng.) https://doi.org/10.25559/SITITO.2017.3.521
20. Martello S., Toth P. Knapsack problems: algorithms and computer implementations. New York, NY, USA: John Wiley & Sons, Inc.; 1990. 296 p.
21. Emelchenkov E.P., Emelchenkov V.E. Binarnye otnoshenija. Otnoshenie jekvivalentnosti [Binary Relations. Equivalence Relation]. Matematicheskaja morfologija: jelektronnyj matematicheskij i mediko-biologicheskij zhurnal. 1997;2(2):3-19. (In Russ., abstract in Eng.) EDN: ADBXSJ
22. Kline K., Gould L., Zanevsky A. Transact-SQL Programming: Covers Microsoft SQL Server 6.5/7.0 and Sybase Adaptive Server 11.5. O'Reilly Media, Inc.; 1999. p. 612-619.
23. Henderson K. The guru's guide to Transact-SQL. Addison-Wesley Professional; 2000. p. 90-91.
24. Henderson K. The Guru's Guide to SQL Server Stored Procedures, XML, and HTML. Addison-Wesley Professional; 2002. p. 32-34.
25. Corlăţan C.G., et al. Query Optimization Techniques in Microsoft SQL Server. Database Systems Journal. 2014;5(2):33-48. Available at: https://dbjournal.ro/archive/16/16_4.pdf (accessed 16.07.2023).
Это произведение доступно по лицензии 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.
