Українська English

Содержание

Введение

В настоящее время в мире существует огромное количество различного рода сред, требующих изучения (начиная с исследования среды при помощи наноботов и заканчивая исследованием поверхностей отдаленных планет с помощью планетоходов). Это является одной из причин активного развития такого направления математической кибернетики, как теория дискретных динамических систем. Исследование среды – это своего рода дискретная система, представленная как модель взаимодействия управляющей и управляемой систем (управляющего автомата и операционной среды), взаимодействие которых зачастую представляется как процесс перемещения управляющего автомата по графу управляемой системы.

Когда о графе ничего неизвестно, то задачу можно сравнить с обходом лабиринта человеком или устройством, находящимся внутри него и не имеющим плана лабиринта. Дуге графа соответствует коридор лабиринта, а вершине – перекресток. Находясь на перекрестке, мы видим исходящие из него коридоры, но мы не знаем, куда ведет тот или иной коридор, до тех пор, пока не прошли по нему до следующего перекрестка. Для выполнения нашей задачи мы, во-первых, имеем некоторую внутреннюю память (блокнот в руках человека), куда можем записывать полученную информацию о пройденной части лабиринта, и, во-вторых, делать пометки в пройденных перекрестках и коридорах. Ориентированному графу соответствует лабиринт, в котором все коридоры «с односторонним движением». Если внутренняя память ограничена конечным числом состояний, мы имеем робот (конечный автомат) на графе как разновидность машины Тьюринга [1].

1. Актуальность темы.

В сфере информационных технологий задачу исследования графа можно применить к верификации и тестированию программных и аппаратных систем, а также исследованию сетей, в том числе сетей интернета и GRID на основе формальных моделей. Модель системы или сети, в конечном счёте, сводится к графу переходов, свойства которого нужно исследовать. За последние годы размер реально используемых систем и сетей и, следовательно, размер их моделей и, следовательно, размер исследуемых графов непрерывно растёт. Проблемы возникают тогда, когда исследование графа одним автоматом (компьютером) либо требует недопустимо большого времени, либо граф не помещается в памяти одного компьютера, либо и то и другое. Поэтому возникает задача параллельного и распределённого исследования графов. Эта задача формализуется как задача исследования графа коллективом автоматов (несколькими параллельно работающими компьютерами с достаточной суммарной памятью) [2].

В данной магистерской работе проводится анализ и разработка алгоритма исследования графа несколькими агентами с целью минимизации его емкостной и временной сложности.

Под емкостной сложностью понимается количество используемой алгоритмом памяти, а под временной количество перемещений агентов по дугам графа.

2. Цель и задачи исследования, планируемые результаты

Целью исследования является разработка алгоритма исследования графа коллективом агентов с меньшим показателем временной сложности или c меньшим использованием памяти чем у уже существующих алгоритмов

Основные задачи исследования:

  1. Изучить основные понятия и обозначения теории графов.
  2. Проанализировать способы уменьшения сложности алгоритма.
  3. Изучить методы восстановления графа.
  4. Разработка усовершенствованного метода распознавания графа.

3. Основные определения

Для лучшего понимания рассматриваемой предметной области, рассмотрим основные ее понятия.

Теория графов – раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств. G=(V, E), где V есть подмножество любого счётного множества, а E – подмножество VxV.

Инцидентор – место соединения вершины и ребра (обычно используются парой – инцидентор от начальной вершины и инцидентор у конечной вершины).
Пример графа

Рисунок 1 – Пример графа с пятью вершинами и шестью ребрами

Матрица инцидентности – одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки – вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность). В случае ориентированного графа каждой дуге ставится в соответствие "-1" в строке вершины x и столбце дуги и "1" в строке вершины y и столбце дуги ; если связи между вершиной и ребром нет, то в соответствующую ячейку ставится "0".

Инцидентор – место соединения вершины и ребра.

Коллектив агентов – совокупность агентов, исследующих граф.

Агент исследователь – агент, который ходит по среде и размечает вершины, одновременно передавая информацию агенту-экспериментатору.

Агент экспериментатор – агент, который восстанавливает граф по данным, переданным агентами исследователями.

Поиск в глубину – один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра.

Порядок прохождения вершин графа в глубину

Рисунок 2 – Порядок прохождения вершин графа в глубину
(анимация: 10 кадров, 10 повторений, 7 килобайт)

Изоморфизм графа. В теории графов изоморфизмом графов G=(VG,EG) и H=(VH,EH) называется биекция между множествами вершин графов f: VG→VH такая, что любые две вершины u и v графа G смежны тогда и только тогда, когда вершины f(u) и f(v) смежны в графе H. Здесь графы понимаются неориентированными и не имеющими весов вершин и ребер. В случае, если понятие изоморфизма применяется к ориентированным или взвешенным графам, накладываются дополнительные ограничения на сохранение ориентации дуг и значений весов. Если изоморфизм графов установлен, они называются изоморфными и обозначаются как G≈H.

Пример изоморфных графов

Рисунок 3 – Пример изоморфных графов

Перешеек – вершина, в которой встречаются агенты исследователи.

Матрица смежности – это квадратная матрица A размера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину.

Петля – ребро, начало и конец которого находятся в одной и той же вершине.

Висячая вершина – вершина называется висячей если имеет степень единица [10].

4.Обзор исследований и разработок по теме

4.1 Обзор международных источников

Проблема исследования графа конечным роботом была поставлена М.О. Рабином еще в далеком 1967 г.

В 1978 г. К. Кобаяши представил статью с описанием останавливающегося алгоритма обхода экспоненциальной сложности, основанного на идее DFS [11]. В 1988 г. С. Куттен [12] предложил алгоритм обхода минимальной сложности O(nm), но его робот не был конечным, так как использовал ячейки графа с логарифмическим (от числа вершин) количеством битов памяти. В 1993 г. Y.Afek и E.Gafni [13] предложили конечный робот A (который они назвали Traversal-3), основанный на поиске в глубину (DFS), с оценкой длины обхода O(nm+n2 logn). Согласно их методу метка ставится на всех 4 вершинах out-пути, кроме его конца, и определяется четность числа помеченных вершин. На следующем проходе удаляются метки с вершин противоположной четности и заново определяется четность числа оставшихся помеченными вершин, и так далее до тех пор, пока не останется одна помеченная вершина – предпоследняя вершина out-пути. За счет этого «метода четности» вместо O(n) проходов достаточным оказывается O(logn) проходов.

4.2 Обзор национальных источников

Проблемой исследования графа занимаются в своих работах занимаются И. Бурдонов, А. Косачев. Внимание они уделяют исследованию ориентированных графов автоматами [1-5]. В их работах часто говорится о применении исследования графов автоматами в тестировании систем. Так они сравнивают саму тестируемую систему с графом, а автоматы в ней при переходах по дугам оказывают тестовое воздействие на нее.

4.3 Обзор локальных источников

В работах Грунского И.С., Стёпкина А.В., Татаринова Е.А. рассматриваются методы распознавания графа как одним агентом так и коллективом агентов [6-9].

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

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

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

Агенты распознают древесные ребра при первом посещении. Древесные пути удлиняются при переходе в новую вершину и укорачиваются при переходе назад. Вершина у которой все инцидентные ребра распознаны красится в черный. Когда в графе не остается окрашенных не в черный цвет вершин, алгоритм заканчивает свою работу.

Процесс распознавания графа состоит из двух разных алгоритмов: обход (был описан выше) и восстановление. Второй алгоритм выполняется агентом-экспериментатором и в результате получает граф изоморфный заданному. Стоит отметить что алгоритмы работаю следующим образом: сначала ходит первый агент, АЭ записывает его действия, затем ходит второй агент и АЭ записывает его действия [6].

Выводы

В настоящее время одним из центральных направлений кибернетики является распознавание неизвестной среды, заданной графом. Данная работа посвящена решению проблемы распознавания несколькими агентами среды, заданной конечным неориентированным графом.

В ходе работы были проанализированы особенности предметной области. Был проанализирован метод распознавания конечного графа двумя агентами, предложенный А.В. Стёпкиным.

Временная сложность данного алгоритма распознавания равна O (n), емкостная – O n2 , а коммуникационная – O n2 * log(n) . При этом алгоритм использует 3 краски.

Список источников

  1. Бурдонов И.Б. Обход неизвестного ориентированного графа конечным роботом / И.Б. Бурдонов // Программирование, 2004 г., № 4, с. 11-34.
  2. Бурдонов И.Б., Косачев А.С. Обход неизвестного графа коллективом автоматов / И.Б. Бурдонов, А.С. Косачев // Труды Института системного программирования РАН, том 26, вып. 2, 2014, стр. 43-86.
  3. Бурдонов И.Б. Проблема отката по дереву при обходе неизвестного ориентированного графа конечным роботом / И.Б. Бурдонов, А.С. Косачев // Программирование, 2004 г., № 6, с. 6-29.
  4. Бурдонов И.Б., Косачев А.С., Кулямин В.В. Неизбыточные алгоритмы обхода ориентированных графов. Недетерминированный случай / И.Б. Бурдонов, А.С. Косачев, В.В. Кулямин // Программирование, 2004 г., №1, с. 2-17.
  5. Бурдонов И.Б., Косачев А.С., Кулямин В.В. Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай / И.Б. Бурдонов, А.С. Косачев, В.В. Кулямин // Программирование, 2003 г., №5, с. 59-69.
  6. Грунский И.С., Стёпкин А.В. Распознавание конечного графа коллективом агентов. – Труды ИПММ НАН Украины. – 2009. – Т.19. – С. 43–52.
  7. Стёпкин А.В. Распознавание графов коллективом агентов / А.В. Стёпкин // Мат. IV мiжнар. наук.-практ. конф. Сучасна iнформацiйна Україна: iнформатика, економiка, фiлософiя 2010, Донецьк, – т.1 – С. 139–143.
  8. Грунский И.С., Татаринов Е.А. Алгоритм распознавания графов / И.С. Грунский, Е.А. Татаринов // Тр. 4 междунар. Конф. Параллельные вычисления и задачи управления PACO’2008, Москва, Ин-т Проблем Управления им. В.А. Трапезникова РАН, 2008 – С. 1483–1498.
  9. Грунский И.С. Распознавание конечного графа блуждающим по нему агентом / И.С. Грунский, Е.А. Татаринов // Вестник Донецкого университета. Сер. А. Естественные науки. – 2009. – № 1. – С. 492–497.
  10. Материал из свободной электронной библиотеки Википедия: словарь теории графов. Электронный ресурс. Режим доступа: http://ru.wikipedia.org/wiki/Глоссарий_теории_графов
  11. Kobayashi K. The firing squad synchronization problem for a class of polyautomata networks / K. Kobayashi // Journal of Computer and System Science, 17:300-318, 1978.
  12. Kutten S. Stepwise construction of an efficient distributed traversing algorithm for general strongly connected directed networks / S. Kutten // In J. Raviv, editor, Proceedings of the Ninth Internationak Conference on Computer Communication, pages 446-452, October 1988.
  13. Afek Y., Gafni E., Distributed Algorithms for Unidirectional Networks / Y. Afek, E. Gafni // SIAM J. Comput., Vol. 23, No. 6, 1994, pp. 1152-1178.