ВИКОРИСТАННЯ КОЛЕКТИВУ МОБІЛЬНИХ АГЕНТІВ ДЛЯ РОЗПІЗНАВАННЯ НЕОРІЄНТОВАНИХ ГРАФІВ

Анотація

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