А В Стёпкин - Алгоритм распознавания графов тремя агентами - страница 1

Страницы:
1  2  3  4 

ВІСНИК ДОНЕЦЬКОГО НАЦІОНАЛЬНОГО УНІВЕРСИТЕТУ, Сер. А: Природничі науки, 2011, № 1

УДК 519.7

АЛГОРИТМ РАСПОЗНАВАНИЯ ГРАФОВ ТРЕМЯ АГЕНТАМИ

А. В. Стёпкин

Славянский государственный педагогический университет, г. Славянск

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

Ключевые слова: распознавание графа, обход графа, агенты.

Введение. Важной и актуальной проблемой компьютерной науки является проблема взаимодейст­вия управляющей и управляемой систем [1]. Ранее подобное взаимодействие было рассмотрено в [2], в предположении, что оно представлено передвижением одного агента-исследователя (АИ) по неизвест­ному графу и обменом данными с агентом-экспериментатором (АЭ), который и производил восстанов­ление графа по данным, полученным от АИ.

Целенаправленное перемещение агента в операционной среде (ОС) невозможно, пока не будет сформирована достаточно полная её модель. В вопросе моделирования ОС определен ряд подходов, од­ним из которых является топологический [3], при котором агенту доступна информация о связях между различными областями среды и недоступна метрическая и алгоритмическая информация о среде. Зачас­тую подобная ситуация возникает в роботике [4]. Топологическая модель представляет собой граф, ос­нащенный дополнительной информацией на ребрах, в вершинах и инциденторах.

Данная работа посвящена решению задачи, в предположении, что взаимодействие управляющей и управляемой систем представляется процессом перемещения двух АИ по неизвестной среде, заданной конечным графом [5]. А суть взаимодействия заключается в обмене данными АИ с АЭ, на основе кото­рого возможно восстановление графа.

Основные определения и обозначения. Требуется разработать такой алгоритм функционирова­ния АИ и АЭ, что АИ, будучи помещены в произвольные, но не совпадающие вершины произвольного неизвестного агентам-исследователям и агенту-экспериментатору графа G, все элементы которого ок­рашены цветом w, через конечное число шагов обойдут его, передавая АЭ информацию. АЭ, в свою очередь, используя эту информацию, через конечное число шагов восстановит граф H , изоморфный G , то есть распознает G .

В работе рассматриваются конечные, неориентированные графы без петель и кратных ребер. Все неопределяемые понятия общеизвестны, с ними можно ознакомиться, например, в [6-8]. Пусть G = (V, E) - граф, у которого V - множество вершин, E - множество ребер (то есть множество двух­элементных подмножеств (u, v), где u, v є V). Тройку ((u, v), v) будем называть инцидентором («точ­кой прикосновения») ребра (u, v) и вершины v. Множество таких троек обозначим I. Множество L = V j E j I назовем множеством элементов графа G . Функцией раскраски графа G назовем ото­бражение ц : L {w, r,y,b} , где w интерпретируется как белый цвет (краска), r - красный, y - жел­тый, b - черный. Пару (G,/i) называют раскрашенным графом. Последовательность uj,u2,...по­парно смежных вершин называют путем в графе G, а k - длиной пути. При условии u1 = путь назы­вают циклом. Окрестностью 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 . Таким образом, изоморфные графы равны с точностью до обозначения вершин и раскраски их элементов.

Мобильные агенты A и B передвигаются по графу из вершины v в вершину u по ребру (v, u), могут изменять окраску вершин v, u, ребра (v, u), инциденторов ((v, u), v), ((v, u), u). Находясь в вер­

© шине v, агенты воспринимают метки всех элементов окрестности O(v) и на их основании определяют по какому ребру (v, u ) они будут перемещаться и как будут перекрашивать элементы v, u,(v, u), ((v, u), v), ((v, u), u). АЭ передает, принимает и идентифицирует сообщения АИ, обладает ко­нечной, неограниченно растущей внутренней памятью, в которой фиксируется результат функциониро­вания АИ на каждом шаге, и, кроме того, постепенно выстраивается представление графа G (изначально неизвестного агентам) списками ребер и вершин.

Отметим, что работа алгоритма осуществляется следующим образом: АИ помещаются в различ­ные вершины графа G , эти вершины сразу окрашиваются в красный и желтый цвета для агентов A и B соответственно. АИ передвигаются одновременно, пошагово передавая АЭ информацию, АЭ в свою очередь обрабатывает полученные от них данные.

Стратегия решения задачи. Рассматриваемый алгоритм основан на стратегии поиска в глубину. Эта стратегия такова: агенты идут «в глубину», пока это возможно, возвращаются назад, ищут другой путь с еще не посещенными вершинами и не пройденными ребрами. В случае обнаружения смежной вершины, окрашенной в «чужой» цвет, агент метит все перешейки из текущей вершины в чужую область и сообщает второму АИ, через агента-экспериментатора, о необходимости распознавания помеченных перешейков. Пока второй АИ распознает перешейки, первый АИ не может метить новые перешейки. В случае отсутствия других возможных вариантов перемещения, кроме как пометить новый перешеек, первый АИ останавливается до того момента, пока второй АИ не распознает все помеченные перешейки.

Предлагаемая стратегия обладает рядом особенностей: 1) Граф G агентам не известен. 2) При об­ходе графа G , агенты создают неявную нумерацию пройденных вершин: при первом посещении верши­ны она окрашивается агентом A в красный цвет (в желтый цвет в случае агента B ) и ей фактически ста­вится в соответствие номер, равный значению переменной Сч _ А для агента A (Сч _ B для агента B).

Отметим, что Сч _ А и Сч _ B принимают соответственно нечетные и четные значения. На основе ну­мерации и происходит восстановление графа путем построения графа H изоморфного G . В процессе обхода агенты строят неявные деревья поиска в глубину. Относительно этих деревьев все ребра разде­ляются на древесные (окрашиваются при первом прохождении по ним красным либо желтым цветом), обратные (не принадлежат дереву и окрашиваются при первом прохождении в черный цвет) и ребра пе­решейки (соединяют деревья, построенные разными агентами). Древесные ребра проходятся как мини­мум 2 раза и при последнем проходе окрашиваются агентами в черный цвет. Обратные ребра проходятся один раз. А вот ребра перешейки проходятся каждым агентом по два раза: первый прошедший по нему агент метит перешеек, окрашивая его в красный цвет в случае агента A (в желтый цвет в случае агента B ), второй прошедший по нему агент распознает перешеек и красит его в черный цвет.

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

Обход графа. В работе АИ можно выделить 5 режимов:

1) Обычный режим. АИ движется вперед по белым вершинам, окрашивая вершины, соединяющие их ребра и дальние инциденторы в «свой» цвет. Если нет возможных путей перемещения, то АИ возвра­щается назад, окрашивая пройденные вершины, ребра и ближние инциденторы в черный цвет. Вернув­шись в начальную вершину, АИ завершает работу. На каждом шаге АИ обменивается данными с АЭ.

2) Распознавание обратных ребер. Если при движении вперед было обнаружено обратное ребро, то агент прекращает работу в обычном режиме. АИ переходит по обратному ребру, окрашивая его в черный цвет, и по своему пути возвращается в вершину, в которой сменил режим работы. Достигнув этой верши­ны, агент переключается в обычный режим работы. На каждом шаге АИ обменивается данными с АЭ.

3) Пометка перешейков. Если в процессе обхода графа был обнаружен перешеек, то при условии, что все ранее помеченные данным АИ перешейки были распознаны, агент переключается в режим по­метки перешейков. В этом режиме АИ переходит по перешейку в чужую область, окрашивая ребро и дальний инцидентор в «свой» цвет. На следующем шаге возвращается по этому перешейку, ничего не окрашивая, и ищет другие перешейки из этой вершины. Пометив все перешейки, АИ сообщает об этом АЭ, который в свою очередь, дает команду второму АИ о необходимости распознавания помеченных перешейков. По завершению режима пометки перешейков АЭ содержит информацию о количестве по­меченных перешейков.

4) Распознавание перешейков. Получив от АЭ команду о необходимости распознавания перешей­ков, АИ переключается в режим распознавания перешейков. Если в этот момент агент работает в режиме распознавания обратного ребра, то АИ переключится в режим распознавания перешейков, лишь по за­вершению распознавания обратного ребра. В этом режиме АИ возвращается назад по своему пути до обнаружения ближайшей вершины, инцидентной помеченному перешейку. Под помеченным перешей­ком понимается ребро, у которого ближний инцидентор, ребро и дальняя вершина этого ребра окрашены в «чужой» цвет. Далее возможны два случая: Помечено один перешеек. АИ переходит по нему в чужую область, окрашивая перешеек в «свой» цвет, а дальний инцидентор в черный. На следующем шаге воз­вращается по этому перешейку в свою область, окрашивая дальний инцидентор и перешеек в черный цвет. Далее движется вперед по своему пути, пока не вернется в вершину, в которой было произведено переключение в режим распознавания перешейков. Помечено не менее двух перешейков. АИ переходит по первому найденному помеченному перешейку в чужую область, окрашивая его в «свой» цвет, а даль­ний инцидентор в черный. На следующем шаге АИ возвращается по этому перешейку в свою область, окрашивая его в черный цвет, а оба инцидентора в красный. Далее АИ движется назад по своему пути, пока не будет найден следующий помеченный перешеек. Далее возможно два варианта.

4.1. Следующий помеченный перешеек не последний. АИ переходит по найденному перешейку, ок­рашивая его в «свой» цвет, а дальний инцидентор в черный. На следующем шаге АИ возвращается по этому перешейку в свою область, окрашивая его и оба инцидентора в черный цвет. И снова возвращается назад по своему пути до следующего помеченного перешейка.

4.2. Следующий помеченный перешеек последний. АИ переходит по найденному перешейку, окра­шивая его в «свой» цвет, а дальний инцидентор в черный. На следующем шаге АИ возвращается по это­му перешейку в свою область, окрашивая его в черный цвет, а оба инцидентора в красный.

АИ переходит по последнему перешейку в чужую область, окрашивая инциденторы в черный цвет. На следующем шаге АИ переходит по первому распознанному перешейку в свою область, окраши­вая инциденторы в черный цвет. Далее АИ возвращается в вершину, в которой было произведено пере­ключение в режим распознания перешейков.

5) Одновременное попадание двух АИ в одну белую вершину. При одновременном попадании двух АИ в одну белую вершину, каждый АИ окрашивает вершину наполовину, и она становится красно-желтой. Агент B на следующем шаге отступает назад по своему пути и переходит в режим пометки пе­решейков (при этом ребро, по которому он вернулся уже посчитано как первый перешеек, а длина жел­того пути уменьшена на одну вершину). Агент A видит разноцветную вершину как свою, но при распо­знавании окрашивает в черный цвет обе половинки.

Алгоритмы обхода и восстановления. Опишем подробно алгоритмы, реализующие описанную выше стратегию. Процесс распознавания состоит из двух принципиально разных типов алгоритмов: «Обход» и «Восстановление». Первый тип алгоритма описывает обход неизвестного графа G агентами-исследователями, с целью проведения серии элементарных экспериментов и передачи информации АЭ. Второй тип алгоритма представляет собой анализ результатов элементарных экспериментов и их объе­динение, в результате которого будет построен граф H , изоморфный распознаваемому графу G .

Рассмотрим непосредственно сами алгоритмы.

Алгоритм работы агента A:

Вход: граф G неизвестный АИ и АЭ, все элементы графа G окрашены краской w, агент A по­мещен в произвольную вершину v .

Выход: все элементы графа G, которые попадут в область работы агента A, окрашены краской b, агент A находится в исходной вершине v ; пошагово выданы команды АЭ.

Данные: v - рабочая вершина графа G , в которой находится агент.

Алгоритм:

1. Агент A красит (p(v) := r);

2. Запрос AN;

3. if AN ф 1 then do

4. Запрос BN;

5. ifBN = 0 then МЕТИМ ПЕР А

6. else ВЫБОР_ХОДА_А(УХ

7. end do;

8. else РАСП_ПЕР_А(у);

Все, процедуры, которые не описаны ниже, представлены в [9]. РАСП_ПЕР_А (v):

1. Z := K ;

2. if в O(v) нет ребра, у которого (jd(y,u) = y) then do

3. Агент A выполняет ОТСТУП_А(у\

4. go to 2 данной процедуры;

5. end do;

6. else do

7.   if (((K = Z)or(K = \))and(Z ф l)) then агент A выполняет РАСП_АВВ(у);

8. else агент A выполняет процедуру РАСП_АВВЪ{у),

9. Агент A запрашивает у АЭ значение переменной K ;

Страницы:
1  2  3  4 


Похожие статьи

А В Стёпкин - Алгоритм распознавания графов тремя агентами

А В Стёпкин - Распознавание конечного графа коллективом агентов