ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

Возможность и сложность распознавания конечного графа коллективом агентов

Journal: Збірник наукових праць фізико-математичного факультету ДДПУ (Vol.1, No. 10)

Publication Date:

Authors : ;

Page : 132-139

Keywords : ;

Source : Downloadexternal Find it from : Google Scholarexternal

Abstract

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

Last modified: 2018-02-23 16:20:20