Распознавание конечных графов тремя агентами

В статье рассматривается проблема распознавания конечных графов тремя агентами. Два агента-исследователя передвигаются по графу, считывают, анализируют и изменяют метки элементов графа, передают информацию о своих передвижениях агенту-экспериментатору, который и распознает исследуемый граф. Предложе...

Full description

Saved in:

Bibliographic Details
Published in:	Штучний інтелект
Date:	2011
Main Author:	Стёпкин, А.В.
Format:	Article
Language:	Russian
Published:	Інститут проблем штучного інтелекту МОН України та НАН України 2011
Subjects:	Системы и методы искусственного интеллекта
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/58846
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:	Распознавание конечных графов тремя агентами / А.В. Стёпкин // Штучний інтелект. — 2011. — № 2. — С. 84-93. — Бібліогр.: 8 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-58846
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
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Распознавание конечных графов тремя агентами
spellingShingle	Распознавание конечных графов тремя агентами Стёпкин, А.В. Системы и методы искусственного интеллекта
title_short	Распознавание конечных графов тремя агентами
title_full	Распознавание конечных графов тремя агентами
title_fullStr	Распознавание конечных графов тремя агентами
title_full_unstemmed	Распознавание конечных графов тремя агентами
title_sort	распознавание конечных графов тремя агентами
author	Стёпкин, А.В.
author_facet	Стёпкин, А.В.
topic	Системы и методы искусственного интеллекта
topic_facet	Системы и методы искусственного интеллекта
publishDate	2011
language	Russian
container_title	Штучний інтелект
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
format	Article
title_alt	Розпізнавання скінченних графів трьома агентами Finite Graphs Exploration by Three Agents
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.
issn	1561-5359
url	https://nasplib.isofts.kiev.ua/handle/123456789/58846
citation_txt	Распознавание конечных графов тремя агентами / А.В. Стёпкин // Штучний інтелект. — 2011. — № 2. — С. 84-93. — Бібліогр.: 8 назв. — рос.
work_keys_str_mv	AT stepkinav raspoznavaniekonečnyhgrafovtremâagentami AT stepkinav rozpíznavannâskínčennihgrafívtrʹomaagentami AT stepkinav finitegraphsexplorationbythreeagents
first_indexed	2025-12-07T18:51:49Z
last_indexed	2025-12-07T18:51:49Z
_version_	1850876635371274240

Распознавание конечных графов тремя агентами

Institution

Similar Items