Русский   English
ДонНТУ   Портал магістрів

Реферат за темою випускної роботи

Зміст

Вступ

У науково - дослідній роботі студента розглядається тематика, пов'язана з автоматним аналізом геометричних середовищ, графів, та інших дискретних структур.

Одним із завдань даної тематики, є завдання опису структури об'єкта на основі інформації отриманої при обході графа по його кордону. Подібні завдання виникають у робототехніці, молекулярній фізиці: побудова моделі карти середовища, моделі об'єкта.

Відомий ряд робіт присвячених задачі розпізнавання структури об'єкта, в яких розглядався випадок вирішення подібних завдань з використанням одного автомата. У цій роботі пропонується алгоритм вирішення задачі розпізнавання з використанням двох агентів. В якості моделі об'єкта використовується неорієнтовані граф. Одним із завдань даної тематики, є завдання виходу на кордон графа мозаїчної структури з урахуванням перебування в ньому дірок.

1. Актуальність теми

Тема стала актуальною ще в 50-х роках минулого століття, коли почали з'являтися перші статті Шеннона К., в якій фактично розглядалася завдання пошуку автоматом - мишею певної мети в лабіринті, що значною мірою визначило тематику направлення на наступні роки. Через 60 років, тема залишається актуальною і дуже часто використовується в створенні ігор, програм та інших продуктів.

2. Мета і завдання дослідження, плановані результати

Метою випускної роботи магістра є розробка нового алгоритму відновлення графа мозаїчної структури, в якому можуть бути присутніми діри. Потрібно розробити такі алгоритми пересування агента АД по вхідному графу G з передачею інформації про це, і відновлення графа агентом АЕ за отриманими даними у вигляді формули, що АД за кінцеве число кроків незалежно від початкового розміщення обійде частину внутрішніх вершин G і всі граничні вершини, крок за кроком передаючи інформацію, за якою АЕ через кінцеве число кроків опише граф P, ізоморфний вихідного графу G.

Основні завдання дослідження.

  1. Розробка алгоритму для АД і АЕ, для обходу і розпізнавання графа.
  2. Створення програми для реалізації цих алгоритмів.

Об'єкт дослідження: автоматний аналіз графів.

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

У рамках магістерської роботи планується отримання нових наукових результатів за наступними напрямками.

  1. Розробка ефективного алгоритму для виходу на кордон графа з урахуванням містяться в ньому дірок.
  2. Розробка ефективного алгоритму для обходу графа по кордону.
  3. Розробка ефективного алгоритму для знаходження та опису всіх дір присутніх у графі.
  4. Розробка ефективного алгоритму для відновлення графа.
  5. Визначення областей застосування для даного алгоритму.
  6. Створення програми для обходу графа.

3. Основні визначення

3.1 Плоскі графи


У багатьох випадках не має значення, як зобразити граф, оскільки ізоморфні графи несуть одну і ту ж інформацію. Однак зустрічаються ситуації, коли важливо з'ясувати, чи можливо намалювати граф на площині гак, щоб його зображення задовольняло певним вимогам. Наприклад, в радіоелектроніці при виготовленні мікросхем друкованим способом електричні ланцюги наносяться на плоску поверхню ізоляційного матеріалу. А так як провідники не ізольовані, то вони неповинні перетинатися. Аналогічна задача виникає при проектуванні залізничних та інших шляхів, де небажані переїзди.

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

Прикладами плоских графів є прості цикли, дерева, ліс.

В якості характеристики плоского представлення графа вводиться поняття грані. Гранню в плоскому поданні графа 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 загального алгоритму.

4.1 Огляд національних джерел


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

Існує, кілька великих статей.

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

Принцип роботи АД(вихід на кордон графу з врахуванням дір)


Рисунок 6 - Принцип роботи АД(вихід на кордон графу з врахуванням дір)

4.2 Огляд локальних джерел


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

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

Розпізнавання графа

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

Перший алгоритм "Обхід" описує переміщення АД по невідомому графу G і генерацію інформації для АЕ.

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

Алгоритм "Обхід" роботи АД.

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

На першому етапі, якщо необхідно АД виходить на кордон, а на другому етапі АД обходить граф проти годинникової стрілки по граничним ребрам до тих пір, поки не повернеться в вершину виходу на кордон.

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

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

Лемма 1. Якщо в мозаїчному графі n вершин, то максимальний шлях по внутрішнім вершин графа в обраному напрямку не перевершує величини l=(n-1)/3.

Лемма 2. Будь маршрут по внутрішніх вершин графа в обраному напрямку переміщення є незамкнутим. Вихідний граф G може мати більш складну структуру, ніж базова структура, для якої виконується наступне.

Лемма 3. Довжина маршруту p по граничним вершин G При підрахунку тимчасової складності має місце: для виходу на кордон графа згідно лемі 1 йде час (n-1)/3, тобто О(n); згідно лемі 3 обхід по межі не перевершує величини 2n, значить оцінюється як О(n) кроків. Ємнісна складність Е(n) відсутня, тому що агенту нічого не потрібно зберігати.

Алгоритм "Відновлення" роботи АЕ.

В алгоритмі аналізується рядок напрямків, з генерованих і переданих АД. Спочатку проводиться пошук точок перегину. Якщо точки є, то визначається ідентифікатор зворотного базової структури, що містить чергову точку перегину, в якості другої вершини маршруту. Виробляється перетворення рядка, нарощування лічильників внутрішніх Сч_вв і граничних Сч_гв вершин, приєднання даної структури до графа, що фіксується додаванням в формулу зі знаком - відповідного фрагмента. Якщо немає таких точок, то знову проглядається спочатку рядок для пошуку ідентифікаторів базових структур. Кожен раз, коли перебуває такий ідентифікатор, проводиться видалення з рядка відповідної підрядка, зменшення значення Сч_вв і Сч_гв, відділення даної структури від графа, і додавання в формулу зі знаком + відповідного фрагмента. В алгоритмі розпізнавання здійснюється два перегляди вхідного рядка. Якщо є хоча б одна точка перегину, то в граф додаються відповідне базової структурі кількість вершин і встановлюється неявна нумерація 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/Граф_(математика)