Использование коллектива агентов для распознавания неориентированных графов
Рассматривается задача распознавания конечных неориентированных графов коллективом агентов. Два агента-исследователя одновременно передвигаются по графу, считывают и изменяют метки элементов графа, передают необходимую информацию агенту-экспериментатору, который строит представление исследуемого гра...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2015 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/124778 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Использование коллектива агентов для распознавания неориентированных графов / А.В. Стёпкин // Кибернетика и системный анализ. — 2015. — Т. 51, № 2. — С. 75-88. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862595427783671808 |
|---|---|
| author | Стёпкин, А.В. |
| author_facet | Стёпкин, А.В. |
| citation_txt | Использование коллектива агентов для распознавания неориентированных графов / А.В. Стёпкин // Кибернетика и системный анализ. — 2015. — Т. 51, № 2. — С. 75-88. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Рассматривается задача распознавания конечных неориентированных графов коллективом агентов. Два агента-исследователя одновременно передвигаются по графу, считывают и изменяют метки элементов графа, передают необходимую информацию агенту-экспериментатору, который строит представление исследуемого графа. Построен алгоритм распознавания линейной (от числа вершин графа) временной сложности и квадратической емкостной сложности. Разработана процедура оптимизации разбиения графа на части, распознаваемые различными агентами. Алгоритм основан на методе обхода графа в глубину.
Розглянуто задачу розпізнавання скінченних неорієнтованих графів колективом агентів. Два агента-дослідника одночасно рухаються графом, зчитують та змінюють помітки елементів графа, передають необхідну інформацію агенту-експериментатору, який будує уявлення про досліджуваний граф. Запропоновано алгоритм розпізнавання лінійної (від числа вершин графа) часової та квадратичної ємнісної складностей. Розроблено процедуру оптимізації розбиття графа на частини для розпізнавання різними агентами. Для розпізнавання два агенти, що рухаються графом, використовують по дві різні фарби (усього три фарби). Алгоритм базується на методі обходу графа в глибину.
The paper considers the problem of exploration of finite undirected graphs by a collective of agents. Two agents-researchers simultaneously move on the graph, read and change marks of graph elements, transfer necessary information to the agent-experimenter (it constructs the representation of the explored graph). An algorithm is proposed for a linear (with respect to the number of nodes) time complexity and quadratic space complexity. An optimization procedure is developed for graph partition for exploring by different agents. Two agents (that move on the graph) need two different colors (three colors in total) for graph exploration. The algorithm is based on depth-first traversal method
|
| first_indexed | 2025-11-27T12:53:35Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-124778 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-27T12:53:35Z |
| publishDate | 2015 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Стёпкин, А.В. 2017-10-05T06:25:17Z 2017-10-05T06:25:17Z 2015 Использование коллектива агентов для распознавания неориентированных графов / А.В. Стёпкин // Кибернетика и системный анализ. — 2015. — Т. 51, № 2. — С. 75-88. — Бібліогр.: 8 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/124778 519.17 Рассматривается задача распознавания конечных неориентированных графов коллективом агентов. Два агента-исследователя одновременно передвигаются по графу, считывают и изменяют метки элементов графа, передают необходимую информацию агенту-экспериментатору, который строит представление исследуемого графа. Построен алгоритм распознавания линейной (от числа вершин графа) временной сложности и квадратической емкостной сложности. Разработана процедура оптимизации разбиения графа на части, распознаваемые различными агентами. Алгоритм основан на методе обхода графа в глубину. Розглянуто задачу розпізнавання скінченних неорієнтованих графів колективом агентів. Два агента-дослідника одночасно рухаються графом, зчитують та змінюють помітки елементів графа, передають необхідну інформацію агенту-експериментатору, який будує уявлення про досліджуваний граф. Запропоновано алгоритм розпізнавання лінійної (від числа вершин графа) часової та квадратичної ємнісної складностей. Розроблено процедуру оптимізації розбиття графа на частини для розпізнавання різними агентами. Для розпізнавання два агенти, що рухаються графом, використовують по дві різні фарби (усього три фарби). Алгоритм базується на методі обходу графа в глибину. The paper considers the problem of exploration of finite undirected graphs by a collective of agents. Two agents-researchers simultaneously move on the graph, read and change marks of graph elements, transfer necessary information to the agent-experimenter (it constructs the representation of the explored graph). An algorithm is proposed for a linear (with respect to the number of nodes) time complexity and quadratic space complexity. An optimization procedure is developed for graph partition for exploring by different agents. Two agents (that move on the graph) need two different colors (three colors in total) for graph exploration. The algorithm is based on depth-first traversal method ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Использование коллектива агентов для распознавания неориентированных графов Використання колективу агентів для розпізнавання неорієнтованих графів Using a collective of agents for exploration of undirected graphs Article published earlier |
| spellingShingle | Использование коллектива агентов для распознавания неориентированных графов Стёпкин, А.В. Кибернетика |
| title | Использование коллектива агентов для распознавания неориентированных графов |
| title_alt | Використання колективу агентів для розпізнавання неорієнтованих графів Using a collective of agents for exploration of undirected graphs |
| title_full | Использование коллектива агентов для распознавания неориентированных графов |
| title_fullStr | Использование коллектива агентов для распознавания неориентированных графов |
| title_full_unstemmed | Использование коллектива агентов для распознавания неориентированных графов |
| title_short | Использование коллектива агентов для распознавания неориентированных графов |
| title_sort | использование коллектива агентов для распознавания неориентированных графов |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/124778 |
| work_keys_str_mv | AT stepkinav ispolʹzovaniekollektivaagentovdlâraspoznavaniâneorientirovannyhgrafov AT stepkinav vikoristannâkolektivuagentívdlârozpíznavannâneoríêntovanihgrafív AT stepkinav usingacollectiveofagentsforexplorationofundirectedgraphs |