Cybernetics And Systems Analysis logo
Інформація редакції Аннотації статей Автори Зміст
Кібернетика і Системний Аналіз
Міжнародний Науково-Теоретичний Журнал
УДК 519.17
А.В. Стьопкін

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

Анотація. Розглянуто задачу розпізнавання скінченних неорієнтованих графів колективом агентів. Два агента-дослідника одночасно рухаються графом, зчитують та змінюють помітки елементів графа, передають необхідну інформацію агенту-експериментатору, який будує уявлення про досліджуваний граф. Запропоновано алгоритм розпізнавання лінійної (від числа вершин графа) часової та квадратичної ємнісної складностей. Розроблено процедуру оптимізації розбиття графа на частини для розпізнавання різними агентами. Для розпізнавання два агенти, що рухаються графом, використовують по дві різні фарби (усього три фарби). Алгоритм базується на методі обходу графа в глибину.

Ключові слова: розпізнавання графа, колектив агентів, обхід графа.



ПОВНИЙ ТЕКСТ

Стёпкин Андрей Викторович,
ассистент кафедры Донбасского государственного педагогического университета, Славянск, Украина,
e-mail: stepkin.andrey@rambler.ru.

© 2015 Kibernetika.org. All rights reserved.