Распознавание конечных графов тремя агентами
В статье рассматривается проблема распознавания конечных графов тремя агентами. Два агента-исследователя передвигаются по графу, считывают, анализируют и изменяют метки элементов графа, передают информацию о своих передвижениях агенту-экспериментатору, который и распознает исследуемый граф. Предложе...
Gespeichert in:
| Veröffentlicht in: | Штучний інтелект |
|---|---|
| Datum: | 2011 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут проблем штучного інтелекту МОН України та НАН України
2011
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/58846 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Распознавание конечных графов тремя агентами / А.В. Стёпкин // Штучний інтелект. — 2011. — № 2. — С. 84-93. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862725296366551040 |
|---|---|
| author | Стёпкин, А.В. |
| author_facet | Стёпкин, А.В. |
| citation_txt | Распознавание конечных графов тремя агентами / А.В. Стёпкин // Штучний інтелект. — 2011. — № 2. — С. 84-93. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| description | В статье рассматривается проблема распознавания конечных графов тремя агентами. Два агента-исследователя передвигаются по графу, считывают, анализируют и изменяют метки элементов графа, передают информацию о своих передвижениях агенту-экспериментатору, который и распознает исследуемый граф. Предложен алгоритм временной сложности О(n³) и емкостной – О(n²), который распознает любой конечный неориентированный граф. При распознавании каждый агент использует две различные краски (всего три краски). Метод основан на методе обхода графа в глубину.
У статті розглядається проблема розпізнавання скінченних графів трьома агентами. Два агенти-дослідники рухаються графом, зчитують, аналізують та змінюють помітки елементів графа, передають інформацію про свої переміщення агенту-експериментатору, який розпізнає досліджуваний граф. Запропоновано алгоритм часової складності О(n³) та ємнісної – О(n²), який розпізнає будь-який скінченний неорієнтований граф. Для розпізнавання кожному агенту необхідно дві різні фарби (усього три фарби). Метод базується на методі обходу графа в глибину.
The Problem of finite graphs exploration by three agents is considered in this work. Two agents-researchers move on graph, they read, analyze and change marks of graph elements, transfer the information about their movements and colorings to the agent-experimenter. It builds explored graph representation. The algorithm with О(n³) time (n is amount of nodes of graph) and О(n²) space complexities is proposed. It recognizes any finite non-oriented graph. For graph exploration each agent needs two different marks (three colors in total). The method is based on the depth-first traversal method.
|
| first_indexed | 2025-12-07T18:51:49Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-58846 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T18:51:49Z |
| publishDate | 2011 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Стёпкин, А.В. 2014-03-31T12:34:03Z 2014-03-31T12:34:03Z 2011 Распознавание конечных графов тремя агентами / А.В. Стёпкин // Штучний інтелект. — 2011. — № 2. — С. 84-93. — Бібліогр.: 8 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/58846 519.7 В статье рассматривается проблема распознавания конечных графов тремя агентами. Два агента-исследователя передвигаются по графу, считывают, анализируют и изменяют метки элементов графа, передают информацию о своих передвижениях агенту-экспериментатору, который и распознает исследуемый граф. Предложен алгоритм временной сложности О(n³) и емкостной – О(n²), который распознает любой конечный неориентированный граф. При распознавании каждый агент использует две различные краски (всего три краски). Метод основан на методе обхода графа в глубину. У статті розглядається проблема розпізнавання скінченних графів трьома агентами. Два агенти-дослідники рухаються графом, зчитують, аналізують та змінюють помітки елементів графа, передають інформацію про свої переміщення агенту-експериментатору, який розпізнає досліджуваний граф. Запропоновано алгоритм часової складності О(n³) та ємнісної – О(n²), який розпізнає будь-який скінченний неорієнтований граф. Для розпізнавання кожному агенту необхідно дві різні фарби (усього три фарби). Метод базується на методі обходу графа в глибину. The Problem of finite graphs exploration by three agents is considered in this work. Two agents-researchers move on graph, they read, analyze and change marks of graph elements, transfer the information about their movements and colorings to the agent-experimenter. It builds explored graph representation. The algorithm with О(n³) time (n is amount of nodes of graph) and О(n²) space complexities is proposed. It recognizes any finite non-oriented graph. For graph exploration each agent needs two different marks (three colors in total). The method is based on the depth-first traversal method. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Системы и методы искусственного интеллекта Распознавание конечных графов тремя агентами Розпізнавання скінченних графів трьома агентами Finite Graphs Exploration by Three Agents Article published earlier |
| spellingShingle | Распознавание конечных графов тремя агентами Стёпкин, А.В. Системы и методы искусственного интеллекта |
| title | Распознавание конечных графов тремя агентами |
| title_alt | Розпізнавання скінченних графів трьома агентами Finite Graphs Exploration by Three Agents |
| title_full | Распознавание конечных графов тремя агентами |
| title_fullStr | Распознавание конечных графов тремя агентами |
| title_full_unstemmed | Распознавание конечных графов тремя агентами |
| title_short | Распознавание конечных графов тремя агентами |
| title_sort | распознавание конечных графов тремя агентами |
| topic | Системы и методы искусственного интеллекта |
| topic_facet | Системы и методы искусственного интеллекта |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/58846 |
| work_keys_str_mv | AT stepkinav raspoznavaniekonečnyhgrafovtremâagentami AT stepkinav rozpíznavannâskínčennihgrafívtrʹomaagentami AT stepkinav finitegraphsexplorationbythreeagents |