Исследование структуры графа при помощи двух агентов
В работе рассматривается решение задачи распознавания конечных неориентированных графов двумя агентами. Один агент-исследователь передвигается по графу, считывает и изменяет метки элементов графа и передает информацию о своих действиях агенту-экспериментатору, который строит представление исследуемо...
Gespeichert in:
| Datum: | 2016 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2016
|
| Schriftenreihe: | Труды Института прикладной математики и механики |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/140863 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Исследование структуры графа при помощи двух агентов / А.В. Стёпкин // Труды Института прикладной математики и механики НАН Украины. — Слов’янськ: ІПММ НАН України, 2016. — Т. 30. — С. 111-121. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-140863 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1408632018-07-18T01:23:24Z Исследование структуры графа при помощи двух агентов Стёпкин, А.В. В работе рассматривается решение задачи распознавания конечных неориентированных графов двумя агентами. Один агент-исследователь передвигается по графу, считывает и изменяет метки элементов графа и передает информацию о своих действиях агенту-экспериментатору, который строит представление исследуемого графа. Предложен алгоритм квадратической (от числа вершин графа) временной, емкостной и коммуникационной сложностей, который распознает любой конечный неориентированный граф. Для распознавания графа требуется 2 различные краски. Метод основан на методе обхода графа в глубину. В роботі розглядається розв’язок задачі розпізнавання скінчених неорієнтованих графів двома агентами. Один агент-дослідник рухається графом, зчитує та змінює помітки на елементах графу та передає інформацію про свої дії агенту-експериментатору, який будує уявлення про досліджуваний граф. Пропонується алгоритм квадратичної (від кількості вершин графу) часової, ємнісної та комунікаційної складностей, який розпізнає довільний скінчений неорієнтований граф. Для розпізнавання графу необхідно дві різні фарби. Метод базується на методі обходу графа в глибину. This paper considers the problem of exploration of finite undirected graphs by two agents. One agentresearcher traverse a graph, read and change labels of graph elements, and send necessary information to the agent-experimenter constructing a representation of the graph being explored. An exploration algorithm is proposed with a quadratic (with respect to the number of nodes) time complexity, space complexity and communication complexity. An algorithm is proposed explored any finite undirected graph. Graph’s exploring needs two different colors. The algorithm is based on the depth-first traversal method. 2016 Article Исследование структуры графа при помощи двух агентов / А.В. Стёпкин // Труды Института прикладной математики и механики НАН Украины. — Слов’янськ: ІПММ НАН України, 2016. — Т. 30. — С. 111-121. — Бібліогр.: 12 назв. — рос. 1683-4720 http://dspace.nbuv.gov.ua/handle/123456789/140863 519.7 ru Труды Института прикладной математики и механики Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
В работе рассматривается решение задачи распознавания конечных неориентированных графов двумя агентами. Один агент-исследователь передвигается по графу, считывает и изменяет метки элементов графа и передает информацию о своих действиях агенту-экспериментатору, который строит представление исследуемого графа. Предложен алгоритм квадратической (от числа вершин графа) временной, емкостной и коммуникационной сложностей, который распознает любой конечный неориентированный граф. Для распознавания графа требуется 2 различные краски. Метод основан на методе обхода графа в глубину. |
| format |
Article |
| author |
Стёпкин, А.В. |
| spellingShingle |
Стёпкин, А.В. Исследование структуры графа при помощи двух агентов Труды Института прикладной математики и механики |
| author_facet |
Стёпкин, А.В. |
| author_sort |
Стёпкин, А.В. |
| title |
Исследование структуры графа при помощи двух агентов |
| title_short |
Исследование структуры графа при помощи двух агентов |
| title_full |
Исследование структуры графа при помощи двух агентов |
| title_fullStr |
Исследование структуры графа при помощи двух агентов |
| title_full_unstemmed |
Исследование структуры графа при помощи двух агентов |
| title_sort |
исследование структуры графа при помощи двух агентов |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2016 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/140863 |
| citation_txt |
Исследование структуры графа при помощи двух агентов / А.В. Стёпкин // Труды Института прикладной математики и механики НАН Украины. — Слов’янськ: ІПММ НАН України, 2016. — Т. 30. — С. 111-121. — Бібліогр.: 12 назв. — рос. |
| series |
Труды Института прикладной математики и механики |
| work_keys_str_mv |
AT stëpkinav issledovaniestrukturygrafapripomoŝidvuhagentov |
| first_indexed |
2025-07-10T11:25:34Z |
| last_indexed |
2025-07-10T11:25:34Z |
| _version_ |
1837259018880417792 |
| fulltext |
ISSN 1683-4720 Труды ИПММ НАН Украины. 2016. Том 30
УДК 519.7
c⃝2016. А. В. Стёпкин
ИССЛЕДОВАНИЕ СТРУКТУРЫ ГРАФА ПРИ ПОМОЩИ ДВУХ
АГЕНТОВ
В работе рассматривается решение задачи распознавания конечных неориентированных графов
двумя агентами. Один агент-исследователь передвигается по графу, считывает и изменяет метки
элементов графа и передает информацию о своих действиях агенту-экспериментатору, который
строит представление исследуемого графа. Предложен алгоритм квадратической (от числа вер-
шин графа) временной, емкостной и коммуникационной сложностей, который распознает любой
конечный неориентированный граф. Для распознавания графа требуется 2 различные краски.
Метод основан на методе обхода графа в глубину.
Ключевые слова: распознавание графа, обход графа, обход в глубину, агенты.
Введение.
Актуальной проблемой математической кибернетики является проблема вза-
имодействия управляющей и управляемой систем [1]. Ранее подобное взаимодей-
ствие было рассмотрено в [2–4], в предположении, что оно представлено передви-
жением агентов-исследователей (АИ) по неизвестному графу и обменом данными
с агентом-экспериментатором (АЭ), который и производил распознавание графа
по данным, полученным от АИ.
Перемещение агента в операционной среде невозможно без построения пол-
ной модели выбранной среды. В вопросах такого моделирования определен ряд
подходов, одним из которых является топологический [5]. При котором блуждаю-
щему агенту доступна информация о связях между различными областями среды
и недоступна метрическая и алгоритмическая информация о среде. Зачастую по-
добная ситуация возникает в роботике [6]. Топологическая модель представляет
собой граф, оснащенный дополнительной информацией на ребрах, в вершинах и
инциденторах.
Данная работа посвящена решению задачи, в предположении, что взаимодей-
ствие управляющей и управляемой систем представляется процессом перемещения
одного АИ по конечному неориентированному графу [7]. А суть взаимодействия
заключается в обмене данными АИ с АЭ, на основе которого возможно распозна-
вание графа.
1. Основные определения и обозначения.
Для распознавания произвольного конечного неориентированного графа тре-
буется разработать такой алгоритм функционирования агентов, что АИ, поме-
щенный в произвольную вершину неизвестного агентам графа G, все элементы
которого окрашены белым цветом, через конечное число шагов обойдет его, пе-
редавая АЭ информацию. АЭ, в свою очередь, используя эту информацию, через
конечное число шагов построит представление графа H, изоморфного G, то есть
111
А. В. Стёпкин
распознает граф G.
Рассматриваются конечные, неориентированные графы без петель и кратных
ребер. Все неопределяемые понятия общеизвестны, и с ними можно ознакомиться,
например, в [8, 9]. Пусть G = (V,E) — граф, у которого V — множество вер-
шин, E — множество ребер, мощности которых равны n и m соответственно.
Для уточнения принадлежности множеств V и E некоторому графу G приня-
ты обозначения VG и EG соответственно. Ребром будем называть двухэлемент-
ное подмножество {u, v} множества V , вершины u, v — смежными, а ребро {u, v}
— инцидентным вершинам u, v. Такое ребро будем обозначать (u, v) или (v, u).
Тройку ((v, u), u) будем называть инцидентором (точкой соединения) ребра (v, u)
и вершины u. Под дальним инцидентором вершины v будем понимать инциден-
тор ((v, u), u), а под ближним — ((v, u), v). Множество таких троек обозначим I.
Множество L = V ∪ E ∪ I называется множеством элементов графа G. Пусть M
некоторое конечное множество. Функцией раскраски графа G назовем сюръектив-
ное отображение µ : L→M . Пара (G,µ) называется раскрашенным графом.
Окрестностью Q(v) вершины v назовем множество элементов графа, состоящее
из вершины v, всех вершин u смежных с v, всех ребер (v, u) и всех инциденторов
((v, u), v) , ((v, u), u).
Последовательность u1, u2, ..., uk попарно смежных вершин называется путем
в графе G, а k — длиной этого пути. Простым путем будем называть путь, в
котором все вершины u1, u2, ..., uk попарно различны. В работе рассматриваются
только связные графы, то есть графы, в которых между двумя произвольными
вершинами существует хотя бы один путь.
Изоморфизмом графов G и H назовем такую биекцию φ : VG → VH , что
(v, u) ∈ EG точно тогда, когда (φ(v), φ(u)) ∈ EH . Таким образом, изоморфные
графы равны с точностью до обозначения вершин и раскраски их элементов.
Нумерацией F : V → N вершин графа G называется инъективное отображе-
ние множества его вершин во множество натуральных чисел. Номер вершины v
в нумерации F обозначается F (v). Прямой нумерацией вершин графа называется
нумерация, соответствующая порядку их обхода при поиске в глубину [8]. Далее
будет рассматриваться прямая нумерация. Древесными ребрами [9] называются
ребра, порождающие дерево поиска при обходе графа в глубину. Обратные ребра
— это ребра соединяющие две несмежные вершины одного дерева поиска в глуби-
ну.
По аналогии с [10] агентом будем называть нечто воспринимающее свою среду
с помощью датчиков и воздействующее на неё с помощью определенных меха-
низмов. В данной работе рассматривается коллектив, состоящий из двух агентов:
агента-исследователя и агента-экспериментатора. Агент-исследователь A облада-
ет следующими свойствами: он передвигаются по графу из вершины v в вершину
u по ребру (v, u), может изменять окраску вершин v, u, ребра (v, u) и инциденторов
((v, u), v) , ((v, u), u) метками из множества M , где M = {w, r, b}, где w интерпрети-
руется как белый цвет (краска), r — красный, b— черный. Краской будем называть
неограниченный ресурс агента. При пометке элемента графа, предыдущая крас-
112
Исследование структуры графа при помощи двух агентов
ка стирается и вместо неё, если это необходимо, наносится новая. Помеченным
путем будем называть простой путь, образованный последовательностью вершин,
помеченных красками в порядке их посещения агентом. Вершины помеченного
пути соединяются ребрами, окрашенными красной краской r, один из инциденто-
ров такого ребра помечен красной краской. Если все вершины помеченного пути
окрашены красной краской, то будем называть его красным путем. Таким длина
красного пути не превосходит число n. Отметим, что в начале работы рассмотрен-
ных ниже алгоритмов все элементы графа окрашены в белый цвет.
Находясь в вершине v, агент-исследователь воспринимает метки всех элемен-
тов окрестности Q(v) и на основании этой информации определяет по какому реб-
ру (v, u) будет дальше перемещаться и как будет окрашивать элементы из Q(v).
Вершину, в которой агент-исследователь находится в данный момент будем назы-
вать текущей для данного агента-исследователя вершиной.
Агент-экспериментатор обладает следующими свойствами: это неподвиж-
ный агент, который может передавать необходимую информацию агенту-
исследователю, а также принимать и идентифицировать сообщения от агента-
исследователя; обладает конечной, неограниченно растущей внутренней памя-
тью, в которой фиксируется результат функционирования агента-исследователя
на каждом шаге; строит представление графа G, вначале неизвестного агентам,
списками ребер и вершин.
Под экспериментом понимается движение агента-исследователя по графу, рас-
краска элементов графа, сбор локальной информации об окрестности вершины и
дальнейший обмен информацией с агентом-экспериментатором. А также постро-
ение агентом-экспериментатором графа, изоморфного исследуемому, с точностью
до отметок на графе. Для возможности проведения требуемых экспериментов, по
априорной информации о графе и о ресурсах агентов, необходимо создать алго-
ритм работы агентов, осуществляющих эти эксперименты.
Обозначим через T (n) временную сложность выполнения алгоритма распо-
знавания графа, S(n) — емкостную сложность, а через K(n) — коммуникаци-
онную сложность. Для оценки сложности вводится асимптотическое обозначение
O(n) [11]. В работе асимптотические оценки сложности алгоритмов считаются, как
обычно, в равномерной шкале [12].
Отметим, что работа алгоритма осуществляется следующим образом: АИ по-
мещается в произвольную вершину графа G, эта вершина сразу окрашивается в
красный цвет. АИ передвигается, пошагово передавая АЭ информацию, АЭ в свою
очередь обрабатывает полученные от АИ команды.
2. Стратегия решения задачи.
Рассматриваемый алгоритм основан на стратегии поиска в глубину. Эта стра-
тегия такова: агент идет «в глубину», пока это возможно, возвращается назад,
ищет другой путь с еще не посещенными вершинами и не пройденными ребрами.
После того, как агент обойдет все вершины и ребра он возвращается в исходную
вершину и завершает обход.
113
А. В. Стёпкин
Предлагаемая стратегия обладает рядом особенностей: 1) Граф G агентам не
известен; 2) При обходе графа G, агенты создают неявную нумерацию пройден-
ных вершин: при первом посещении вершины она окрашивается агентом в красный
цвет и ей фактически ставится в соответствие номер, равный значению перемен-
ной Сч_А. На основе построенной нумерации и происходит распознавание графа G
путем построения графа H изоморфного G. В процессе обхода агент строит неяв-
ное дерево поиска в глубину. Относительно этого дерева все ребра разделяются
на древесные (окрашиваются при первом прохождении по ним красным цветом)
и обратные (не принадлежат дереву и окрашиваются при первом прохождении в
черный цвет). Древесные ребра проходятся как минимум 2 раза и при последнем
проходе окрашиваются агентами в черный цвет. Обратные ребра проходятся от
одного до двух раз.
Красные вершины графа G, на каждом шаге алгоритма, образуют красный
путь. При проходе в новую вершину красный путь удлиняется, при проходе назад
– укорачивается, при распознавании обратного ребра – не изменяется. Вершина, у
которой все инцидентные ребра распознаны, окрашивается в черный цвет. Алго-
ритм заканчивает работу, когда красный путь становятся пустым, а все вершины
черными.
3. Обход графа.
В работе АИ можно выделить 2 режима:
1) Обычный режим. АИ движется вперед по белым вершинам, окрашивая вер-
шины, соединяющие их ребра и дальние инциденторы в красный цвет. Если нет
возможных путей перемещения, то АИ возвращается назад, окрашивая пройден-
ные вершины, ребра и ближние инциденторы в черный цвет. Вернувшись в началь-
ную вершину, АИ завершает работу. На каждом шаге АИ обменивается данными
с АЭ.
2) Распознавание обратных ребер. Если при движении вперед в вершине v было
обнаружено обратное ребро, то АИ прекращает работу в обычном режиме и пе-
реключается в режим распознавания обратных ребер. АИ красит в красный цвет
ближние инциденторы всех обратных ребер инцидентных вершине v. Завершив
покраску инциденторов, АИ передвигается назад по своему пути, до обнаружения
вершины инцидентной помеченному обратному ребру (под помеченным обратным
ребром понимается белое ребро, у которого дальний инцидентор и дальняя верши-
на окрашены в красный цвет), переходит по этому ребру, окрашивая его в черный
цвет. На этом этапе возможны два случая:
2.1) Распознаны не все, помеченные АИ, обратные ребра. В этом случае АИ
возвращается назад по пройденному на предыдущем шаге ребру, окрашивая в
черный цвет ближний инцидентор, и продолжает движение назад по своему пути,
до обнаружения следующей вершины, инцидентной помеченному обратному ребру.
2.2) Распознаны все, помеченные АИ, обратные ребра. В этом случае АИ окра-
шивает ближний инцидентор ребра, по которому он перешел на предыдущем шаге,
в черный цвет и завершает работу в режиме распознавания обратных ребер.
114
Исследование структуры графа при помощи двух агентов
4. Алгоритмы обхода и восстановления.
Опишем подробно алгоритмы, реализующие описанную выше стратегию. Про-
цесс распознавания состоит из двух принципиально разных типов алгоритмов:
«Обход» и «Восстановление». Первый тип алгоритма описывает обход неизвест-
ного графа G агентом-исследователем, с целью проведения серии элементарных
экспериментов и передачи информации АЭ. Второй тип алгоритма представляет
собой анализ результатов элементарных экспериментов и их объединение, в ре-
зультате которого будет построен граф H, изоморфный распознаваемому графу
G с точностью до отметок на графе.
Рассмотрим непосредственно сами алгоритмы.
Алгоритм работы АИ:
Вход: граф G неизвестный АИ и АЭ, все элементы графа G окрашены краской
w, АИ помещен в произвольную вершину v.
Выход: все элементы графа G, которые попадут в область работы АИ, окра-
шены краской b; АИ находится в исходной вершине v; пошагово выданы команды
АЭ.
Данные: v – рабочая вершина графа G, в которой находится агент.
1. Агент A красит (µ(v) := r);
2. if ∃(v, u) ∈ Q(v) : (µ(v, u) = w) and (µ(u) = µ(v) = r) then РАСП_А(v);
3. else if ∃(v, u) ∈ Q(v) : (µ(v, u) = w) and (µ(u) = w) then do
4. агент A выполняет процедуру ВПЕРЕД_А(v);
5. go to 2;
6. end do;
7. else if ∃(v, u) ∈ Q(v) : (µ(v)=r)and(µ((v, u),v)=r)and(µ(v, u)=r) then do
8. агент A выполняет процедуру НАЗАД_А(v);
9. go to 2;
10. end do;
11. else агент A выполняет процедуру СТОП_А(v);
РАСП_А(v)
1. while ∃(v, u) ∈ Q(v) : ((µ(v) = µ(u) = r) and (µ(v, u) = w)) do
2. агент A красит µ ((v, u) , v) := r;
3. агент A записывает в M : МЕТКА_OР_А;
4. end do;
115
А. В. Стёпкин
5. агент A выбирает (v, u) ∈ Q(v) : (µ ((v, u) , v) = r) and (µ (v, u) = r) and
and (µ (u) = r) и переходит по нему в вершину u;
6. v := u;
7. агент A записывает в M : ОТСТУП_А;
8. if @(v, u) ∈ Q(v) : (µ(v, u)=w)and(µ((v, u), u)=r)and(µ(v)=µ(u)=r) then go to
5 данной процедуры;
9. else do
10. агент A переходит по ребру (v, u), красит µ(v, u) := b;
11. v := u;
12. агент A записывает в список M : ВПЕРЕД_OР_А;
13. end do;
14. запрос UDOBR_A;
15. if UDOBR_A = TRUE then do
16. агент A выбирает (v, u) ∈ Q(v) : (µ(v, u) = b) and (µ ((v, u), v) = r) and
and (µ(v) = µ(u) = r) и красит µ ((v, u), v) := b;
17. агент A записывает в список M : РЕБРА_РАСПОЗНАНЫ_А;
18. end do;
19. else do
20. агент A выбирает (v, u) ∈ Q(v) : (µ(v, u) = b) and (µ ((v, u), v) = r) and
and (µ (v) = µ (u) = r) и переходит по нему в вершину u;
21. агент A красит µ ((v, u), v) := b;
22. v := u;
23. go to 5 данной процедуры;
24. end do;
При выполнении процедуры ВПЕРЕД_А(v), агент A выбирает из окрестности
Q(v) произвольное ребро (v, u), у которого µ(v, u) = w, µ(u) = w и переходит по
нему в вершину u. При этом окрашивает µ(v, u) := r, µ ((v, u), u) := r, µ(u) := r,
выполняет присвоение v := u и записывает в список M сообщение: ВПЕРЕД_A.
116
Исследование структуры графа при помощи двух агентов
В процессе выполнения процедуры НАЗАД_A(v), агент A выби-
рает из окрестности Q(v) ребро, для которого выполняется условие
(µ(v) = r) and (µ ((v, u), v) = r) and (µ(v, u) = r), и переходит по нему в вер-
шину u. При этом, производит окрашивание µ(v) := b, µ ((v, u), v) := b, µ(v, u) := b,
выполняет присвоение v := u и записывает в список M сообщение: НАЗАД_А.
При выполнении процедуры СТОП_А(v), агент A окрашивает µ(v) := b, запи-
сывает в список M сообщение: СТОП_А и завершает работу.
Выполняя процедуру ОТСТУП_А(v), агент A выбирает из окрестности Q(v)
ребро (v, u), у которого (µ ((v, u), v) = r) and (µ(v, u) = r) и переходит по нему в
вершину u, выполняет присвоение v := u и записывает в список M сообщение:
ОТСТУП_А.
Алгоритм работы АЭ:
Вход: список сообщений M от агента-исследователя.
Выход: список вершин VH и ребер EH графа H, изоморфного графу G.
Данные: VH , EH списки вершин и ребер графа H, изоморфного графу G. Сч_А
— счетчик числа посещенных вершин графа G агентом A. M — список сообще-
ний от агента-исследователя. i — счетчик используемый агентом A при подсчете
номеров вторых вершин помеченных обратных ребер. STOP_A — переменная,
используемая агентом A, для сигнализации агенту-экспериментатору, о заверше-
нии обхода графа. UDOBR_A — логическая переменная, используемая агентом
A для определения является ли рассматриваемое обратное ребро последним из
помеченных. KOBR_A — переменная, в которой агент A записывает количество
помеченных обратных ребер. r(1), r(2), ..., r(t) — список номеров вершин красного
пути, где t — длина этого списка. Mes — текущее сообщение.
1. Сч_А := 1, M := ∅, i := 0, EH := ∅, STOP_A := 0, UDOBR_A := FALSE,
KOBR_A := 0, t := 1, r(t) :=Сч_А, VH := {1};
2. while STOP_A = 0 do
3. if M ̸= ∅ then do
4. считать в Mes сообщение и удалить его из очереди M ;
5. ОБР_СП_А();
6. end do;
7. end do;
8. печать VH , EH .
ОБР_СП_А():
1. if Mes ="ВПЕРЕД_А"then ВПЕРЕД_А();
2. if Mes ="НАЗАД_А"then НАЗАД_А();
117
А. В. Стёпкин
3. if Mes ="РЕБРА_РАСПОЗНАНЫ_А"then РЕБРА_РАСПОЗНАНЫ_А();
4. if Mes ="ОТСТУП_А"then ОТСТУП_А();
5. if Mes ="МЕТКА_ОР_А"then МЕТКА_ОР_А();
6. if Mes ="ВПЕРЕД_ОР_А"then ВПЕРЕД_ОР_А();
7. if Mes ="СТОП_А"then СТОП_А().
ВПЕРЕД_А(): выполняются операции: Сч_А:=Сч_А+1; t := t+1; r (t) :=Сч_А;
VH := VH
∪
{Сч_А}; EH := EH
∪
{(r(t− 1), r(t))};
НАЗАД_А(): из списка r(1)...r(t) удаляется элемент r(t); t := t− 1;
РЕБРА_РАСПОЗНАНЫ_А(): i := 0;
ОТСТУП_А(): i := i+ 1;
МЕТКА_OР_А():KOBR_A := KOBR_A+ 1;
ВПЕРЕД_OР_А():KOBR_A := KOBR_A− 1; UDOBR_A := (KOBR_A = 0);
EH := EH
∪
{(r (t) , r (t− i))};
СТОП_А(): STOP_A := 1;
5. Свойства алгоритма распознавания.
Теорема. Три агента, выполнив алгоритм распознавания, распознают любой
граф G с точностью до изоморфизма.
Доказательство. В начале работы алгоритма распознавания, при n > 3, как
минимум два раза, когда агент-исследователь посещает белые вершины иссле-
дуемого графа G, выполняется процедура: ВПЕРЕД_А(v). Процедурой агента-
экспериментатора ВПЕРЕД_А() создается новая вершина графа H. Таким
образом, процесс выполнения описанного алгоритма индуцирует отображение
φ : VG → VH вершин графа G в вершины графаH. Причем равенство φ (v) =Сч_А
устанавливается, когда вершина v красится в красный цвет.
Указанное отображение естественным образом устанавливает неявную нуме-
рацию вершин графа G. Более того, отображение φ является биекцией, поскольку
рассматриваются связные графы, а в таких графах все вершины достижимы из
начальных вершин. Поэтому все вершины посещаются агентом-исследователем (то
есть окрашиваются в красный цвет) и при первом посещении вершины агентом ей
присваивается единственный номер.
Из описания алгоритма следует, что агент-исследователь проходит все реб-
ра графа G, поскольку по окончании алгоритма все ребра становятся черными.
Выполняя процедуру ВПЕРЕД_А() агент-экспериментатор распознает древесное
ребро (v,u) и так нумерует вершину u, что ребру (v, u) однозначно соответству-
ет ребро (φ(v), φ(u)) графа H. Выполняя процедуру ВПЕРЕД_OР_А() агент-
экспериментатор распознает обратное ребро (v,u) и ставит ему в однозначное со-
ответствие ребро (φ(v), φ(u)) графа H. Следовательно, φ является изоморфизмом
графа G на граф H. Что и требовалось доказать.
118
Исследование структуры графа при помощи двух агентов
Подсчитаем временную, емкостную и коммуникационную сложности в равно-
мерной шкале [12]. Рассмотрим подробнее свойства красного пути. Из описания
алгоритма следует, что на каждом шаге алгоритма красный путь — это простой
путь, берущий начало в вершине v с номером φ(v) = 1 и оканчивающийся в вер-
шине u с номером φ(u) = Сч_A. Следовательно, длина красного пути не превос-
ходит n.
Каждый раз при выполнении процедур ВПЕРЕД_А(v) и НАЗАД_А(v) агент-
исследователь проходит одно ребро. При однократном выполнении процедуры из
режима распознавания обратных ребер агент-исследователь метит не более n− 2
обратных ребер, по одному разу проходит не более n − 1 ребер красного пути, а
также по два раза проходится не более n− 2 обратных ребер.
При подсчете временной сложности алгоритма, будем считать, что инициа-
лизация алгоритма, и выбор одной из возможных процедур занимают некоторое
постоянное число единиц времени. Также будем считать, что проход по ребру
агента-исследователя и обработка команды агента-экспериментатора полученной
на данном этапе от агента-исследователя осуществляется за время равное некото-
рой константе. Примем, что время пересылки одного сообщения равно константе,
которая не превышает времени прохода по ребру агента-исследователя. Причем
общее время, затрачиваемое на анализ окрестности Q(v) вершины и выбор необ-
ходимых ребер оценивается как O(n2) [8]. Тогда временная сложность алгоритма
определяется следующими соотношениями:
1. Процедуры ВПЕРЕД_А(v) и НАЗАД_А(v) выполняются не более чем 2·(n− 1)
раз, общее время их выполнения оценивается как O (n).
2. Время, затрачиваемое на работу в режиме распознавания обратных ребер оце-
нивается как n · 4 ·O(n), то есть как O
(
n2
)
.
Таким образом верхняя оценка числа переходов по ребрам, совершаемых
агентом-исследователем равняется O(n2), а суммарная временная сложность T (n)
алгоритма удовлетворяет соотношению: T (n) = O
(
n2
)
.
Емкостная сложность S(n) алгоритма определяется суммарной сложностью
списков VH , EH , r(1), ..., r(t), сложность которых соответственно определяется ве-
личинами O (n) , O
(
n2
)
, O (n).
Следовательно: S (n) = O
(
n2
)
.
На каждом шаге алгоритма агент-исследователь отправляет агенту-
экспериментатору одно сообщение. Поэтому объем передаваемой агентами
информации оценивается как K(n) = O
(
n2
)
.
Учитывая описанные выше предположения о способе подсчета временной
сложности, имеет место следующая теорема:
Теорема. Временная, емкостная, коммуникационная сложности алгорит-
ма и число переходов по ребрам, совершаемых агентом-исследователем, равны
O
(
n2
)
, где n — число вершин графа. Для распознавания достаточно двух красок.
6. Выводы. Предложен алгоритм распознавания графа среды временная, ем-
костная, коммуникационная сложности и число переходов по ребрам которой рав-
119
А. В. Стёпкин
ны O
(
n2
)
. Агент-исследователь имеет конечную память, независимую от n, и ис-
пользует две краски.
1. Капитонова Ю. В., Летичевский А. А. Математическая теория проектирования вычисли-
тельных систем. – М.: Наука. 1988. – 296 с.
2. Грунский И.С., Татаринов Е. А. Распознавание конечного графа блуждающим по нему
агентом // Вестник Донецкого университета. Серия А. Естественные науки. – 2009. – T. 1.
– C. 492–497.
3. Стёпкин А. В. Использование коллектива агентов для распознавания графов // Компью-
терные исследования и моделирование. – 2013. – Т. 5, № 4. – С. 525–532.
4. Stepkin A. Using a Collective of Agents for Exploration of Undirected Graphs // Cybernetics and
Systems Analysis. – 2015. – V. 51, № 2. – P. 223–233.
5. Kuipers B. The spatial semantic hierarchy // Artificial Intelligence. – 2000. – V. 119, № 1–2. –
P. 191–233.
6. Dudek G., Jenkin M. Computational principles of mobile robotics. – Cambridge Univ. press,
Cambridge. 2000. – 280 p.
7. Кудрявцев В. Б., Алешин С.В., Подкозлин А. С. Введение в теорию автоматов. – М.: Наука,
1985. – 320 с.
8. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2001.
– 960 с.
9. Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и
применение. – СПБ.: БХВ–Петербург, 2003. – 1104 с.
10. Рассел С., Норвиг П. Искусственный интеллект: современный подход. — 2-е издание. — М.:
«Вильямс», 2006. — 1408 с.
11. Килибарда Г., Кудрявцев В. Б., Ушчумлич Щ. Коллективы автоматов в лабиринтах // Дис-
кретная математика. — 2003. – Т. 15, № 3. — С. 3–40.
12. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. —
М.: Мир, 1979. — 536 с.
A. V. Stepkin
Exploration of the graph structure by two agents.
This paper considers the problem of exploration of finite undirected graphs by two agents. One agent-
researcher traverse a graph, read and change labels of graph elements, and send necessary information
to the agent-experimenter constructing a representation of the graph being explored. An exploration
algorithm is proposed with a quadratic (with respect to the number of nodes) time complexity, space
complexity and communication complexity. An algorithm is proposed explored any finite undirected
graph. Graph’s exploring needs two different colors. The algorithm is based on the depth-first traversal
method.
Keywords: graph exploration, traversal of a graph, depth-first traversal method, agents.
А. В. Стьопкiн
Дослiдження структури графа за допомогою двох агентiв.
В роботi розглядається розв’язок задачi розпiзнавання скiнчених неорiєнтованих графiв двома
агентами. Один агент-дослiдник рухається графом, зчитує та змiнює помiтки на елементах графу
та передає iнформацiю про свої дiї агенту-експериментатору, який будує уявлення про дослiджу-
ваний граф. Пропонується алгоритм квадратичної (вiд кiлькостi вершин графу) часової, ємнiсної
120
Исследование структуры графа при помощи двух агентов
та комунiкацiйної складностей, який розпiзнає довiльний скiнчений неорiєнтований граф. Для
розпiзнавання графу необхiдно двi рiзнi фарби. Метод базується на методi обходу графа в гли-
бину.
Ключовi слова: розпiзнавання графу, обхiд графу, обхiд в глибину, агенти.
Донбасский государственный педагогический университет,
Славянск
stepkin.andrey@rambler.ru
Получено 06.09.16
121
|