Українська   English
ДонНТУ   Портал магистров

Реферат по теме выпускной работы

Содержание

Введение

В научно-исследовательской работе студента рассматривается тематика, связанная с автоматным анализом геометрических сред, графов, и других дискретных структур.

Одной из задач данной тематики, является задача описания структуры объекта, на основе информации полученной при обходе графа по его границе. Подобные задачи возникают в робототехнике, молекулярной физике: построение модели карты среды, модели объекта.

Известен ряд работ посвященных задаче распознавания структуры объекта, в которых рассматривался случай решения подобных задач с использованием одного автомата. В настоящей работе предлагается алгоритм решения задачи распознавания с использованием двух агентов. В качестве модели объекта используется неориентированный граф. Одной из задач данной тематики, является задача выхода на границу графа мозаичной структуры с учётом нахождения в нём дыр.

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

Тема стала актуальной ещё в 50-х годах прошлого века, когда начали появляться первые статьи Шеннона К., в которой фактически рассматривалась задача поиска автоматом-мышью определенной цели в лабиринте, что в значительной мере определило тематику направления на последующие годы. Спустя 60 лет, тема остаётся актуальной и очень часто используется в создании игр, программ и других продуктов.

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

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

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

  1. Разработка алгоритмов для АИ и АЭ, для обхода и распознавания графа.
  2. Создание программы для реализации этих алгоритмов.

Объект исследования: автоматный анализ графов.

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

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

  1. Разработка эффективного алгоритма для выхода на границу графа с учётом содержащихся в нём дыр.
  2. Разработка эффективного алгоритма для обхода графа по границе.
  3. Разработка эффективного алгоритма для нахождения и описания всех дыр присутствующих в графе.
  4. Разработка эффективного алгоритма для восстановления графа.
  5. Определение областей применения для данного алгоритма.
  6. Создание программы для обхода графа.

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

3.1 Плоские графы

Во многих случаях не имеет значения, как изобразить граф, поскольку изоморфные графы несут одну и ту же информацию. Однако встречаются ситуации, когда важно выяснить, возможно ли нарисовать граф на плоскости гак, чтобы его изображение удовлетворяло определенным требованиям. Например, в радиоэлектронике при изготовлении микросхем печатным способом электрические цепи наносятся на плоскую поверхность изоляционного материала. А так как проводники не изолированы, то они нe должны пересекаться. Аналогичная задача возникает при проектировании железнодорожных и других путей, где нежелательны переезды.

Плоским графом называется граф, который можно начертить на плоскости таким образом, чтобы его ребра не имели точек пересечения, отличных от вершин.

Примерами плоских графов являются простые циклы, деревья, лес.

В качестве характеристики плоского представления графа вводится понятие грани. Гранью в плоском представлении графа G называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов. В качестве грани можно рассматривать и часть плоскости, расположенную «вне» плоского представления графа; она ограничена «изнутри» простым циклом и не содержит в себе других циклов. Эту часть плоскости называют «бесконечной» гранью. Примеры плоских графов даны на рисунке 1.

Пример бесконечного плоского графа

Рисунок 1 – Пример плоского графа

На рисунке 2 изображен пример бесконечного плоского графа.

Пример бесконечного плоского графа

Рисунок 2 – Пример бесконечного плоского графа

3.2 Мозаики


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

Бесконечный плоский граф называется мозаикой, если индекс его вершины конечен, и он не имеет бесконечных граней. Можно показать, что существует только три вида мозаик, других правильных мозаик нет.

  1. Мозаика на основе треугольников.
  2. Мозаика на основе прямоугольников.
  3. Мозаика на основе шестиугольников.

На рисунке 3, рисунке 4 и рисунке 5 представлены виды простых мозаик.

Двойственным бесконечным графом к мозаике на основе треугольников является мозаика на основе шестиугольников и наоборот. Двойственным бесконечным графом к мозаике на основе прямоугольников является сама эта мозаика.

Правильная мозаика на основе прямоугольника

Рисунок 3 – Правильная мозаика на основе прямоугольника

Правильная мозаика на основе треугольника

Рисунок 4 – Правильная мозаика на основе треугольника

Правильная мозаика на основе шестиугольника

Рисунок 5 – Правильная мозаика на основе шестиугольника

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

Одним из шагов при решении задачи восстановления графа мозаичной структуры с дырами является выход на границу графа с учётом возможности нахождения на пути дыр. В процессе выполнения научно-исследовательской работы был разработан алгоритм выхода агента на вершину графа мозаичной структуры с дырами.

Алгоритм выхода агента на границу графа.

После постановки агента на произвольную вершину графа ему необходимо выйти на границу графа.

  1. Агент помещается случайным образом в произвольную вершину графа v.
  2. Агент проверяет степень вершины, на которую попал.
  3. Если степень вершины, на которую попал агент меньше пяти, то это граничная вершина. Алгоритм заканчивает работу.
  4. Агент проверяет степени вершин смежных с текущей вершиной.
  5. Если хотя бы у одной из смежных вершин степень меньше пяти, то рассматриваемая вершина является граничной и переходим на неё. Алгоритм заканчивает работу.
  6. Если степень текущей вершины равна шести или пяти и присутствует диаметрально противоположное ребро относительно первого встречного ребра, то переходим на следующую вершину. Дальнейший анализ производится, начиная с пункта 2.
  7. Если диаметрально противоположное ребро отсутствует, то это дырка и выполняется алгоритм обхода дырки.
  8. Действия повторяются, пока агент не выйдет на границу.

Алгоритм обхода дырки.

  1. Относительно диаметрально противоположного ребра один поворот почасовой стрелке и переход на следующую вершину.
  2. Относительно ребра, по которому перешли на данную вершину два поворота по часовой стрелке и переход на следующую вершину по текущему ребру.
  3. Относительно ребра диаметрально противоположного ребру, по которому перешли на текущую вершину два поворота по часовой стрелке и переход на следующую вершину.
  4. По ребру диаметрально противоположному отсутствующему переходим в следующую вершину.
  5. Дальнейший анализ производится, начиная с пункта 2 общего алгоритма.

Принцип работы АИ(выход на границу графа с учётом дыр)


Рисунок 6 - Принцип работы АИ(выход на границу графа с учётом дыр)

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


По тематике теории графов в национальных источниках информация практически отсутствует, но публикуются достаточно часто новые статьи, алгоритмы, наработки и решения.

Существует, несколько больших статей.

  1. Капитонова Ю.В., Летичевский А.А. "Математическая теория проектирования вычислительных систем".
    Излагаются основы математического аппарата и современных методов проектирования систем преобразования информации: аппаратуры вычислительных машин, программ и программных систем, систем управления и обработки данных, основанных на применении средств вычислительной техники.Первая часть посвящена обзору основных математических моделей вычислительных систем. Вторая часть содержит изложение практических методов проектирования различного типа систем — аппаратуры ЭВМ, последовательных и параллельных программ, компонент общесистемной математики.Для математиков и инженеров — разработчиков аппаратных и программных средств, а также для студентов и аспирантов в области информатики и вычислительной техники.
  2. В.Б. Кудрявцев, Ш. Ушчумлич, Г. Килибарда. "О поведении автоматов в лабиринтах".
    Дается обзор более 80-ти работ, выполненных за последние 20 лет, по поведению систем автоматов в лабиринтах. Выделяются основные понятия, проблематика, достижения, методы решения задач и открытые проблемы. Основные утверждения в ряде случаев приводятся в более сильном виде по сравнению с формулировками авторов. Статья содержит также новые результаты по проблеме обхода лабиринтов автоматами.

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


В Донецком национальном техническом университете есть публикация, на тему "Распознавание графа мозаичной структуры коллективом агентов", авторы: Шатохина Н.К., Шатохин П.А.

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

Распознавание графа

Процесс распознавания состоит из двух алгоритмов.

Первый алгоритм "Обход" описывает перемещение АИ по неизвестному графу G и генерацию информации для АЭ.

Второй алгоритм "Восстановление", представляет собой анализ полученной информации, на основании которой создается символьное описание графа Р, изоморфного исходному G.

Алгоритм "Обход" работы АИ.

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

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

Алгоритм АИ выхода на границу. Агент, помещенный в произвольную вершину v, определяет ее степень, если это внутренняя вершина, т.е. deg(v)=6, то перемещается по диаметрально противоположному ребру относительно первого встреченного ребра до следующей вершины. Эту процедуру повторяет до тех пор, пока не найдет граничную вершину, выбирает первое граничное ребро путем поворота против часовой стрелки, которое помечает маркером. Алгоритм обхода графа по граничным вершинам. Дальнейшее перемещение агента происходит по границе графа в направлении против часовой стрелки, начиная из найденной вершины и ребра. Агент перемещается к следующей вершине по выбранному ребру, фиксируя букву-направление своего перемещения.

Далее АИ проверяет, является ли помеченным маркером выбранное ребро. Если оно не помечено, он пересылает букву АЭ и продолжает движение, в противном случае АИ завершает свою работу. Алгоритм "Обход" состоит двух частей. Первая часть может отсутствовать.

Алгоритм "Восстановление" работы АЭ.

В алгоритме анализируется строка направлений, сгенерированная и переданная АИ. Вначале производится поиск точек перегиба. Если точки имеются, то определяется идентификатор обратной базовой структуры, содержащий очередную точку перегиба, в качестве второй вершины маршрута. Производится преобразование строки, наращивание счетчиков внутренних Сч_вв и граничных Сч_гв вершин, присоединение данной структуры к графу, что фиксируется добавлением в формулу со знаком - соответствующего фрагмента. Если нет таких точек, то вновь просматривается сначала строка для поиска идентификаторов базовых структур. Каждый раз, когда находится такой идентификатор, производится удаление из строки соответствующей подстроки, уменьшение значения Сч_вв и Сч_гв, отделение данной структуры от графа, и добавление в формулу со знаком + соответствующего фрагмента. В алгоритме распознавания осуществляется два просмотра исходной строки. Если имеется хотя бы одна точка перегиба, то в граф добавляются соответствующее базовой структуре количество вершин и устанавливается неявная нумерация u: V(G∪G)→V(H∪G), где G' граф включенной части. Нумерация u(v)=Сч_вв или u(v)=Сч_гв, для всех v∈G'. Эта нумерация является биекцией, т.к. добавление базовых структур выполняется взаимно однозначно в соответствии с их идентификаторами. При выполнении операции отделения в графе Н создается неявная нумерация d: V(G')→V(H) вершин графа G в вершины графа Н, тех вершин, которые содержатся в отделяемой базовой структуре. При этом равенство d(v)=t, где t=Сч_вв или t=Сч_гв. Эта нумерация также является биекцией, т.к. удаление базовых структур выполняется взаимно однозначно в соответствии с их идентификаторами.

Тем самым доказана следующая терема.

Теорема 1. Выполняя алгоритмы распознавания, агенты распознают любой граф G с точностью до изоморфизма.

При подсчете временной сложности алгоритма работы АЭ учитывается, что распознавание структуры графа выполняется за счет двукратного просмотра исходной строки, длина которой не может превосходить 2n букв, т.е. временная сложность оценивается следующим образом.

Процесс присоединения базовых структур выполняется не более чем возможное количество точек перегиба, а это не более чем за n/2 шагов. Процесс отсечения базовых структур выполняется не более чем возможное количество углов в графе, т.е. не более, чем за n/2 шагов. Второй просмотр строки выполняется не более чем за 2n шагов. Следовательно, суммарная временная сложность оценивается как Т(n)=О(n).

Таким образом, совместная работа АИ и АЭ оценивается как O(n). Емкостная сложность Е(n) определяется сложностью списков строки направлений S, множества граничных вершин V'⊂V, и строки формул F, сложность которых определяется величинами O(n), O(n), O(n).

Выводы

Проведён анализ существующих алгоритмов восстановления графа мозаичной структуры. Изучены основные определения и понятия.

Магистерская работа посвящена актуальной научной задаче исследования графов мозаичной структуры.

Предложен алгоритм выхода на вершину графа мозаичной структуры с учётом возможности присутствия дыр в нём.

Проведена оценка сложности модифицированного алгоритма.

Примечание

При написании данного реферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2014 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.

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

  1. Шатохина Н.К., Шатохин П.А. Распознавание графа мозаичной структуры коллективом агентов. / Научные работы Донецкого национального технического университета. Серия «Проблемы моделирования и автоматизации проектирования» (МАП-2011). Выпуск: 9 (179) – Донецк, ДонНТУ – 2011. – С. 111–121.
  2. Оре О. Графы и их применение. – М.: «Мир», 1965. – 175 с.
  3. Оре О. Теория графов. – М.: Наука, 1968. – 336 с.
  4. Ерош И.Л., Сергеев М.Б., Соловьев Н.В. Дискретная математика: Учеб. пособие – СПбГУАП. СПб., 2005. – 144 с.
  5. Харари Ф. Теория графов. – М.: «Мир», 1965. – 302 с.
  6. В. Г. Дурнев, М.А. Башкин, О.П. Якимова Элементы дискретной математики. – Яросл. гос. ун-т им. П.Г.–Демидова. – Ярославль: ЯрГУ, 2007. – Часть II. – 173 с.
  7. Д.А. Кларнер Математический цветник. Пер. с англ. Данилова Ю. А. – М.: Мир, 1983. – 484 с.
  8. Ерош И.Л. Дискретная математика. Теория чисел: учеб. пособие / И. Л. Ерош. СПбГУАП. СПб., 2001. – 32 с.
  9. Уилсон Р. Введение в теорию графов. Пер с англ. – М.: Мир, 1977. – 208 с.
  10. Салий В. Н., Богомолов А. М. Алгебраические основы теории дискретных систем. – М.: Физико-математическая литература, 1997.
  11. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. – М.: Наука, 1990. – 384 с.
  12. Капитонова Ю.В., Летичевский А.А. Математическая теория проектирования вычислительных систем / Ю.В. Капитонова, А.А. Летичевский. – М.: Наука, 1998. – 296 с.
  13. Кудрявцев В.Б., Ущумлич Ш. О поведении автоматов в лабиринтах / Дискретная математика. – 1992. – Т.4, Выпуск: 3. – С. 3–28.
  14. Анджанс А.В. Возможности автоматов при обходе плоскости / Проблемы передачи информации. – 1983. – Т.19, Выпуск: 3. – С. 78–89.
  15. Анджанс А.В. О возможностях автоматов при обходе одномерных областей / Латвийский математический ежегодник. Выпуск: 27. – Рига, 1983. – С. 191–201.
  16. Бесконечные графы. [Электронный ресурс]. – Режим доступа: https://sites.google.com/a/labore.ru/teoria-grafov-i-ee-primenenie/vvedenie-v-teoriu/beskonecnye-grafy
  17. Теория графов: основные понятия и определения. [Электронный ресурс]. – Режим доступа: http://mathhelpplanet.com/static.php?p=teoriya-grafov-ponyatiya-i-opredeleniya
  18. Плоские графы. Формула Эйлера. [Электронный ресурс]. – Режим доступа: http://grafielk.narod.ru/HTMLs/theory7.html
  19. Граф (математика). [Электронный ресурс]. – Режим доступа: http://ru.wikipedia.org/wiki/Граф_(математика)