Криворучко Дмитрий Владимирович
dvkr@ukr.net

«Разработка программно-аппаратного комплекса для системы дистанционного обучения ВУЗа»
Научный руководитель: доц. каф. АТ Воропаева В.Я.

РОЗРОБКА ППП ДЛЯ ВИКОНАННЯ ЛАБОРАТОРНИХ РОБІТ ПО КУРСУ
"ТЕОРІЯ МЕРЕЖ ТА СИСТЕМ ЗВ'ЯЗКУ"

Криворучко Д.В, ФКИТА, гр. ТКС - 99н

Научный руководитель доц. Воропаева В.Я.

Донецький національний технічний університет

Статья опубликована в сборнике «Мир информации и телекоммуникации.» Международная научно-техническая конференция студенчества и молодежи. Доклады, тезисы. Киев. 2002г. 312стр. стр. 172-173

Однією з складових частин курсу "Теорія мереж та систем зв'язку" для студентів спеціальності "Телекомунікаційні системи та мережі" є аналіз та оптимальний синтез телекомунікаційних мереж з використанням теорії графів. Проводиться оптимізація загальної вартості мережі, виявлення слабких ("вузьких") елементів, з'ясування найкоротших шляхів, тестування на відмовостійкость та інше. Найбільш поширені наступні методи і алгоритми [1, 2], які дозволяють аналізувати різні за розмірами та складом мережі:

     Алгоритм Дейкстри.

Дозволяє вирішувати одну з найбільш важливих потокових задач знаходження в мережі заданої топології ланцюгу із джерела в стік, що мінімізує вартість (час) проходження потоку заданої величини. Припустимо, що кожній дузі (i,j) орієнтованої мережі поставлено в відповідність деяке число Cij, яке називається узагальненою вартістю дуги. Фіктивним або "безкоштовним", дугам приписується вартість Cij=0, а кожній парі вузлів (i,j), для яких не існує дуги, з'єднуючої їх, приписується вартість Cij=∞. Ця задача є типовою задачею лінійного програмування: мінімізувати сумарну вартість проходження одиниці потоку

   (1)


при дотриманні умов на величину потоку в джерелі s (2), проміжних вузлах (3) та кінцевому вузлі t (4)

   (2)



   (3)


   (4)

Згідно з умовою (2), одиниця потоку витікає із джерела. Умова (2) гарантує збереження цієї одиниці потоку при проходженні по мережі. Згідно з умовою (3) одиниця потоку втікає в стік.
Алгоритм оснований на приписуванні вузлам тимчасових, або постійних позначок. Первісно кожному вузлу, виключаючи джерело, приписується тимчасова позначка, відповідна довжині найкоротшої дуги, що веде з джерела в даний вузол. Джерелу приписується постійна позначка, значення якій дорівнює нулю. Кожному вузлу, в який не можна дістатися безпосередньо з джерела, приписується тимчасова позначка ∞, а всім іншим вузлам - тимчасові позначки Csj, j≠s. Якщо визначено, що вузол належить найкоротшому ланцюгу, його позначка стає постійною. Алгоритм заснований на наступному простому факті: якщо відомий найкоротший ланцюг з вузла s в вузол j і вузол k належить цьому ланцюгу, то найкоротший ланцюг з s в k є частиною первісного ланцюга, що закінчується в вузлі k. Алгоритм починає працювати при j=s. Після цього величина j послідовно збільшується на одиницю, і при j=t алгоритм завершує роботу. Модель мережі, що ілюструє роботу алгоритму:

Приклад роботи алгоритму.

     Алгоритм Флойда.

Розглядається задача знаходження найкоротших ланцюгів між всіма парами вузлів мережі G= (N, A). Якщо довжина кожної дуги відповідає відстані або вартості одиниці потоку по цій дузі, то найкоротшим ланцюгом між двома довільними вузлами є ланцюг, вартість одиниці потоку по якому мінімальна. Дуги з множини А можуть бути орієнтованими і неорієнтованими. Однак оскільки направлення потоку в неорієнтованих дугах не можна визначити заздалегідь, то кожну таку дугу слід замінити двома орієнтованими дугами з протилежними напрямками і довжинами, рівними довжині неорієнтованими дуги.

     Алгоритм Прима.

Задача про найкоротшій остов має широке практичне застосування і є однією з небагатьох задач, що можуть бути вирішені за допомогою економних "поглинаючих" алгоритмів. Задача полягає в виборі таких дуг заданої мережі, що їхня сумарна вартість мінімальна і для будь-який пари вузлів знайдеться шлях (або маршрут), що з'єднає їх. Цього можна досягти, вибираючи дуги таким чином, що утворене ними дерево з'єднає всі вузли заданої мережі. Інакше кажучи, нас цікавить, як побудувати остов мінімальної вартості.

     Алгоритм Форда - Фалкерсона.

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

     Алгоритм Комівояжера.

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

На кафедрі Автоматики та телекомунікацій Донецького національного технічного університету було розроблено пакет прикладних програм, в якому реалізовані дані алгоритми. Характеристики програми:
      - Максимальна кількість вузлів мережі 20.
      - Результати обчислень можна проглянути на графі мережі або у вигляді таблиці для кожного кроку обчислень.
      - При зміні будь-яких даних відбувається автоматичне перерахування.
      - Програма працює з несиметричними і симетричними матрицями.
      - При завданні відстані (пропускний спроможності) слід вибирати цілі значення з діапазону [0; 100]. Числа, що виходять за цей діапазон будуть визначені як нескінченність і позначатися дефісом "-".

Програма знаходиться за адресою: http://www.donapex.net/~lex

Список літератури:

1. Кучмент Л.С., Демидов В.Н., Мотовилов Ю.Г. Формирование речного стока: Физ.-мат. модели. М.: Наука, 1983. 216с.
2. Д. Филлипс, А. Гарсиа-Диас Методы анализа сетей. М.: Мир, 1984 - 496 с.

Личная страница        Сайт ДонНТУ        Магистратура ДонНТУ        Поиск       

Главная        Магистерская работа        Ссылки        Результаты поиска