Использование коллектива агентов для распознавания неориентированных графов
Рассматривается задача распознавания конечных неориентированных графов коллективом агентов. Два агента-исследователя одновременно передвигаются по графу, считывают и изменяют метки элементов графа, передают необходимую информацию агенту-экспериментатору, который строит представление исследуемого гра...
Збережено в:
| Дата: | 2015 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/124778 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Использование коллектива агентов для распознавания неориентированных графов / А.В. Стёпкин // Кибернетика и системный анализ. — 2015. — Т. 51, № 2. — С. 75-88. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-124778 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1247782017-10-06T03:02:49Z Использование коллектива агентов для распознавания неориентированных графов Стёпкин, А.В. Кибернетика Рассматривается задача распознавания конечных неориентированных графов коллективом агентов. Два агента-исследователя одновременно передвигаются по графу, считывают и изменяют метки элементов графа, передают необходимую информацию агенту-экспериментатору, который строит представление исследуемого графа. Построен алгоритм распознавания линейной (от числа вершин графа) временной сложности и квадратической емкостной сложности. Разработана процедура оптимизации разбиения графа на части, распознаваемые различными агентами. Алгоритм основан на методе обхода графа в глубину. Розглянуто задачу розпізнавання скінченних неорієнтованих графів колективом агентів. Два агента-дослідника одночасно рухаються графом, зчитують та змінюють помітки елементів графа, передають необхідну інформацію агенту-експериментатору, який будує уявлення про досліджуваний граф. Запропоновано алгоритм розпізнавання лінійної (від числа вершин графа) часової та квадратичної ємнісної складностей. Розроблено процедуру оптимізації розбиття графа на частини для розпізнавання різними агентами. Для розпізнавання два агенти, що рухаються графом, використовують по дві різні фарби (усього три фарби). Алгоритм базується на методі обходу графа в глибину. 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 2015 Article Использование коллектива агентов для распознавания неориентированных графов / А.В. Стёпкин // Кибернетика и системный анализ. — 2015. — Т. 51, № 2. — С. 75-88. — Бібліогр.: 8 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/124778 519.17 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Стёпкин, А.В. Использование коллектива агентов для распознавания неориентированных графов Кибернетика и системный анализ |
| description |
Рассматривается задача распознавания конечных неориентированных графов коллективом агентов. Два агента-исследователя одновременно передвигаются по графу, считывают и изменяют метки элементов графа, передают необходимую информацию агенту-экспериментатору, который строит представление исследуемого графа. Построен алгоритм распознавания линейной (от числа вершин графа) временной сложности и квадратической емкостной сложности. Разработана процедура оптимизации разбиения графа на части, распознаваемые различными агентами. Алгоритм основан на методе обхода графа в глубину. |
| format |
Article |
| author |
Стёпкин, А.В. |
| author_facet |
Стёпкин, А.В. |
| author_sort |
Стёпкин, А.В. |
| title |
Использование коллектива агентов для распознавания неориентированных графов |
| title_short |
Использование коллектива агентов для распознавания неориентированных графов |
| title_full |
Использование коллектива агентов для распознавания неориентированных графов |
| title_fullStr |
Использование коллектива агентов для распознавания неориентированных графов |
| title_full_unstemmed |
Использование коллектива агентов для распознавания неориентированных графов |
| title_sort |
использование коллектива агентов для распознавания неориентированных графов |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2015 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/124778 |
| citation_txt |
Использование коллектива агентов для распознавания неориентированных графов / А.В. Стёпкин // Кибернетика и системный анализ. — 2015. — Т. 51, № 2. — С. 75-88. — Бібліогр.: 8 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT stëpkinav ispolʹzovaniekollektivaagentovdlâraspoznavaniâneorientirovannyhgrafov |
| first_indexed |
2023-10-18T20:47:11Z |
| last_indexed |
2023-10-18T20:47:11Z |
| _version_ |
1796151104495419392 |