АЛГОРИТМ РОЗПІЗНАВАННЯ ГРАФІВ КОЛЕКТИВОМ АГЕНТІВ

Анотація

Робота присвячена проблемі розпізнавання скінчених зв’язних неорієнтованих графів без петель та кратних ребер колективом агентів. Метою роботи є розробка нового методу розпізнавання неорієнтованих графів колективом агентів та побудова алгоритму, що базується на цьому методі. В роботі запропоновано наступну методологію до досягнення поставленої мети. Для розпізнавання використовується два агенти: нерухомий агент – агент-експериментатор, що знаходиться поза межами графа та виконує побудову мапи досліджуваного графа у вигляді списків ребер та вершин. Обчислення виконуються на базі повідомлень, які він отримує від іншого агента. Агент-експериментатор має скінчену на кожному кроці, але необмежено зростаючу внутрішню пам’ять. Другий агент – агент-дослідник, що представлений у вигляді мобільного агента, який може рухатися досліджуваним графом, зчитувати та змінювати відмітки на елементах графа, а також відправляти повідомлення агенту-експериментатору. Під час роботи агент-дослідник фарбуватиме необхідні елементи графа в чорний колір і наприкінці роботи всі елементи графа будуть пофарбовані. Агент-дослідник має скінчену пам’ять, яка не залежить від розмірності досліджуваного графа та використовує одну чорну фарбу. Функціонування колективу агентів забезпечується взаємодією двох принципово різних алгоритмів: алгоритму обходу графа агентом-дослідником та алгоритму побудови мапи графа агентом-експериментатором. Науковою новизною є отримання нового методу та алгоритму розпізнавання графів колективом агентів, який дозволяє використовувати для розпізнавання графів лише одну фарбу та дає можливість в подальшому використати даний алгоритм як основу для використання більшої кількості агентів-дослідників. Алгоритм має кубічну часову, квадратичну ємнісну та кубічну комунікаційну складності алгоритму розпізнавання, при цьому верхня оцінка числа переходів по ребрах, що здійснює агент-дослідник оцінюється як O(n3).