Распознавание конечного графа коллективом агентов
Рассматривается задача распознавания неизвестного графа коллективом агентов. Два агента-исследователя передвигаются по графу, изменяют и считывают метки на элементах графа и передают информацию агенту-экспериментатору, который строит представление исследуемого графа. Предложен алгоритм, который расп...
Gespeichert in:
| Veröffentlicht in: | Труды Института прикладной математики и механики |
|---|---|
| Datum: | 2009 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2009
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/123897 |
| 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: | Распознавание конечного графа коллективом агентов / И.С. Грунский, А.В. Стёпкин // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2009. — Т. 19. — С. 43-52. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-123897 |
|---|---|
| record_format |
dspace |
| spelling |
Грунский, И.С. Стёпкин, А.В. 2017-09-13T09:23:19Z 2017-09-13T09:23:19Z 2009 Распознавание конечного графа коллективом агентов / И.С. Грунский, А.В. Стёпкин // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2009. — Т. 19. — С. 43-52. — Бібліогр.: 10 назв. — рос. 1683-4720 https://nasplib.isofts.kiev.ua/handle/123456789/123897 519.6 Рассматривается задача распознавания неизвестного графа коллективом агентов. Два агента-исследователя передвигаются по графу, изменяют и считывают метки на элементах графа и передают информацию агенту-экспериментатору, который строит представление исследуемого графа. Предложен алгоритм, который распознает любой конечный неориентированный граф. Для распознавания графа агентам требуется 2 различные краски, кубическое (от числа вершин графа) число шагов и квадратичная память. Метод основан на методе обхода графа в глубину. ru Інститут прикладної математики і механіки НАН України Труды Института прикладной математики и механики Распознавание конечного графа коллективом агентов 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 |
Грунский, И.С. Стёпкин, А.В. |
| publishDate |
2009 |
| language |
Russian |
| container_title |
Труды Института прикладной математики и механики |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| description |
Рассматривается задача распознавания неизвестного графа коллективом агентов. Два агента-исследователя передвигаются по графу, изменяют и считывают метки на элементах графа и передают информацию агенту-экспериментатору, который строит представление исследуемого графа. Предложен алгоритм, который распознает любой конечный неориентированный граф. Для распознавания графа агентам требуется 2 различные краски, кубическое (от числа вершин графа) число шагов и квадратичная память. Метод основан на методе обхода графа в глубину.
|
| issn |
1683-4720 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/123897 |
| citation_txt |
Распознавание конечного графа коллективом агентов / И.С. Грунский, А.В. Стёпкин // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2009. — Т. 19. — С. 43-52. — Бібліогр.: 10 назв. — рос. |
| work_keys_str_mv |
AT grunskiiis raspoznavaniekonečnogografakollektivomagentov AT stepkinav raspoznavaniekonečnogografakollektivomagentov |
| first_indexed |
2025-11-25T21:45:40Z |
| last_indexed |
2025-11-25T21:45:40Z |
| _version_ |
1850560358462259200 |
| fulltext |
ISSN 1683-4720 Труды ИПММ НАН Украины. 2009. Том 19
УДК 519.6
c©2009. И.С. Грунский, А.В. Стёпкин
РАСПОЗНАВАНИЕ КОНЕЧНОГО ГРАФА
КОЛЛЕКТИВОМ АГЕНТОВ
Рассматривается задача распознавания неизвестного графа коллективом агентов. Два агента-ис-
следователя передвигаются по графу, изменяют и считывают метки на элементах графа и пере-
дают информацию агенту-экспериментатору, который строит представление исследуемого графа.
Предложен алгоритм, который распознает любой конечный неориентированный граф. Для распо-
знавания графа агентам требуется 2 различные краски, кубическое (от числа вершин графа) число
шагов и квадратичная память. Метод основан на методе обхода графа в глубину.
Введение. Основной проблемой компьютерной науки, является проблема вза-
имодействия управляющей и управляемой систем, т.е. взаимодействия управляю-
щего автомата (агента) и его операционной среды [1]. В рассмотренном ниже слу-
чае взаимодействие этих систем представляется как процесс перемещения агентов
по графу среды [2], который является топологической моделью среды [3]. В этом
случае агенту доступна информация только о связях между различными областя-
ми среды и недоступна метрическая и алгоритмическая информация о данной сре-
де. Зачастую подобная ситуация возникает в роботике [4]. Топологическая модель
представляет собой граф с помеченными различными способами вершинами, дуга-
ми, инциденторами. Выделяют три основные задачи исследования среды агентом:
1) самолокализация агента; 2) контроль соответствия модели среды и самой сре-
ды; 3) построение агентом модели карты среды [4]. Значительное количество работ
(см. обзоры [5–7]) посвящено задаче распознавания среды, известен ряд алгорит-
мов распознавания, получено много результатов о возможности, невозможности и
сложности такого распознавания с помощью тех или иных средств агента. Однако
на наш взгляд, мало исследована возможность и сложность распознавания графа
более чем одним агентом.
В настоящей работе предложен новый алгоритм распознавания. В нем использует-
ся три агента: два агента-исследователя (АИ), которые перемещаются по графу, и
агент-экспериментатор (АЭ), который принимает сообщения АИ и по ним строит
представление исследуемого графа, основное внимание уделено анализу того, что
и как распознается на каждом шаге алгоритма и выделению элементарного экс-
перимента. Алгоритм основан на методе обхода графа вглубь и при этом агенты-
исследователи специальным образом окрашивают элементы графа. Алгоритм, на
наш взгляд, является базовым и на его основе авторы надеются создать новые бо-
лее эффективные алгоритмы, которые позволят улучшить результаты, полученные
с помощью аналогичного алгоритма [8].
1. Основные определения и обозначения.
1.1. Раскрашенные графы. Рассматриваются конечные, неориентированные
43
И.С. Грунский, А.В. Стёпкин
графы без петель и кратных ребер. Все неопределяемые понятия общеизвестны, их
можно найти, например, в [9-11]. Пусть G = (V, E) – граф, у которого V – множество
вершин, E – множество ребер, т.е. двухэлементных подмножеств (u, v), где u, v ∈ V .
Тройку ((u, v), v) будем называть инцидентором ("точкой прикосновения") ребра
(u, v) и вершины v. Множество таких троек обозначим I. Множество L = V ∪E ∪ I
назовем множеством элементов графа G. Функцией раскраски графа G назовем
отображение µ : L → {w, r, y, b}, где w интерпретируется как белый цвет (краска),
r – красный, y – желтый, b – черный. Пара (G,µ) называется раскрашенным гра-
фом. Последовательность u1, u2, ...uk попарно смежных вершин называется путем в
графе G, а k – длиной пути. При u1 = uk этот путь называется циклом. Окрест-
ностью O(v) вершины v будем называть множество элементов графа, состоящее
из вершины v, всех вершин u смежных с v, всех ребер (v, u) и всех инциденторов
((v, u), v), ((v, u), u). Мощность множеств вершин V и ребер E обозначим через n и m
соответственно. Ясно что m ≤ n(n−1)
2 . Изоморфизмом графа G и графа H назовем
такую биекцию ϕ : VG → VH , что (v, u) ∈ EG точно тогда, когда (ϕ(v), ϕ(u)) ∈ EH .
Таким образом, изоморфные графы равны с точностью до обозначения вершин и
раскраски их элементов.
1.2. Мобильные агенты. Мобильные агенты A и B характеризуются следую-
щими свойствами. Они передвигаются по графу из вершины v в вершину u по
ребру (v, u). При этом агенты могут изменять окраску вершин v, u, ребра (v, u),
инциденторов ((v, u), v),((v, u), u). Находясь в вершине v агенты A и B восприни-
мают метки всех элементов окрестности O(v) и на этом основании определяют по
какому ребру (v, u) они будут перемещаться и как будут перекрашивать элементы
v, u, (v, u), ((v, u) , v) , ((v, u) , u). АЭ передает, принимает и идентифицирует сообще-
ния АИ, обладает конечной, неограниченно растущей внутренней памятью, в кото-
рой фиксируется результат функционирования АИ на каждом шаге, и, кроме того,
постепенно выстраивается представление графа G вначале неизвестного агентам,
списками ребер и вершин.
1.3. Постановка задачи. Требуется разработать такой алгоритм функциони-
рования АИ(передвижения по графу, раскраски его элементов и передачи информа-
ции АЭ) и АЭ(восстановления графа по данным полученным от АИ), что АИ будучи
помещены в произвольные вершины произвольного неизвестного АИ и АЭ графа G,
все элементы которого окрашены цветом w, через конечное число шагов обойдут его,
пошагово передавая АЭ информацию, по которой АЭ через конечное число шагов
восстановит граф H, изоморфный G, т.е. распознает G.
2. Распознавание графа.
2.1. Стратегия распознавания графа. Предлагаемый алгоритм основан на
стратегии поиска в глубину. Эта стратегия такова: агенты идут “вглубь”, пока это
возможно, возвращаются назад, ищут другой путь с еще не посещенными верши-
нами и не пройденными ребрами, в случае обнаружения смежной вершины окра-
шенной в “чужой” цвет метим все перешейки из текущей вершины в чужую об-
ласть и сообщаем второму АИ, через АЭ о необходимости вернуться и распознать
помеченные перешейки, также передается информация о количестве помеченных
44
Распознавание конечного графа коллективом агентов
перешейков. Пока второй агент не распознает все перешейки, выбор дальнейшего
пути перемещения первым агентом изменяется. В таком случае поиск перешейков
выполняется непосредственно перед проверкой выполнения условий, связанных с
распознаванием дерева, построенного данным АИ. Если отсутствуют все возмож-
ные варианты перемещения, наличие которых проверяется до проверки на наличие
перешейка, то при обнаружении его, текущий агент останавливается до того момен-
та, пока все помеченные перешейки не будут распознаны вторым агентом.
Известен ряд алгоритмов поиска в глубину для известного графа [9–11]. Пред-
лагаемая ниже стратегия обладает рядом особенностей. 1) Граф G агентам не из-
вестен. 2) При прохождении вершин графа G агенты создают неявную нумерацию
пройденных вершин: при первом посещении вершины она окрашивается красным
цветом, если это агент A и желтым цветом в случае агента B и ей фактически
ставится в соответствие номер, равный значению переменной Сч_А для агента A
или Сч_В для агента B. Агент A ведет нумерацию нечетными числами, а агент B
четными, другими словами переменные Сч_А и Сч_B принимают соответственно
нечетные и четные значения. На основе этой нумерации и происходит восстановле-
ние графа путем построения графа H изоморфного G. В процессе поиска агенты
строят неявные деревья поиска в глубину и относительно этих деревьев все ребра
разделяются на древесные, т.е. принадлежащие деревьям и окрашиваемые при пер-
вом прохождении по ним в красный (желтый) цвет, обратные – не принадлежащие
дереву и окрашиваемые при первом прохождении в черный цвет и ребра перешейки,
которые соединяют деревья. Древесные ребра проходятся, по крайней мере, 2 раза
и при последнем проходе окрашиваются агентом в черный цвет, обратные прохо-
дятся один раз, а ребра перешейки проходятся каждым агентом два раза, первый
прошедший по нему агент метит перешеек, окрашивая его в красный цвет в случае
агента A или в желтый для агента B, второй прошедший по нему агент распознает
перешеек и красит его в черный цвет.
Древесные ребра распознаются агентами при первом проходе по ним. Красные
(желтые) вершины графа G, на каждом шаге алгоритма, образуют красный (жел-
тый) путь. С помощью этого пути распознаются обратные ребра, при проходе в но-
вую вершину красный (желтый) путь удлиняется, при проходе назад (в случае если
это не возврат для распознавания перешейков) – укорачивается, при распознавании
обратного ребра – не изменяется. Вершина, у которой все инцидентные ребра рас-
познаны красится черным. Алгоритм оканчивает работу, когда красный и желтый
пути становятся пустыми, а все вершины черными.
2.2. Распознавание графа. Весь процесс распознавания состоит из двух прин-
ципиально разных алгоритмов: 1) "Обход"; 2) "Восстановление". Первый алгоритм
описывает обход неизвестного графа G агентами-исследователями, с целью прове-
дения серии элементарных экспериментов и передачи информации АЭ. Второй ал-
горитм представляет собой анализ результатов элементарных экспериментов и их
объединение, в результате которого будет построен граф H, изоморфный распозна-
ваемому графу G. Стоит отметить, что совместная работа алгоритмов осуществ-
ляется в следующей последовательности: сначала ходит агент A, АЭ обрабатывает
45
И.С. Грунский, А.В. Стёпкин
полученные от него данные, далее ходит агент B, АЭ обрабатывает полученные
данные и т.д. Агенты исследователи помещаются в различные вершины графа G,
эти вершины сразу окрашиваются в красный и желтый цвет для агентов A и B
соответственно.
2.3. Алгоритм работы агента A.
Вход: граф G неизвестный АИ и АЭ, все элементы графа G окрашены краской
w, агент A помещен в произвольную вершину v.
Выход: все элементы графа G, которые попадут в область работы агента окра-
шены краской b, агент A находится в исходной вершине v;
Данные: v – рабочая вершина графа G, в которой находится агент.
Алгоритм:
1. Агент A красит (µ(v) := r);
2. Запрос AN ;
3. if AN=0 then do
4. Запрос F ;
5. if F=0 then МЕТИМ_ПЕР_А(v);
6. else ВЫБОР_ХОДА_А(v);
7. end do;
8. else РАСП_ПЕР_А(v);
Рассмотрим процедуры, используемые в данном алгоритме.
МЕТИМ_ПЕР_А(v)
1. if в O(v) обнаружено ребро, у которого (µ(v, u) = w)and(µ(u) = y) then do
2. Агент A выполняет процедуру МЕТИМ_AB(v);
3. go to 1 данной процедуры;
4. end do;
5. else do
6. Агент A запрашивает у АЭ значение переменной E;
7. if E=0 then ВЫБОР_ХОДА_А(v);
8. else do
9. Агент A выполняет процедуру ФИКС_A(v);
10. go to 2 алгоритма обхода;
11. end do;
12. end do;
ВЫБОР_ХОДА_А(v)
1. if в O(v) есть ребро, у которого (µ(v, u) = w)and(µ(u) = µ(v) = r)then do
2. Агент A выполняет процедуру РАСП_A(v);
3. go to 2 алгоритма обхода;
4. end do;
5. else if в O(v) есть ребро, у которого (µ(v, u) = w)and(µ(u) = w)then do
6. Агент выполняет процедуру ВПЕРЕД_A(v);
7. go to 2 алгоритма обхода;
8. end do;
9. else if в O(v) есть ребро, у которого(µ(v, u) = w)and(µ(u) = y) then do
46
Распознавание конечного графа коллективом агентов
10. Агент выполняет процедуру СТОИТ_A (v);
11. go to 2 алгоритма обхода;
12. end do;
13. else if в O(v) есть ребро, у которого (µ(v, u) = y) then do
14. Агент A выполняет процедуру СТОИТ_A(v);
15. go to 2 алгоритма обхода;
16. end do;
17. else if в O(v) есть ребро, у которого (µ(v, u) = r)and(µ(u) = y)then do
18. Агент A выполняет процедуру СТОИТ_A (v);
19. go to 4 алгоритма обхода;
20. end do;
21. else if в O(v) есть ребро,т.ч.(µ(v, u) = r)and(µ(v) = r)and(µ((v, u), v) = r)
then do
22. Агент A выполняет процедуру НАЗАД_A(v);
23. go to 2 алгоритма обхода;
24. end do;
25. else агент A выполняет процедуру СТОП_A;
РАСП_ПЕР_А(v)
1. if в O(v) есть ребро, у которого (µ(v, u) = y) then do
2. Агент A выполняет процедуру РАСП_АВВ(v);
3. Агент A запрашивает у АЭ значение переменной K;
4. if K 6= 0 then go to 1 данной процедуры;
5. else do
6. Агент A выполняет процедуру ОБН_А(v);
7. if в O(v) есть ребро,т.ч.(µ(v, u) = r)and(µ(u) = r)and(µ((v, u), ) = r)
then do
8. Агент A выполняет процедуру ВПЕРЕД_AR(v);
9. go to 7 данной процедуры;
10. end do;
11. else go to 2 алгоритма обхода;
12. end do;
13. end do;
14. else do
15. Агент A выполняет процедуру ОТСТУП_А(v);
16. Перемещаемся в строку 1 данной процедуры;
17. end do;
ВПЕРЕД_А(v): агент A выбирает из O(v) ребро (v, u) у которого µ(v, u) = w,
µ(u) = w, переходит по нему в вершину u, окрашивая µ(v, u) := r, µ(u) := r,
µ((v, u), u) := r, выполняет v := u и записывает в список M : ВПЕРЕД_A;
НАЗАД_A(v): агент A выбирает из O(v) произвольное ребро (v, u) у которого
((µ(v, u) = r)and(µ((v, u), v) = r)and(µ(v) = r) и переходит по нему в вершину u
окрашивая µ(v) := b, µ(v, u) := b, выполняет v := u и записывает в M : НАЗАД_А;
СТОИТ_А(v): aгент A не выполняет никаких действий, запись в M : СТОИТ_А;
47
И.С. Грунский, А.В. Стёпкин
МЕТИМ_АВ(v): агент A выбирает из O(v) произвольное ребро (v, u), у которого
(µ(v, u) = w)and(µ(u) = y), переходит по нему в вершину u, окрашивая µ(v, u) := r,
µ((v, u), u) := r, выполняет v := u и записывает в M : ВПЕРЕД_AB, на следующем
шаге A выбирает из O(v) ребро (v, u), у которого ((µ(v, u) = r)and(µ(v) = y)), и
переходит по нему в вершину u, выполняет v := u и записывает в M : НАЗАД_АB;
РАСП_АВB(v): агент A выбирает из O(v) ребро (v, u), у которого µ(v, u) = y, и
переходит по нему в вершину u, окрашивая µ(v, u) := r, µ((v, u), u) := b, выполняет
v := u и записывает в список M : ВПЕРЕД_ABB, на следующем шаге агент A выби-
рает из O(v) ребро (v, u), у которого ((µ(v, u) = r)and(µ((v, u), v) = b)), и переходит
по нему в вершину u, окрашивая µ(v, u) := b, выполняет v := u и записывает в
список M : НАЗАД_АBB;
ВПЕРЕД_АR(v): агент A выбирает из O(v) произвольное ребро (v, u), у которого
(µ(v, u) = r)and(µ(u) = r)and(µ((v, u), u) = r), и переходит по нему в вершину u,
выполняет v := u и записывает в M : ВПЕРЕД_AR;
ОТСТУП_А(v): агент A выбирает из O(v) произвольное ребро (v, u), у которого
((µ(v, u) = r)and(µ((v, u), v) = r)), и переходит по нему в вершину u, выполняет
v := u и записывает в M : ОТСТУП_А;
ФИКС_А(v): агент A записывает в M : ФИКС_А;
ОБН_А(v): Агент A записывает в M : ОБН_А;
РАСП_А(v)
1. A выбирает из O(v) ребро (v, u), у которого (µ(v) = µ(u) = r)and(µ(v, u) = w),
и переходит по нему в вершину u;
2. Агент A красит µ(v, u) = b;
3. Агент A выбирает из O(u) произвольное ребро (u, l), у которого
(µ(u, l) = r)and(µ((u, l), l) = r)and(µ(l) = r), и переходит по нему в вершину l;
4. u:=l;
5. Агент A записывает в M : РАСП_А;
6. while в O(u) есть ребро (u, l), у которого
(µ(u, l) = r)and(µ((u, l), l) = r)and(µ(l) = r) do
7. агент A переходит по ребру (u, l) в вершину l;
8. u:=l;
9. Агент A записывает в M : ОТСТУПИЛ_А;
10. end do;
11. Агент A записывает в M : РЕБРО_РАСПОЗНАНО_А;
Алгоритм работы агента B аналогичен алгоритму работы агента A.
2.4. Алгоритм "Восстановление".
Вход: списки сообщений M и N от АИ.
Выход: список вершин VH и ребер EH графа H, изоморфного G.
Данные: VH , EH – списки вершин и ребер графа H, изоморфного графу G.
Сч_А, Сч_В – счетчики числа посещенных вершин графа G агентов A и B соответ-
ственно. r(1)r(2)..r(t) – список номеров вершин красного пути, t – длина этого спис-
ка. y(1)y(2)..y(p) – список номеров вершин желтого пути, p – длина этого списка.
N_A – переменная, в которой хранится номер вершины, из которой агент последний
48
Распознавание конечного графа коллективом агентов
раз помечал перешейки. N_B – переменная, в которой хранится номер вершины,
из которой агент последний раз помечал перешейки. F – количество перешейков
из вершины N_А, помеченных для распознавания. K – количество перешейков из
вершины N_В, помеченных для распознавания. E – переменная, в которой делается
отметка о том, был ли на предыдущем шаге агентом A помечен перешеек (значение
"1") или нет (значение "0"). L – переменная, в которой делается отметка о том,
был ли на предыдущем шаге агентом B помечен перешеек (значение "1") или нет
(значение "0"). i – счетчик, используемый агентом A при подсчете номера второй
вершины перешейка и номера второй вершины обратного ребра. j – счетчик, ис-
пользуемый агентом B при подсчете номера второй вершины перешейка и номера
второй вершины обратного ребра. Mes – текущее сообщение. AN – переменная, в
которой значение "1" дает агенту A сигнал для возврата и распознавания поме-
ченных агентом B перешейков, значение "0" позволяет агенту A работать дальше
в обычном режиме. BN – переменная, в которой значение "1" дает агенту B сиг-
нал для возврата и распознавания помеченных агентом A перешейков, значение "0"
позволяет A работать дальше в обычном режиме.
Алгоритм:
1. Сч_А:=1;
2. Сч_В:=2;
3. Обнуляем массивы: AN, BN, N_A, N_B, N, M, F, K, E, L, i, j, EH ;
4. t:=1;
5. p:=1;
6. r(t):= Сч_А;
7. y(p):= Сч_В;
8. VH := {1, 2};
9. While (M 6= ∅)and(N 6= ∅) do
10. if M 6= ∅ then do Прочитать в Mes сообщение и удалить его из M ;
11. ОБР_СП_А(); end do;
12. if N 6= ∅ then do Прочитать в Mes сообщение и удалить его из N ;
13. ОБР_СП_B(); end do;
14. end do;
15. Печать VH , EH .
Рассмотрим используемые процедуры.
ОБР_СП_А():
1. if Mes = "ВПЕРЕД_А" then ВПЕРЕД_А() ;
2. if Mes = "ВПЕРЕД_АВ" then ВПЕРЕД_AB();
3. if Mes = "ВПЕРЕД_АBB" then ВПЕРЕД_ABB();
4. if Mes = "НАЗАД_А" then НАЗАД_А();
5. if Mes = "НАЗАД_АВ" then НАЗАД_АВ();
6. if Mes = "НАЗАД_АВВ" then НАЗАД_АВВ();
7. if Mes = "ФИКС_А" then ФИКС_А();
8. if Mes = "ОБН_А" then ОБН_А();
9. if Mes = "РАСП_А" then РАСП_А();
49
И.С. Грунский, А.В. Стёпкин
10. if Mes = "ОТСТУП_А" then ОТСТУП_А();
ВПЕРЕД_А(): выполняется серия операций: Сч_А:=Сч_А+2 ; t := t + 1;
r(t):=Сч_А; VH := VH∪{Сч_А}; EH := EH∪{r(t-1),r(t)};
НАЗАД_А(): из списка r(1)..r(t) удаляется элемент r(t); t := t− 1;
ВПЕРЕД_AB(): F присваивается значение F + 1;
НАЗАД_АВ(): E присваивается значение 1;
ВПЕРЕД_ABB(): EH := EH∪{N_A, r(t)− i};
НАЗАД_АВВ(): K присваивается значение K − 1;
ОТСТУП_А(): i присваивается значение i + 2;
ФИКС_А(): выполняется серия операций: N_A:=Сч_А; BN:=1 ; E := 0;
ОБН_А(): отменяется команда "назад" для A(AN := 0), обнуляется параметр i;
РАСП_А():
1. Прочитать в Mes сообщение из M и удалить его;
2. While Mes ="ОТСТУПИЛ_А" do
3. i := i + 2;
4. end do;
5. EH := EH∪{r(t),r(t)-i};
6. i := 0;
Процедуры обработки списка сообщений от агента B аналогичны.
3. Свойства алгоритма распознавания. В начале алгоритма, если n ≥ 3,
то как минимум по одному разу выполнятся процедуры: ВПЕРЕД_А(v), ВПЕ-
РЕД_А(), поскольку в рассматриваемых графах простых циклов длины меньшей
3 нет. При выполнении агентом A процедуры ВПЕРЕД_А(v) он посещает новую
вершину графа G, процедурой ВПЕРЕД_А() агента АЭ создается новая вершина
графа H. Следовательно, в процессе выполнения алгоритма устанавливается неяв-
ная нумерация ϕ : VG → VH вершин графа G в вершины графа H, где устанавлива-
ется равенство ϕ(v) = t, когда вершина v красится в красный цвет и t =Сч_А или
равенство ϕ(s) = p, когда вершина s красится в желтый цвет и p =Сч_B. Эта ну-
мерация является биекцией, поскольку в связном графе G все вершины достижимы
из начальных вершин, и поэтому все вершины посещаются агентами, т.е. красят-
ся в красный и желтый цвета. Поскольку алгоритм действия агентов АИ основан
на стратегии обхода графа вглубь, то все ребра графа G являются либо древесны-
ми (принадлежащими красному или желтому дереву и при первом прохождении
красятся в красный или желтый цвета соответственно), либо обратными (и при
единственном прохождении красятся в черный цвет), либо перешейками (которые
красятся при первом прохождении в красный или желтый цвета, но отнести такие
ребра к дереву одного из агентов АИ нельзя, т.к. пронумерованы инцидентные ему
вершины разными агентами АИ). Из описания алгоритма следует, что агенты АИ
проходят все ребра графа G, поскольку при окончании алгоритма все ребра стано-
вятся черными. При выполнении процедуры ВПЕРЕД_А() или ВПЕРЕД_B() АЭ
распознает древесное ребро (v, u) и так нумерует вершину u, что ребру (v, u) одно-
значно соответствует ребро (ϕ(v), ϕ(u)) графа H. Выполняя процедуру РАСП_A()
или РАСП_B(), агент АЭ распознает обратное ребро (v, u) графа G и ставит ему
50
Распознавание конечного графа коллективом агентов
в однозначное соответствие ребро (ϕ(v), ϕ(u)) графа H. При выполнении агента-
ми процедур ФИКС_А(), ВПЕРЕД_АВВ() или ФИКС_В(), ВПЕРЕД_ВАА() АЭ
распознает перешеек(v, u) графа G и ставит ему в однозначное соответствие ребро
(ϕ(v), ϕ(u)) графа H. Следовательно, ϕ является изоморфизмом графа G на граф
H.
Теорема 1. Выполняя алгоритм распознавания, агенты распознают любой граф
G с точностью до изоморфизма.
Подсчитаем временную и емкостную сложность в равномерной шкале [9]. Для
этого рассмотрим свойства красного и желтого путей. Из описания алгоритма сле-
дует, что на каждом шаге алгоритма красный (желтый) путь – это простой путь,
соединяющий начальную вершину v (либо s – в случае агента B) с номером ϕ(v) =
1(ϕ(s) = 2) с вершиной u (z) с номером ϕ(u) =Сч_A (ϕ(z) =Сч_B). Следователь-
но, общая длина красного и желтого пути не превосходит n. Выполняя процеду-
ры ВПЕРЕД_A(v) (ВПЕРЕД_B(s)) и НАЗАД_A(v) (НАЗАД_B(s)) агенты АИ
проходят одно ребро, при выполнении процедуры РАСП_А(v) (РАСП_B(s)) аген-
ты АИ проходят одно обратное ребро и не более n − 2 (изначально одна вершина
уже окрашена в "чужой" цвет) ребер красного (желтого) пути. При выполнении
процедуры РАСП_А(v) (РАСП_B(s)) агенты АИ проходят фактически цикл, со-
стоящий из обратного ребра и некоторого конечного отрезка красного (желтого)
пути, соединяющего вершины инцидентные обратному ребру. Выполняя процедуры
МЕТИМ_АВ(v) (МЕТИМ_ВА(s)) и РАСП_АВВ(v) (РАСП_ВАА(s)) оба агента
АИ проходят один и тот же перешеек, сначала в одном направлении, потом в обрат-
ном. Выполняя процедуры ВПЕРЕД_AR(v) (ВПЕРЕД_BR(s)) и ОТСТУП_A(v)
(ОТСТУП_B(s)) агенты АИ проходят одно красное (желтое) ребро. При выполне-
нии ФИКС_А(v) (ФИКС_B(s)), ОБН_А(v) (ОБН_В(s)) агенты АИ не передвига-
ются, а только делают записи в свой список команд для АЭ, на что так же уходит
один ход.
При подсчете временной сложности алгоритма, будем считать, что инициализа-
ция алгоритма, анализ окрестности O(v) рабочей вершины и выбор одной из воз-
можных процедур занимают некоторое постоянное число единиц времени. Так же
будем считать, что выбор ребра, проход по нему агента АИ и обработка команды АЭ,
полученной на данном этапе от агента АИ, осуществляется за 1 единицу времени.
Тогда временная сложность алгоритма определяется соотношениями: 1) Инициали-
зация выполняется один раз и ее асимптотическая сложность равна O(1); 2) Проце-
дуры ВПЕРЕД_А(v) и ВПЕРЕД_B(s) выполняются не более чем n−1 раз и общее
время их выполнения оценивается как O(n); 3) Общее время выполнения процедур
НАЗАД_А(v) и НАЗАД_B(s) оценивается как O(n); 4) На выполнение процедур
МЕТИМ_А(v) и МЕТИМ_B(s) уходит время, оцениваемое как 2 × O(m), т.е. как
O(n2); 5) Выполнение РАСП_АВВ(v) и РАСП_ВАА(s) занимает время, оценивае-
мое как O(n2); 6) Процедуры ВПЕРЕД_AR(v) и ВПЕРЕД_BR(s) выполняются за
время, оцениваемое как O(n) ×m, т.е. как O(n3); 7) Процедуры ОТСТУП_А(v) и
ОТСТУП_B(s) выполняются за время, оцениваемое как O(n) ×m, т.е. как O(n3);
8) Время, затрачиваемое на ФИКС_А(v) и ФИКС_B(s), оценивается как O(n); 9)
51
И.С. Грунский, А.В. Стёпкин
Время, затрачиваемое на ОБН_А(v) и ОБН_B(s), оценивается как O(n); 10) Вы-
полнение процедур РАСП_А(v) и РАСП_B(s), выполняется за время, которое оце-
нивается как O(n)×m, т.е. как O(n3); 11) Время выполнения СТОИТ_А(v) и СТО-
ИТ_В(s) в общей сложности для всех трёх возможных случаев оценивается как
O(n) + O(n2) = O(n2). Следовательно, суммарная временная сложность T (n) алго-
ритма удовлетворяет соотношению: T (n) = O(n3).
Емкостная сложность S(n) алгоритма определяется сложностью списков VH ,
EH , r(1)...r(t), y(1)...y(p), сложность которых соответственно определяется величи-
нами O(n), O(n2), O(n), O(n). Следовательно: S(n) = O(n2).
Теорема 2. Временная сложность алгоритма распознавания равна O(n3), а
емкостная – O(n2). При этом алгоритм использует 3 краски.
Выводы. В работе предложен алгоритм распознавания графа тремя агента-
ми, два из которых ходят по графу, а третий обрабатывает полученную от них
информацию. Выполняя алгоритм распознавания, они строят граф H, изоморфный
исследуемому. Каждому АИ требуется 2 краски, одна из которых совпадает по цвету
для обоих агентов. Алгоритм останавливается через O(n3) шагов, и требует O(n2)
единиц памяти.
1. Капитонова Ю.В., Летичевский А.А. Математическая теория проектирования вычислитель-
ных систем. – М.: Наука, 1988. – 296с.
2. Кудрявцев В.Б., Алешин С.В., Подкозлин А.С. Введение в теорию автоматов. – М.: Наука,
1985. – 320с.
3. Kuipers B. The spatial semantic hierarchy // Artificial Intelligence. – 2000. – V.119, №1. – 2. –
P.191-233.
4. Dudek G, Jenkin M. Computational principles of mobile robotics. – Cambridge Univ. press, Cambrid-
ge, 2000. – 280p.
5. Калибарда Г., Кудрявцев В.Б., Ущумлич Ш. Независимые системы автоматов в лабиринтах
// Дискретная математика. – 2003. – Т.15, вып.2. – С.3-39.
6. Fraigniaud P., Jecincas D., Peer G., Pelc A., Peleg D. Graph Exploration by a finite automaton
// proc. 29 th Internac. Symp. On Math. Foundation of Computer Science (MFCS), LNCS 3153. –
2004. – Р.451-462.
7. Грунский И.С., Татаринов Е.А. Распознавание конечного графа блуждающим по нему аген-
том // Вестник ДонНУ, сер. А естествен. науки 2009, вып.1. – С.492-497
8. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. –
М.: Мир, 1979. – 536с.
9. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2001.
– 960с.
10. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и при-
менение. – СПБ.: БХВ – Петербург, 2003. – 1104с.
Ин-т прикл. математики и механики НАН Украины, Донецк
Славянский гос. пед. ун-т
stepkin.andrey@rambler.ru
Получено 11.11.09
52
титул
Научное издание
Том 19
содержание
Том 19
Донецк, 2009
Основан в 1997г.
|