Алгоритм распознавания конечных графов коллективом агентов
Електронний архів E-archive DonNTU – (Electronic archive Donetsk National Technical University)
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Алгоритм распознавания конечных графов коллективом агентов
|
|
| Creator |
Стёпкин, А.В.
|
|
| Description |
В настоящее время интенсивно развивается такое направление математической кибернетики, как теория дискретных динамических систем . В общей схеме Глушкова – Летичевского такая система представляется в виде модели взаимодействия управляющей и управляемой систем . Подобное взаимодействие рассматривалось в , в предположении, что оно представлено передвижением одного агента-исследователя (АИ) по неизвестному графу и обменом данными с агентом-экспериментатором (АЭ), который и производил восстановление графа по данным, полученным от АИ. На мой взгляд, мало исследована возможность и сложность распознавания графов коллективом агентов. Рассматривается задача распознавания неизвестного графа коллективом агентов. Два агента-исследователя одновременно передвигаются по графу, считывают и изменяют метки на элементах графа, передают информацию агенту-экспериментатору, который и выполняет восстановление графа. Предложен алгоритм, который распознает любой конечный неориентированный граф. Для распознавания графа каждому агенту требуется 2 различные краски (всего 3 краски), квадратическое (от числа вершин графа) число шагов и квадратичная память. Метод основан на методе обхода графа в глубину. |
|
| Date |
2012-04-30T14:52:15Z
2012-04-30T14:52:15Z 2011-04-12 |
|
| Type |
Article
|
|
| Identifier |
http://ea.donntu.edu.ua/handle/123456789/12753
|
|
| Language |
other
|
|
| Relation |
Том Первый;Информационные управляющие системы и технологии
|
|
| Publisher |
ДонНТУ
|
|