Распознавание конечных графов тремя агентами
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Распознавание конечных графов тремя агентами
|
|
| Creator |
Стёпкин, А.В.
|
|
| Subject |
Системы и методы искусственного интеллекта
|
|
| 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. |
|
| Date |
2014-03-31T12:34:03Z
2014-03-31T12:34:03Z 2011 |
|
| Type |
Article
|
|
| Identifier |
Распознавание конечных графов тремя агентами / А.В. Стёпкин // Штучний інтелект. — 2011. — № 2. — С. 84-93. — Бібліогр.: 8 назв. — рос.
1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/58846 519.7 |
|
| Language |
ru
|
|
| Relation |
Штучний інтелект
|
|
| Publisher |
Інститут проблем штучного інтелекту МОН України та НАН України
|
|