Исследование структуры графа при помощи двух агентов
В работе рассматривается решение задачи распознавания конечных неориентированных графов двумя агентами. Один агент-исследователь передвигается по графу, считывает и изменяет метки элементов графа и передает информацию о своих действиях агенту-экспериментатору, который строит представление исследуемо...
Збережено в:
| Дата: | 2016 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2016
|
| Назва видання: | Труды Института прикладной математики и механики |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/140863 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Исследование структуры графа при помощи двух агентов / А.В. Стёпкин // Труды Института прикладной математики и механики НАН Украины. — Слов’янськ: ІПММ НАН України, 2016. — Т. 30. — С. 111-121. — Бібліогр.: 12 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-140863 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1408632018-07-18T01:23:24Z Исследование структуры графа при помощи двух агентов Стёпкин, А.В. В работе рассматривается решение задачи распознавания конечных неориентированных графов двумя агентами. Один агент-исследователь передвигается по графу, считывает и изменяет метки элементов графа и передает информацию о своих действиях агенту-экспериментатору, который строит представление исследуемого графа. Предложен алгоритм квадратической (от числа вершин графа) временной, емкостной и коммуникационной сложностей, который распознает любой конечный неориентированный граф. Для распознавания графа требуется 2 различные краски. Метод основан на методе обхода графа в глубину. В роботі розглядається розв’язок задачі розпізнавання скінчених неорієнтованих графів двома агентами. Один агент-дослідник рухається графом, зчитує та змінює помітки на елементах графу та передає інформацію про свої дії агенту-експериментатору, який будує уявлення про досліджуваний граф. Пропонується алгоритм квадратичної (від кількості вершин графу) часової, ємнісної та комунікаційної складностей, який розпізнає довільний скінчений неорієнтований граф. Для розпізнавання графу необхідно дві різні фарби. Метод базується на методі обходу графа в глибину. This paper considers the problem of exploration of finite undirected graphs by two agents. One agentresearcher traverse a graph, read and change labels of graph elements, and send necessary information to the agent-experimenter constructing a representation of the graph being explored. An exploration algorithm is proposed with a quadratic (with respect to the number of nodes) time complexity, space complexity and communication complexity. An algorithm is proposed explored any finite undirected graph. Graph’s exploring needs two different colors. The algorithm is based on the depth-first traversal method. 2016 Article Исследование структуры графа при помощи двух агентов / А.В. Стёпкин // Труды Института прикладной математики и механики НАН Украины. — Слов’янськ: ІПММ НАН України, 2016. — Т. 30. — С. 111-121. — Бібліогр.: 12 назв. — рос. 1683-4720 http://dspace.nbuv.gov.ua/handle/123456789/140863 519.7 ru Труды Института прикладной математики и механики Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
В работе рассматривается решение задачи распознавания конечных неориентированных графов двумя агентами. Один агент-исследователь передвигается по графу, считывает и изменяет метки элементов графа и передает информацию о своих действиях агенту-экспериментатору, который строит представление исследуемого графа. Предложен алгоритм квадратической (от числа вершин графа) временной, емкостной и коммуникационной сложностей, который распознает любой конечный неориентированный граф. Для распознавания графа требуется 2 различные краски. Метод основан на методе обхода графа в глубину. |
| format |
Article |
| author |
Стёпкин, А.В. |
| spellingShingle |
Стёпкин, А.В. Исследование структуры графа при помощи двух агентов Труды Института прикладной математики и механики |
| author_facet |
Стёпкин, А.В. |
| author_sort |
Стёпкин, А.В. |
| title |
Исследование структуры графа при помощи двух агентов |
| title_short |
Исследование структуры графа при помощи двух агентов |
| title_full |
Исследование структуры графа при помощи двух агентов |
| title_fullStr |
Исследование структуры графа при помощи двух агентов |
| title_full_unstemmed |
Исследование структуры графа при помощи двух агентов |
| title_sort |
исследование структуры графа при помощи двух агентов |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2016 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/140863 |
| citation_txt |
Исследование структуры графа при помощи двух агентов / А.В. Стёпкин // Труды Института прикладной математики и механики НАН Украины. — Слов’янськ: ІПММ НАН України, 2016. — Т. 30. — С. 111-121. — Бібліогр.: 12 назв. — рос. |
| series |
Труды Института прикладной математики и механики |
| work_keys_str_mv |
AT stëpkinav issledovaniestrukturygrafapripomoŝidvuhagentov |
| first_indexed |
2023-10-18T21:23:37Z |
| last_indexed |
2023-10-18T21:23:37Z |
| _version_ |
1796152692532314112 |