Определение максимального множества независимых простых путей между вершинами графа
Аннотация
В настоящей статье излагается алгоритм определения максимального количества независимых простых путей, а также самих путей, между заданными вершинами графа. Данная задача крайне важна в теории связи, решение ее необходимо для обеспечения устойчивости сети связи. В то же время эта задача не рассматривается отдельной задачей в теории графов. Актуальность решения ее обусловлена, во-первых, как уже отмечалось, необходимостью повышения устойчивости сети связи, и, во-вторых, тем фактом, что для реальных сильно разветвленных сетей связи использование традиционных алгоритмов для поиска независимых маршрутов, основанных на поиске кратчайших путей, становится неэффективным. Неэффективность объясняется тем, что при наличии, например, двух независимых маршрутов в крупномасштабных сетях связи традиционные алгоритмы поиска кратчайших путей могут обнаружить только один из-за того, что между имеющимися независимыми простыми путями существуют пути, через которые пройдет найденный стандартным алгоритмом (нахождения кратчайшего пути) путь, захватив при этом части двух имеющихся независимых маршрутов. Аналогичный эффект может быть и при наличии более двух независимых простых путей, когда стандартные алгоритмы поиска кратчайшего пути могут «потерять» все простые пути сверх одного. Предмет настоящей статьи посвящен устранению данной проблемы.
Литература
2. Berge C. Theorie des Graphes. 2nd Ed. Dunod; 1958. (In French)
3. Harary F. Graph Theory. CRC Press; 1994. 288 p. (In Eng.)
4. Diestel R. Graph Theory. Graduate Texts in Mathematics, vol. 173. 5th Ed. Springer, Berlin, Heidelberg; 2017. 428 p. (In Eng.) DOI: https://doi.org/10.1007/978-3-662-53622-3
5. Belov V.V., Vorobyov E.M., Shatalov V.E. Teoriya grafov [Graph Theory]. Higher School, Moscow; 1976. 392 p. (In Russ.)
6. Emelichev V.A., Melnikov O.I., Sarvanov V.I., Tyshkevich R.I. Lekcii po teorii grafov [Lectures on Graph Theory]. URSS, Moscow; 2009. 392 p.
7. Smagin A.A., Terentyeva Yu.Yu. A mathematical model of a counter built on the basis of the Lynch-Davison code. Journal of Instrument Engineering. 2000; 43(3):28-32. Available at: https://www.elibrary.ru/item.asp?id=24234126 (accessed 15.02.2021). (In Russ., abstract in Eng.)
8. Krichevsky R.E. Szhatie i poisk informacii [Compression and search for information]. Radio and Communications, Moscow; 1989. 168 p. (In Russ.)
9. Wentzel E.S. Teoriya veroyatnostej [Probability Theory]. Nauka, Moscow; 1969. 576 p. (In Russ.)
10. Ajemov A.S., Sannikov V.G. Obshchaya teoriya svyazi [General Theory of Communication]. Telecom, Moscow; 2020. 624 p. (In Russ.)
11. Dutta B., Jackson M. The stability and efficiency of directed communication networks. Review of Economic Design. 2000; 5(3):251-272. (In Eng.) DOI: https://doi.org/10.1007/PL00013688
12. Melnikov B.F., Meshchanin V.Y., Terentyeva Y.Y. Implementation of optimality criteria in the design of communication networks. Journal of Physics: Conference Series. Engineering and Innovative Technologies. 2020; 1515:042093. (In Eng.) DOI: https://doi.org/10.1088/1742-6596/1515/4/042093
13. Bulynin A.G., Melnikov B.F., Meshchanin, V.Y., Terentyeva. Y.Y. Optimization problem, arising in the development of high-dimensional communication networks, and some heuristic methods for solving them. Informatization and Communication. 2020; (1):34-40. (In Russ., abstract in Eng.) DOI: https://doi.org/10.34219/2078-8320-2020-11-1-34-40
14. Bulynin A.G., Melnikov B.F., Meshchanin, V.Y. and Terentyeva. Y.Y. Algorithms for designing communication networks using greedy heuristics of different types. Proceedings of the International Conference on Information Technology and Nanotechnology (ITNT-2020). Samara University, Samara; 2020. p. 856-860. Available at: https://www.elibrary.ru/item.asp?id=43576630 (accessed 15.02.2021). (In Russ., abstract in Eng.)
15. Melnikov B.F., Terentyeva. Y.Y. Building communication networks: on the application of the Kruskal’s algorithm in the problems of large dimensions. International Journal of Open Information Technologies. 2021; 9(1):13-21. Available at: https://www.elibrary.ru/item.asp?id=44584129 (accessed 15.02.2021). (In Russ., abstract in Eng.)
16. Colorni A., Dorigo M., Maniezzo V. Distributed Optimization by Ant Colonies. In: F. Varela, P. Bourgine (Eds.) Proceedings of the European Conference on Artificial Life (ECAL’91). Paris, France, Elsevier Publishing; 1991. p. 134-142. (In Eng.)
17. Dorigo M., Maniezzo V., Colorni A. Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). 1996; 26(1):29-41. (In Eng.) DOI: https://doi.org/10.1109/3477.484436
18. Gambardella L.M., Dorigo M. Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem. Machine Learning Proceedings. Morgan Kaufmann; 1995. p. 252-260. (In Eng.) DOI: https://doi.org/10.1016/B978-1-55860-377-6.50039-6
19. Dorigo M., Gambardella L.M. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation. 1997; 1(1):53-66. (In Eng.) DOI: https://doi.org/10.1109/4235.585892
20. Stützle T., Hoos H. MAX-MIN Ant System and local search for the traveling salesman problem. Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC '97). Indianapolis, IN, USA; 1997. p. 309-314. (In Eng.) DOI: https://doi.org/10.1109/ICEC.1997.592327
21. Coltorti D., Rizzoli A.E. Ant Colony Optimization for Real-World Vehicle Routing Problems. SIGEVOlution. 2007; 2(2):2-9. (In Eng.) DOI: https://doi.org/10.1145/1329465.1329466
22. Stützle T., et al. Parameter Adaptation in Ant Colony Optimization. In: Y. Hamadi, E. Monfroy, F. Saubion (Eds.) Autonomous Search. Springer, Berlin, Heidelberg; 2011. p. 191-215. (In Eng.) DOI: https://doi.org/10.1007/978-3-642-21434-9_8
23. Li Y., Li W. Adaptive Ant Colony Optimization Algorithm Based on Information Entropy: Foundation and Application. Fundamenta Informaticae. 2007; 77(3):229-242. Available at: https://content.iospress.com/articles/fundamenta-informaticae/fi77-3-03 (accessed 15.02.2021). (In Eng.)
24. Merkle D., Middendorf M., Schmeck H. Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation. 2002; 6(4):333-346. (In Eng.) DOI: https://doi.org/10.1109/TEVC.2002.802450
25. Tavares Neto R.F., Godinho Filho M. Literature review regarding Ant Colony Optimization applied to scheduling problems: Guidelines for implementation and directions for future research. Engineering Applications of Artificial Intelligence. 2013; 26(1):150-161. (In Eng.) DOI: http://dx.doi.org/10.1016/j.engappai.2012.03.011
Это произведение доступно по лицензии 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.
