РОЗПІЗНАВАННЯ ЗВ’ЯЗНИХ НЕОРІЄНТОВАНИХ ГРАФІВ МОБІЛЬНИМ АГЕНТОМ
DOI:
https://doi.org/10.35546/kntu2078-4481.2025.1.2.29Ключові слова:
розпізнавання графа, неорієнтований граф, мобільний агент, складності розпізнавання, обхід графа в глибинуАнотація
Дослідження присвячено проблемі розпізнавання скінчених зв’язних неорієнтованих графів без петель та кратних ребер мобільним агентом. Метою роботи є побудова нового ефективного методу розпізнавання графів та алгоритму, що базується на цьому методі. В роботі запропоновано наступну методологію до досягнення поставленої мети. Використати мобільного агента, який може пересуватися по графу, зчитувати й залишати мітки на елементах графа. Також агент має скінчену на кожному кроці, але необмежено зростаючу внутрішню пам’ять (ємність пам’яті залежить від досліджуваного графа) та для розпізнавання графу використовує фарбу одного кольору. На основі даних, отриманих при переміщенні по графу, мобільний агент в своїй пам’яті поступово вибудовує представлення досліджуваного графа списком ребер і списком вершин. Алгоритм розпізнавання графа базується на методі обходу графа в глибину. У статті детально розглянуто режими роботи мобільного агента із зазначенням пріоритетності активації цих режимів в процесі роботи. Також в роботі проведено аналіз часової й ємнісної складностей побудованого алгоритму та проаналізовано кількість переходів по ребрах, які необхідно виконати мобільному агенту для повного розпізнавання досліджуваного графа. Науковою новизною є отримання нового більш ефективного методу та алгоритму розпізнавання графів, що базується на цьому методі, який дозволяє використовувати для розпізнавання графів лише одну фарбу та дає можливість в подальшому використати даний алгоритм як основу для роботи мультиагентної системи. Алгоритм має квадратичну часову й квадратичну ємнісну складності алгоритму розпізнавання, при цьому верхня оцінка числа переходів по ребрах, що здійснює мобільний агент оцінюється як O(n2).
Посилання
Goth G. Exploring new frontiers. Communications of the ACM. 2009. 52(11). P. 21–23.
Dey, S.; Xu, H. Intelligent Distributed Swarm Control for Large-Scale Multi-UAV Systems: A Hierarchical Learning Approach. Electronics 2023, 12(1):89. https://doi.org/10.3390/electronics12010089
Dongyu Li, Shuzhi Sam Ge, Wei He, Guangfu Ma, Lihua Xie. Multilayer formation control of multi-agent systems. Automatica. V 109. 2019 https://doi.org/10.1016/j.automatica.2019.108558
Zhang T, Ma X, Li H, Wang Z, Xie S, Luo J. Ordered-Bipartite Consensus of Multi-Agent Systems under Finite Time Control. Applied Sciences. 2022; 12(23):12337. https://doi.org/10.3390/app122312337
Стьопкін А. В. Алгоритм розпізнавання простих неорієнтованих графів колективом агентів. Вчені записки таврійського національного університету імені В. І. Вернадського Серія: Технічні науки. Київ, 2024. Т. 35(74) № 5. C. 303–309. https://doi.org/10.32782/2663-5941/2024.5.1/43
Стьопкін А. В. Мультиагентна система розпізнавання неорієнтованих графів. Інформаційні технології та суспільство. Київ, 2024. Вип. 3(14). 38–43 с.
Stopkin A. V. Finite graph exploration by a mobile agent. Mathematical Modeling and Computing. 2025 Vol. 12, No. 1, pp. 75–82.
Shannon C. E. Presentation of a maze-solving machine. Cybernetics Trans, of the 8th Conf. of the JosiahMacy Jr. Found / Editor: H. Foerster. 1951. pp. 173–180.
Dopp K. Automaten in labirinthen. Electronische Informationsverarbeitung und Kybernetik. 1971. V. 7, № 2. pp. 79–94.
Dudek G., Jenkin M., Milios E., Wilkes D. Map validation in a graphlike world. Proceedings of the 13th International Joint Conference on Artifical Intelligence (Chambery, France, August 1993). San Fransisco: Morgan Kaufmann Publishers Inc., 1993. pp. 1648–1653.
Сапунов С. В., Сенченко А. С. Лингвистическое представление графов с помеченными вершинами. Доповіді Національної академії наук України, 2019. № 11. С. 17–24.
Dudek G., Jenkin M., Milios E., Wilkes D. A taxonomy for swarm robots. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Yokohama, Japan, 1993. pp. 441–447.
Dudek G., Jenkin M., Milios E., Wilkes D. Topological exploration with multiple robots. Proc. 7th International Symposium on Robotics with Application (ISORA). Anchorage, Alaska, USA, 1998.
Грунский И. С., Татаринов Е. А. Распознавание конечного графа блуждающим по нему агентом. Вестник ДонНУ, 2009, Вып.1. С. 492–497.
Грунский И. С., Стёпкин А. В. Распознавание конечного графа коллективом агентов. Труды ИПММ НАН Украины, 2009. Т.19. C. 43−52.
Стёпкин А. В. Распознавание конечных графов тремя агентами / А. В. Стёпкин // Искусственный интеллект. 2011. № 2. С. 84–93.
Stepkin A. Using a Collective of Agents for Exploration of Undirected Graphs. Cybernetics and Systems Analysis. 2015. V.51, № 2. pp. 223–233. https://doi.org/10.1007/s10559-015-9715-z
Cormen Т., Leiserson Ch., Rivest R., Stein C. Introduction to Algorithms. Cambridge, 2009. 1292 p.
Aho, A. V., Hopcroft, J. E., Ullman, J. D. (1974). The Design and Analysis of Computer Algorithms. Reading, Mass.: Addison-Wesley.
