Алгоритм розпізнавання простих графів колективом агентів
Тип публікації :
Стаття
Дата випуску :
23 грудня 2025 р.
Автор(и) :
Стьопкін, Андрій
Турка, Тетяна
Мова основного тексту :
Англійська
eKNUTSHIR URL :
Том :
81
Випуск :
2
ISSN :
1812-5409
Початкова сторінка :
211
Кінцева сторінка :
216
Цитування :
[APA 7] Стьопкін, А., & Турка, Т. (2025). Algorithm for recognizing simple graphs by a collective of agents. Bulletin of Taras Shevchenko National University of Kyiv. Physics and Mathematics, 81(2), 211–216. https://doi.org/10.17721/1812-5409.2025/2.33
[ДСТУ] Стьопкін А., Турка Т. Algorithm for recognizing simple graphs by a collective of agents. Bulletin of Taras Shevchenko National University of Kyiv. Physics and Mathematics. 2025. Vol. 81, no. 2. P. 211—216. DOI: 10.17721/1812-5409.2025/2.33 (date of access: 25.07.2026).
Нині досить динамічно розвиваються напрямки автоматизації та роботизації різних процесів. Звісно, це стосується і дослідження різноманітних середовищ, де організація роботи людини є складнішою або навіть небезпечнішою, ніж організація роботи в тих самих умовах спеціальних роботизованих систем. Це робить актуальними дослідження, спрямовані на розпізнавання (побудову мапи) невідомих графів мобільними агентами. У представленій роботі запропоновано новий алгоритм розпізнавання скінчених, неорієнтованих графів без петель і кратних ребер за допомогою двох агентів різного типу. Один з агентів – агент-дослідник, що пересувається по графу, зчитує та змінює мітки елементів графа і передає інформацію про свої дії іншому агенту – агенту-експериментатору. Робота агента-дослідника базується на методі обходу графа у глибину. Агент-дослідник має скінчену пам'ять, що не залежить від розмірності графа. Другий агент – це агент-експериментатор, що перебуває поза межами досліджуваного графа. Головним завданням цього агента є побудова представлення досліджуваного графа (у вигляді переліку ребер і вершин) у своїй пам'яті на основі інформації, яку він отримує від агента-дослідника. Агент-експериментатор має скінчену внутрішню пам'ять, що необмежено зростає, розмірність якої залежить від кількості вершин графа над розпізнаванням якого працюють агенти.
Також детально розглянуто режими роботи агента-дослідника із зазначенням пріоритетності їхньої активації залежно від навколишніх умов і перелік повідомлень, якими обмінюються агенти у процесі роботи алгоритму. Наведено повний алгоритм роботи агента-експериментатора з обробки отриманих повідомлень, на основі яких і відбувається розпізнавання графа. Виконано аналіз часової, ємнісної, комунікаційної складності побудованого алгоритму та проаналізовано кількість переходів по ребрах, які виконує агент-дослідник під час обходу графа. З'ясовано, що запропонований алгоритм має квадратичні (від кількості вершин досліджуваного графа) часову, ємнісну та комунікаційну складності. Верхню оцінку кількості переходів по ребрах, які здійснює агент-дослідник, оцінено як O(n^2), де n – кількість вершин у графі. Для роботи запропонованого алгоритму розпізнавання графа агенту-досліднику необхідно дві фарби різного кольору й один камінь.
Також детально розглянуто режими роботи агента-дослідника із зазначенням пріоритетності їхньої активації залежно від навколишніх умов і перелік повідомлень, якими обмінюються агенти у процесі роботи алгоритму. Наведено повний алгоритм роботи агента-експериментатора з обробки отриманих повідомлень, на основі яких і відбувається розпізнавання графа. Виконано аналіз часової, ємнісної, комунікаційної складності побудованого алгоритму та проаналізовано кількість переходів по ребрах, які виконує агент-дослідник під час обходу графа. З'ясовано, що запропонований алгоритм має квадратичні (від кількості вершин досліджуваного графа) часову, ємнісну та комунікаційну складності. Верхню оцінку кількості переходів по ребрах, які здійснює агент-дослідник, оцінено як O(n^2), де n – кількість вершин у графі. Для роботи запропонованого алгоритму розпізнавання графа агенту-досліднику необхідно дві фарби різного кольору й один камінь.
Файл(и) :![Ескіз]()
Вантажиться...
Формат :
Adobe PDF
Розмір :
532 KB
Контрольна сума :
(MD5):68b655d1cde7ae6b8a3dcccab228c8d0
Якщо не вказано інше, ця робота розповсюджується на умовах ліцензії Creative Commons Attribution 4.0 International