Русский   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 & rarr; VH така, що будь-які дві вершини u і v графа G суміжні тоді і тільки тоді, коли вершини f (u) і f (v) суміжні в графі H. Тут графи розуміються неорієнтованими і не мають ваг вершин і ребер. У разі, якщо поняття ізоморфізму застосовується до орієнтованим або зваженим графам, накладаються додаткові обмеження на збереження орієнтації дуг і значень ваг. Якщо ізоморфізм графів встановлено, вони називаються ізоморфними і позначаються як G & asymp; 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.