Возможность и сложность распознавания графов коллективом агентов
Journal: Збірник наукових праць фізико-математичного факультету ДДПУ (Vol.-, No. 3)Publication Date: 2013-04-25
Authors : Стёпкин А.В.;
Page : 104-113
Keywords : распознавание графа; обход в глубину; агент-исследователь; агент-экспериментатор;
Abstract
В работе рассматривается задача распознавания конечного графа коллективом агентов. Два агента-исследователя одновременно передвигаются по графу, считывают и изменяют отметки на элементах графа, передают необходимую информацию агенту- экспериментатору, который и распознает исследованный граф. Предложен алгоритм кубической (от числа вершин графа) временной и квадратической емкостной сложностей, который распознает любой конечный неориентированный граф без петель и кратных ребер. Для распознавания графа каждому агенту необходимо 2 различные краски (всего 3краски). Метод основан на методе обхода графа в глубину
Other Latest Articles
- Использование генетических алгоритмов для решения задачи о расщеплении множества
- О естественноматематическом образовании в постнеклассический период развития науки
- Исследование распределения дефектов в полупроводниковых пластинах интегральных схем при воздействии механических напряжений
- Формування наноструктур у монокристалічному германії за умови дислокаційно поверхневої дифузії
- Дослідження імовірнісних алгоритмів тестування простоти чисел
Last modified: 2018-02-21 05:10:13