43341

РОЗРОБКА ПРОГРАМНОГО КОМПЛЕКСУ ПО ЗНАХОДЖЕННЮ НАЙКОРОТШИХ МАРШРУТІВ НА ДТМ

Курсовая

Информатика, кибернетика и программирование

Транспортні задачі, у яких вершинами графа є пункти, а ребрами – дороги (автомобільні, залізні й ін.) і/або інші транспортні (наприклад, авіаційні) маршрути. Інший приклад – мережі постачання (енергопостачання, газопостачання, постачання товарами і т.д.), у яких вершинами є пункти виробництва й споживання, а ребрами – можливі маршрути переміщення (лінії електропередач, газопроводи, дороги і т.д.).

Украинкский

2013-11-04

871 KB

37 чел.

29


Глава 11. Независимость и покрытия

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТРАНСПОРТНИЙ УНІВЕРСИТЕТ

КАФЕДРА ІНФОРМАЦІЙНИХ СИСТЕМ І ТЕХНОЛОГІЙ

КУРСОВА РОБОТА

на тему: «РОЗРОБКА ПРОГРАМНОГО КОМПЛЕКСУ
ПО ЗНАХОДЖЕННЮ НАЙКОРОТШИХ МАРШРУТІВ НА ДТМ
»

з дисципліни «Новітні платформи програмування»

Виконав: ст. гр. КН. – ІІІ – 1

Давидок О.П.

(Варіант 6)

Науковий керівник:

ст. вик. Москаленко Н.В.

Київ-2011

ЗМІСТ

ВСТУП…………………………………………………………………….

2

  1.  АНАЛІЗ ПРЕДМЕТНОЇ ОБЛАСТІ. ПОСТАНОВКА ЗАДАЧІ…….

3

1.1 Математична постановка задачі маршрутизації……………………

3

1.2 Основні визначення теорії графів……………………………………

4

1.3 Постановка задачі…………………………………………………….

6

  1.  РОЗРОБКА СХЕМ АЛГОРИТМІВ……………………………….…..

8

2.1Використання теорії графів ……………………………………….….

8

2.2 Задача про найкоротший шлях………………………………….……

9

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

9

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

13

2.2.3 Матричний метод (третій метод)…………………………..….

16

3.ОПИС ЗАСТОСУВАННЯ ПРОГРАМНОГО КОМПЛЕКСУ……...

20

ВИСНОВОК………………………………………………………….……

23

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ…………………………….

24

ДОДАТОК ……………………………………………………………….

25

ВСТУП

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

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

Для вирішення транспортної задачі розроблено декілька методів та застосовується теорія графів.

Транспортні задачі, у яких вершинами графа є пункти, а ребрами – дороги (автомобільні, залізні й ін.) і/або інші транспортні (наприклад, авіаційні) маршрути. Інший приклад – мережі постачання (енергопостачання, газопостачання, постачання товарами і т.д.), у яких вершинами є пункти виробництва й споживання, а ребрами – можливі маршрути переміщення (лінії електропередач, газопроводи, дороги і т.д.).

Перша робота з теорії графів, що належить відомому швейцарському математику Л. Ейлеру, з'явилася в 1736г. Спочатку теорія графів здавалася досить незначним розділом математики, так як вона мала справу в основному з математичними розвагами й головоломками [1, 6, 12].

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

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

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


РОЗДІЛ 1

АНАЛІЗ ПРЕДМЕТНОЇ ОБЛАСТІ. ПОСТАНОВКА ЗАДАЧІ

1.1 Математична постановка задачі маршрутизації

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

Класичний варіант задачі маршрутизації [2, 10].

Маршрутизація транспорту відноситься до комбінаторних задач, які можна представити у вигляді графа G(V, E):

V = {v0, v1, ..., vn} — множина вершин (v0 — депо, v1... vn — споживачі),

E — множина ребер {(vi, vj) | i ≠ j},

C — матриця ненегативних відстаней(вартості шляху) cij між споживачами,

m — кількість машин,

Ri — маршрут i-ї машини (i=1..m),

C(Ri) — вартість маршруту Ri,

qi  – об'єм вантажу, що поставляється i- му споживачеві.

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

Рішенням задачі є: розбиття безлічі V на підмножини(маршрути); завдання порядку обходу на кожній підмножині(перестановка вершин маршруту).

Рішення є прийнятним (feasible), якщо усі маршрути задовольняють додатковим обмеженням завдання.

Цільовою функцією є вартість рішення задачі: FVRP = ∑C(Ri), i = 1..m,

де C(Ri) — сума довжин ребер маршруту Ri.

У класичному варіанті вимагається знайти прийнятне рішення з мінімальною вартістю.

Управління парком транспортних засобів. Це завдання стоїть перед комерційними перевізниками, які здійснюють замовлене транспортування вантажів і пасажирів (таксі), перед мережевими торговими компаніями, збутовими підрозділами нафтових компаній, а також компаніями, які торгують по каталогах і через інтернет - магазини. Мета – знизити загальні витрати на транспортування і прискорити виконання замовлень.

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

1.2 Основні визначення теорії графів

Як це не дивно, але для поняття «граф» немає загальновизнаного єдиного визначення. Різні автори, особливо стосовно до різноманітних застосувань, називають «графом» дуже схожі, але все-таки різні об'єкти. Тут використовується термінологія [4, 13, 15], яка була обрана з міркувань максимального спрощення визначень і доказів.

Графом G(V,E) називається сукупність двох множин – непустої множини V (множини вершин) і множини Е неупорядкованих пар різних елементів множини V (Е – множина ребер).

G(V,E)=<V; E>, V≠?, E, E=E-1.

Число вершин графа G позначимо р, а число ребер – q.

p:=p(G):=|V|, q:=g(G):=|E|.

Якщо елементами множини Е є впорядковані пари, то граф називається орієнтованим (або орграфом). У цьому випадку елементи множини V називаються вузлами, а елементи множини Е — дугами (орієнтованими ребрами).

Дуга — впорядкована пара вершин (v, w), в якій вершину v називають початком, а w — кінцем дуги. Можна сказати, що дуга v → w веде від вершини v до вершини w, при цьому вершина w суміжна з вершиною v.

Довжина маршрута — кількість ребер в маршруті (з повтореннями). Якщо маршрут M = v0,e1,v1,e2,v2,...,ek,vk, то довжина M дорівнює k (позначається  |M|=k).

Відстанню між вершинами u й v (позначається d(u,v)) називається найменша довжина шляху (u, v)

Зважений граф — граф, кожному ребру якого поставлено у відповідність деяке значення (вага ребра).

Інцидентність — поняття, що використовується тільки для ребра і вершини: якщо v1,v2 — вершини, а e = (v1,v2) — ребро, що їх з'єднує, тоді вершина v1 і ребро e інцидентні, вершина v2 і ребро e також інцидентні. Дві вершини (або два ребра) інцидентними бути не можуть. Для позначення найближчих вершин (ребер) використовується поняття суміжності.

Матриця інцидентності графа — матриця, значення елементів якої характеризуються інцидентністю відповідних вершин графа (по вертикалі) та його ребер (по горизонталі) [15]. Для неорієнтованого графа елемент приймає значення 1, якщо вершина і ребро, що відповідають йому, інцидентні. Для орієнтованого графа елемент приймає значення 1, якщо інцидентна вершина є початок ребра, значення -1, якщо кінець; в інших випадках  значенню елемента присвоюється 0 (рис.1.1).

Рис. 1.1. Зразки матриць інцидентності та суміжності

Суміжність — поняття, яке використовується по відношенню тільки до двох ребер або двох вершин: два ребра, інцидентні одній вершині, називаються суміжними; дві вершини, інцидентні одному ребру, також називаються суміжними.

Матриця суміжності графа G з кінцевим числом вершин n (пронумерованих числами від 1 до n) — це квадратна матриця A розміру n, у якій значення елемента aij дорівнює числу ребер з i-й вершини графа в j-ю вершину.

Множина суміжності вершини v — множина вершин, суміжних із вершиною v. Позначається Γ + (v)

Шлях в орграфі — послідовність вершин v1, v2, …, vn, для якої існують дуги v1 → v2, v2 → v3, …, vn-1 → vn. Кажуть, що шлях починається у вершині v1, проходить через вершини v2, v3, …, vn-1, і закінчується у вершині vn. [I-2,I-3]

В алгоритмах, що працюють зі зваженими графами (наприклад в алгоритмі Флойда-Уоршелла), елементи матриці суміжності замість чисел 0 і 1, що вказують на присутність або відсутність ребра, часто містять ваги самих ребер.

При цьому на місце відсутніх ребер ставлять деяке спеціальне граничне значення (англ. sentinel), що залежить від розв'язуваної задачі, звичайно 0 або  ∞.[3]

1.3 Постановка задачі

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

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

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

Перший метод Дейкстри знаходить найкоротші маршрути від заданої вершини до всіх інших;

другий метод Флойда;

третій матричний метод визначають найкоротші маршрути між будь-якою парою вершин;

                                   

                               Рис.1.2. Заданий орграф (варіант 6)

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

Структура проектованого програмного комплексу повинна включати три основні компоненти:

  •  процедуру визначення найкоротших маршрутів по методу Дейкстри;
  •  процедуру визначення найкоротших маршрутів по методу Флойда;
  •  процедуру визначення найкоротших маршрутів по модифікованому методу Дейкстри. 

Вимоги до функціональних характеристик програми.

Програма повинна виконувати наступні функції:

  •  Введення вхідних даних
  •  Рішення задачі - знаходження оптимального шляху
  •  Вивід знайденого рішення


РОЗДІЛ 2

РОЗРОБКА СХЕМ АЛГОРИТМІВ

2.1 Використання теорії графів

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

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

«Транспортні» задачі, у яких вершинами графа є пункти, а ребрами - дороги (автомобільні, залізні й ін.) і/або інші транспортні (наприклад, авіаційні) маршрути. Інший приклад - мережі постачання (енергопостачання, газопостачання, постачання товарами і т.д.), у яких вершинами є пункти виробництва й споживання, а ребрами - можливі маршрути переміщення (лінії електропередач, газопроводи, дороги і т.д.). Відповідний клас задач оптимізації потоків вантажів, розміщення пунктів виробництва й споживання і т.д., іноді називається задачами забезпечення або задачами про розміщення. Їхнім підкласом є задачі про вантажоперевезення [3, 12].

«Технологічні задачі», у яких вершини відображають виробничі елементи (заводи, цехи, верстати і т.д.), а дуги - потоки сировини, матеріалів і продукції між ними, полягають у визначенні оптимального завантаження виробничих елементів, що й забезпечують це завантаження потоків [8, 11].

Обмінні схеми, що є моделями таких явищ як бартер, взаємозаліки і т.д. Вершини графа при цьому описують учасників обмінної схеми (ланцюжка), а дуги - потоки матеріальних і фінансових ресурсів між ними. Задача полягає у визначенні ланцюжка обмінів, оптимальної з погляду, наприклад, організатора обміну й погодженої з інтересами учасників ланцюжка й існуючими обмеженнями [3, 6, 8].

Управління проектами. З погляду теорії графів проект - сукупність операцій і залежностей між ними (сітковий графік - див. нижче). Хрестоматійним прикладом є проект будівництва деякого об'єкта. Сукупність моделей і методів, що використовують мову й результати теорії графів і орієнтованих на рішення задач управління проектами, одержала назву календарно-мережного планування й управління (КМПУ) [8]. У рамках КМПУ вирішуються завдання визначення послідовності виконання операцій і розподілу ресурсів між ними, оптимальних з погляду тих або інших критеріїв (часу виконання проекту, витрат, ризику й ін.).

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

Моделі організаційних структур, у яких вершинами є елементи організаційної системи, а ребрами або дугами - зв'язку (інформаційні, що управляють, технологічні й ін.) між ними [10, 11].

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

Теорія графів надає дуже зручну мову для опису програмних (та й багатьох інших) моделей. Цю тезу можна пояснити наступною аналогією. Поняття відносини також можна цілком виразити через поняття множини. Однак незалежне визначення поняття відносини зручніше — введення спеціальних термінів і позначень спрощує виклад теорії й робить її більш зрозумілою. Те ж стосується й до теорії графів. Струнка система спеціальних термінів і позначень теорії графів дозволяє просто й доступно описувати складні й тонкі речі. Особливо важлива наявність наочної графічної інтерпретації поняття графа.

Сама назва «граф» має на увазі наявність графічної інтерпретації. Картинки дозволяють відразу «побачити» суть справи на інтуїтивному рівні, доповнюючи й прикрашаючи стомлюючі раціональні текстові докази й складні формули [4].

2.2 Задача про найкоротший шлях

Завдання пошуку найкоротших і найдовших шляхів на графах виникають  у різних галузях управління. Розглянемо задачу про найкоротший шлях.

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

Відомо [4, 12], що для існування найкоротшого шляху необхідно й досить відсутності в мережі контурів негативної довжини.

Алгоритми рішення задачі про найкоротший шлях дозволяють розв'язувати широкий клас задач дискретної оптимізації.

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

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

Алгоритм Дейкстри знаходить найкоротший шлях між двома даними вершинами в (ор)графі, якщо довжини дуг не негативні.

ЗАУВАЖЕННЯ. Для застосовності алгоритму Дейкстри достатньо виконання більш слабкої умови, чім позитивність довжин дуг. А саме, досить виконання нерівності трикутника: u,v,w  V d(u, v) ≤ d(u, w) + d(w, v), яка, мабуть, виконується, якщо довжини дуг не негативні [6].

Застосуємо алгоритм Дейкстри для заданого орієнтованого графа рисунок 1.5.

Матриця довжин дуг для заданого графа має вигляд:

1

2

3

4

5

6

1

0

10

100

30

2

10

0

80

50

D0 =

3

0

40

10

4

0

60

5

70

0

6

20

0

Стартова вершина, від якої будується дерево найкоротших шляхів - вершина 1. Задаємо стартові умови: d(1)=0, d(x)=∞.

Забарвлюємо вершину 1, y=1 (рис. 2.1).

Знаходимо найближчу вершину до забарвленої нами, використовуючи формулу: d(x)=min{d(x); d(y)+ a(y,x)} 

d(2)=min{d(2) ; d(1)+a(1,2)}=min{∞; 0+10}=10 

d(3)=min{d(3) ; d(1)+a(1,3)}=min{∞; 0+∞}=∞

d(4)=min{d(4) ; d(1)+a(1,4)}=min{∞; 0+100}=100 

d(5)=min{d(5) ; d(1)+a(1,5)}=min{∞; 0+30}=30

d(6)=min{d(6) ; d(1)+a(1,6)}=min{∞; 0+∞}=∞

                                 

Рис. 2.1. Крок 1

Мінімальну довжину має шлях від вершини 1 до вершини 2 d(2)=10. Включаємо вершину №2 в поточне орієнтованe дерево,  та дугу яка веде в цю вершину. Згідно з вираженням це дуга (1,2) рис. 2.2.

d(3)=min{d(3) ; d(2)+a(2,3)}=min{∞; 10+80}=90

d(4)=min{d(4) ; d(2)+a(2,4)}=min{100; 10+∞}=100

d(5)=min{d(5) ; d(2)+a(2,5)}=min{30; 10+50}=30

d(6)=min{d(6) ; d(2)+a(2,6)}=min{∞; 10+∞}=∞

                                 

Рис. 2.2. Крок 2

Мінімальну довжину має шлях від вершини 1 до вершини 3 d(3)=30. Включаємо вершину №3 в поточне орієнтованe дерево, та дугу яка веде в цю вершину. Згідно з вираженням це дуга (1,3).

d(4)=min{d(4) ; d(3)+a(3,4)}=min{100; 0+40}=40

d(5)=min{d(5) ; d(3)+a(3,5)}=min{30; 0+∞}=30

d(6)=min{d(6) ; d(3)+a(3,6)}=min{∞; 90+10}=100

Мінімальну довжину має шлях від вершини 1 до вершини 6 d(6)=40. Включаємо вершину №6 в поточне орієнтованe дерево, та дугу яка веде в цю вершину. Згідно з вираженням це дуга (3,6) рис. 2.3.

d(4)=min{d(4) ; d(6)+a(6,4)}=min{40; 40+∞}=40

d(5)=min{d(5) ; d(6)+a(6,5)}=min{30; 40+20}=30

                                

Рис. 2.3. Крок 4

Мінімальну довжину має шлях від вершини 1 до вершини 5 d(5)=60. Включаємо вершину №5 в поточне орієнтованe дерево, та дугу яка веде в цю вершину. Згідно з вираженням це дуга (2,5).

d(4)=min{d(4) ; d(5)+a(5,4)}=min{40; 30+∞}=30

Мінімальну довжину має шлях від вершини 1 до вершини 4 d(4)=70. Включаємо вершину №4 в поточне орієнтованe дерево, та дугу яка веде в цю вершину. Згідно з вираженням це дуга (3,4).

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

                                   

Рис. 2.4. Відповідь

d(1)=1 Довжина маршруту L=0

d(2)=1-2 Довжина маршруту L=10

d(3)=1-2-3 Довжина маршруту L=90

d(4)=1-4 Довжина маршруту L=100

d(5)=1-5 Довжина маршруту L=30

d(6)=1-2-3-6 Довжина маршруту L=100

 (У додатку A наведений текст програми на мові C#, який реалізує алгоритм Дейкстри).

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

Алгоритм Флойда знаходить найкоротші шляхи між усіма парами вершин в (ор)графі. У цьому алгоритмі для зберігання інформації про шляхи використовується матриця Н[1..р, 1..р], де

H [i,j] = к, якщо к — перша вершина, що досягається на найкоротшому шляху з i в j; або 0, якщо з і в j немає шляхів.

ЗАУВАЖЕННЯ. Якщо в G є цикл із негативною вагою, то розв'язку поставленої задачі не існує, тому що можна “накручувати” на цьому циклі як завгодно короткий шлях [11].

Застосуємо алгоритм для заданого орієнтованого графа рис. 1.5. 

1

2

3

4

5

6

1

0

10

100

30

2

10

0

80

50

D0 =

3

0

40

10

4

0

60

5

70

0

6

20

0

На підставі матриці D0, вичислимо послідовно усі елементи матриці D1. Для цього ми використовуємо рекурентне співвідношення di,j1=min{ di,10+ d1,j0; di,j0}.

1

2

3

4

5

6

1

0

10

100

30

2

10

0

40

110

40

D1 =

3

0

40

10

4

0

60

5

70

0

6

20

0

На підставі матриці D1, вичислимо послідовно усі елементи матриці D2. Для цього ми використовуємо рекурентне співвідношення di,j2=min{ di,21+ d2,j1; di,j1}.

1

2

3

4

5

6

1

0

10

90

100

30

2

10

0

80

110

40

D2 =

3

0

40

10

4

0

60

5

70

0

6

20

0

На підставі матриці D2, вичислимо послідовно усі елементи матриці D3. Для цього ми використовуємо рекурентне співвідношення di,j3=min{ di,32+ d3,j2; di,j2}.

1

2

3

4

5

6

1

0

10

90

100

30

100

2

10

0

80

110

50

90

D3 =

3

0

40

10

4

0

60

5

70

110

0

80

6

20

0

На підставі матриці D3, вичислимо послідовно усі елементи матриці D4. Для цього ми використовуємо рекурентне співвідношення di,j4=min{ di,43+ d4,j3; di,j3}.

1

2

3

4

5

6

1

0

10

90

100

30

100

2

10

0

80

110

40

90

D4 =

3

0

40

10

4

0

60

5

70

110

0

80

6

20

0

На підставі матриці D4, вичислимо послідовно усі елементи матриці D5. Для цього ми використовуємо рекурентне співвідношення di,j5=min{ di,54+ d5,j4; di,j4}.

1

2

3

4

5

6

1

0

10

90

100

30

100

2

10

0

80

110

40

90

D5 =

3

0

40

10

4

0

60

5

70

110

0

80

6

90

130

20

0

На підставі матриці D5, вичислимо послідовно усі елементи матриці D6. Для цього ми використовуємо рекурентне співвідношення di,j6=min{ di,65+ d6,j5; di,j5}.

1

2

3

4

5

6

1

0

10

90

100

30

100

2

10

0

80

110

40

90

D6 =

3

0

40

30

10

4

150

0

80

60

5

70

110

0

80

6

90

130

20

0

У багатьох ситуаціях потрібно роздрукувати найдешевший шлях від однієї вершини до іншої. Щоб відновити при необхідності найкоротші шляхи, можна в алгоритмі Флойда ввести ще одну матрицю Р, у якій елемент P[i, j] містить вершину k, отриману при перебуванні найменшого значення A[i, j]. Якщо P[i, j] = 0, то найкоротший шлях з вершини i у вершину j складається з однієї дуги i—>j. Модифікована версія алгоритму Флойда, що дозволяє відновлювати найкоротші шляхи (У додатку A наведений текст програми на мові C#, який реалізує алгоритм Флойда).

2.2.3 Матричний метод (третій метод)

Спочатку складемо матрицю суміжності S вже відомого графа G = (V, Е), зображеного на рис. 1.5. Рядки матриці S відповідають вершинам Vi , стовпці – вершинам Vj . Елементи головної діагоналі дорівнюють 0, так як приймається, що відстань усередині вузла рівна нулю. Елемент Sij , що стоїть на перетинанні i-го рядка й j-го стовпця, покладається рівним значенню при наявності прямого зв'язку (дуги Eij) між вершинами  Vi й Vj і ∞ – при відсутності такого зв'язку.

1

2

3

4

5

6

1

0

10

100

30

2

10

0

40

110

50

S1=

3

0

40

10

4

0

60

5

70

0

6

20

0

Далі визначається матриця S2 = S + S за наступним правилом додавання елементів матриць S:

(1)

При знаходженні матриці r-ї використовують такі ж операції:

,

елементи якої:

Розрахунок матриці закінчується, якщо в процесі розрахунку матриці виконується рівність (2).

(2)

  

1

2

3

4

5

6

1

2

3

4

5

6

1

20

90

60

160

1

0

30

130

120

50

100

2

20

120

110

40

90

2

30

0

100

160

70

130

S2=

3

0

30

100

S3=

3

100

120

4

0

80

4

150

0

5

110

0

80

5

100

170

6

90

0

6

130

100

1

2

3

4

5

6

1

40

110

170

80

140

2

40

140

130

60

110

3

190

140

110

S4=

4

190

160

5

170

190

6

120

190

Елементи матриці , розрахунок закінчуємо.

Елементи матриці  визначають довжину найкоротшого шляху між вершинами Vi і Vj, що містить m ланок (дуг).

У процесі  формування матриць одержуємо матрицю P, елементи якої являють собою кількості дуг, що складають найкоротші шляхи між вершинами Vi і Vj графа G. 

1

2

3

4

5

6

1

2

1

2

1

1

3

2

1

2

1

2

2

2

P

=

3

2

2

3

1

2

1

4

1

1

3

4

2

1

5

1

1

1

2

3

2

6

2

2

2

3

1

3

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

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

РОЗДІЛ 3

ОПИС ЗАСТОСУВАННЯ ПРОГРАМНОГО КОМПЛЕКСУ

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

Для початку роботи з програмою запустіть файл curs.exe (рис. 3.1).

Рис. 3.1. Головне вікно програми

Для подальшого розрахунку необхідно обрати метод. Виберемо спочатку «метод Дейкстра» (рис.3.2).

Рис. 3.2. «метод Дейкстра»

Результат роботи програми відповідає розрахункам з розділу 2, підрозділ 2.2.1, програма працює вірно. Далі оберемо «метод Флойда» (рис.3.3).

Рис. 3.3. «метод Флойда»

Результат роботи програми відповідає розрахункам з розділу 2, підрозділ 2.2.2, програма працює вірно. Для розрахунку останнього методу оберемо «Матричный метод» (рис. 3.4).

Рис. 3.4. «Матричный метод»

Результат роботи програми відповідає розрахункам з розділу 2, підрозділ 2.2.3, програма працює вірно. Всі методи дають однакові результати.


ВИСНОВОК

При виконанні курсової роботи були виконані наступні завдання:

  1.  Вивчені загальні поняття теорії графів: граф, вузли графа, орієнтовані графи, дуги графа, найкоротші шляхи з однієї вершини в іншу.
  2.  Вивчені алгоритми знаходження найкоротших шляхів в графі, такі як алгоритм Дейкстри, алгоритм Флойда та матричний метод.
  3.  Створений додаток, який реалізує вказані алгоритми для поставленого завдання.
  4.  Додаток відлагоджений і протестований на прикладах, приведених в курсовій роботі.

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

 


СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

  1.   Бурков В.Н., Горгидзе И.А., Ловецкий С.Е. Прикладные задачи теории графов. Тбилиси: Мецниереба, 1974. - 234 с.
  2.  Бурков В.Н., Ланда Б. Д., Ловецкий С.Е., Тейман А.И., Чернышев В.Н. Сетевые модели и задачи управления.М.: Советское радио, 1967. - 144 с.
  3.  Вагнер Г. Основы исследования операций. М.: Мир, 1972. Т. 1-4.
  4.  Воронин А.А., Мишин С.П. Оптимальные иерархические структуры. М.: ИПУ РАН, 2003. - 210 с.
  5.  Глинський Я.М., Анохін В.Є., Ряжська В.А. C++ і C++ Builder. Навч. посіб. 2-е вид. – Львів: Деол, СПД Глинський, 2004. – 192 с.
  6.  Емеличев В.А,, Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. - 384 с.
  7.  Климова Л.М. Основы практического программирования на языке Си++. – М.: Приор, 2003. – 464 с.
  8.  Коргин Н.А. Механизмы обмена в активных системах. М.: ИПУ РАН, 2003.
  9.   Методичні вказівки до виконання курсової роботи з дисципліни "Новітні платформи програмування" для студентів спеціальності 7.080401 "Інформаційні управляючі системи та технології" / Укл. Н.В. Москаленко, Н.В. Кірхар, Київ, НТУ, 2011
  10.   Новиков Д.А. Сетевые структуры и организационные системы. М.: ИПУ РАН, 2003. - 102 с.
  11.   Прокудін Г. С., Білоус С. О. Один з підходів до вирішення сітьової транспортної задачі. // Безпека дорожнього руху України. – К.: ООО "Журнал "Радуга", 2003, № 1 – 2(15). – С. 52 – 56.


ДОДАТОК

КОД ПРОГРАМИ

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

namespace curs

{ public partial class Form1 : Form

   { tatic Int32 inf = 2147000000;

       int[,] ribs = {{inf, 10, inf,100, 30,inf},

//Введення існуючої матріці

                      {10,inf,80,inf,50,inf},

                      {inf,inf,inf,40,inf,10},

                      {inf,inf,inf,inf,inf,60},

                      {inf,inf,70,inf,inf,inf},

                      {inf,inf,inf,inf,20,inf}};

       public Form1()

       { InitializeComponent();

       }

//Створення кнопки зберігання результату

       private void buttonDSave_Click(object sender, EventArgs e)

       {saveFileDialog.Filter = "txt файли(*.txt)|*.txt";

           saveFileDialog.FileName = "Result";

           if (saveFileDialog.ShowDialog() == DialogResult.OK)

           { richTextBoxDRs.SaveFile(saveFileDialog.FileName, RichTextBoxStreamType.PlainText);

           }  }

//Створення кнопки очищення вікна з результатами

       private void buttonDClear_Click(object sender, EventArgs e)

       { richTextBoxDRs.Clear();

       }

//Створення кнопки виходу з програми

       private void buttonDExit_Click(object sender, EventArgs e)

       {Application.Exit();

       }

//Знаходження мінімального елемента матриці

       private int find_min()

       {  int i,v=0,min = MAXX;

           for(i=0;i<n;i++)

           if (u[i]==0 && d[i] < min)

           {  min = d[i]; v = i;

           }

             return v;       }

       private void InitArrays()

       {  n = ColQty;

           for (i = 0; i < n; i++)

           {   u[i] = 0;

               d[i] = MAXX;

               p[i] = 0;

               for (j = 0; j < n; j++)

               {  mp[i, j] = -1;

                   int tmp;

                   try

                   { tmp = Convert.ToInt32(Grid.Rows[i].Cells[j].Value);

                   }

                   catch

                   {  tmp = 0;

                   }

                   if (tmp != 0)

                   { Grid.Rows[i].Cells[j].Value = tmp;

                       m[i, j] = tmp;

                   }   else

                   {  Grid.Rows[i].Cells[j].Value = "";

                       m[i, j] = MAXX;

                   }

                   if (i == j)//путь в самого себя ))

                       m[i, j] = 0;

               }            }

           d[s] = 0;

           u[s] = 1;

           p[s] = s;  }

       private void Relax(int i, int j)

       { if (d[j] > d[i] + m[i, j])

           { d[j] = d[i] + m[i, j];

               p[j] = i;

           }         }

// Реалізація методу Дейкстра

       private void Deikstra(int start_V)

       { s = start_V;

           v = s;

           InitArrays();

           listBox1.Items.Add("Метод Дейкстры.");

            for (i = 0; i < n; i++)

           {  v = find_min();

               if (v == n)

                   break;

               for (j = 0; j < n; j++)

                   if (u[j] == 0) Relax(v, j);

               u[v] = 1;

           }

           string ss = "";

           for (i = 0; i < n; i++)

               ss = ss + d[i] + "   ";

   listBox1.Items.Add("Кратчайшие расстояния от вершины источника: "+ss);

           ss = "";

           for (i = 0; i < n; i++)

               ss = ss + (p[i]+1) + "   ";

           listBox1.Items.Add("Список вершин: " + ss);

           for (i = 0; i < n; i++)

           {  ss = "";

               j = i;

               for (; ; )

               { ss = "->"+(j + 1) + ss;

                   j = p[j];

                   if (j == 0)

                       break;

               }

               ss = "1" + ss;

 listBox1.Items.Add("d(" + (i + 1) + ")=" + ss + " Длина маршрута L= " + d[i]);

           }   }

//Реалізація методу Флойда

       private void Floid()

       {  listBox1.Items.Add("Метод Флойда.");

           InitArrays();

           for (i = 0; i < n; i++)

               m[i, i] = 0;

           int k = 0;

           for (k = 0; k < n; k++)

           {  for (i = 0; i < n; i++)

                   for (j = 0; j < n; j++)

                       if (m[i, k] < MAXX && m[k, j] < MAXX)

                       {  if (m[i, j] > (m[i, k] + m[k, j]))

                           {m[i, j] = m[i, k] + m[k, j];

                               mp[i, j] = k;

                           }  }

               listBox1.Items.Add("Шаг :" + (k+1));

               for (i = 0; i < n; i++)

               {  string ss = "";

                   for (j = 0; j < n; j++)

                       if (m[i,j]!=MAXX)

                           ss = ss + (m[i, j]) + "   ";

                       else

                           ss = ss + "  ∞   ";

                   listBox1.Items.Add(ss);

               }    }

           listBox1.Items.Add("Матрица промежуточных вершин:");

           for (i = 0; i < n; i++)

           {  string ss = "";

               for (j = 0; j < n; j++)

                       ss = ss + (mp[i, j]+1) + "   ";

               listBox1.Items.Add(ss);

           }      }

       public Form1()

       {   InitializeComponent();

       }

       private void textBox1_KeyPress(object sender, KeyPressEventArgs e)

       {    if (e.KeyChar == 13)

           {    if (textBox1.Text.Length>0)

               {  try

                   {  ColQty = Convert.ToInt32(textBox1.Text);

                   }

                   catch

                   {  ColQty=0;

                   }

                   if (ColQty > 0)

                   {  Grid.ColumnCount = ColQty;

                       Grid.RowCount = ColQty;

                       Grid.RowHeadersVisible = false;

                   }   }    }   }

       private void button1_Click(object sender, EventArgs e)

       {  Deikstra(0);   }

       private void button2_Click(object sender, EventArgs e)

       {    Floid();      }

richTextBoxDRs.AppendText("\t\tМатричний метод пошуку найкоротших шляхів на графі.\n");

           int sn = 0;

           for (int k = 1; k < 20; k++)

           { int f = 0;

               for (int i1 = 0; i1 < n; i1++)

                   for (int j1 = 0; j1 < n; j1++)

                       if (S[k - 1, i1, j1] == 0)

                           f++;

               if (f != 0)

               { sn++;

                   for (int i = 0; i < n; i++)

                       for (int j = 0; j < n; j++)

                       { int min = inf;

                           for (int k1 = 0; k1 < n; k1++)

                            if ((S[0, i, k1] * S[k - 1, k1, j]) != 0)

                                  { if ((S[0, i, k1] + S[k - 1, k1, j]) < min)

                                       min = S[0, i, k1] + S[k - 1, k1, j];

                           }

                           if (min != inf)

                               S[k, i, j] = min;

                           else S[k, i, j] = 0;

                       } }

               else goto l1;

           }

         int indmin = 0;

           for (int i = 0; i < n; i++)

               for (int j = 0; j < n; j++)

               { int min = inf;

                   for (int k = 0; k < 20; k++)

                       if (S[k, i, j] != 0 && S[k, i, j] < min)

                       {  min = S[k, i, j];

                           indmin = k;

                       }

                   D[i, j] = min;

                   P[i, j] = indmin;

               }

           for (int k = 0; k < sn + 1; k++)

           { richTextBoxDRs.AppendText("\t\t\tМатриця S" + (k + 1).ToString() + "\n");

               for (int i1 = 0; i1 < n; i1++)

               { richTextBoxDRs.AppendText("\t\t");

                   for (int j1 = 0; j1 < n; j1++)

                       richTextBoxDRs.AppendText(S[k, i1, j1].ToString() + "\t");

                   richTextBoxDRs.AppendText("\n");

               }

               richTextBoxDRs.AppendText("\n");

           }

           richTextBoxDRs.AppendText("\t\tМатриця D" + "\n");

           for (int i = 0; i < n; i++)

           { richTextBoxDRs.AppendText("\t\t");

               for (int j = 0; j < n; j++)

                   if (D[i, j] != inf)

                       richTextBoxDRs.AppendText(D[i, j].ToString() + "\t");

                   else richTextBoxDRs.AppendText("∞" + "\t");

               richTextBoxDRs.AppendText("\n");

           }

           richTextBoxDRs.AppendText("\n");

           richTextBoxDRs.AppendText("\t\tМатриця P" + "\n");

           for (int i = 0; i < n; i++)

           { richTextBoxDRs.AppendText("\t\t");

               for (int j = 0; j < n; j++)

                   richTextBoxDRs.AppendText((P[i, j] + 1).ToString() + "\t");

               richTextBoxDRs.AppendText("\n");

           }

           richTextBoxDRs.AppendText("\n");

           richTextBoxDRs.AppendText("\t\t Найкоротші маршрути та їх відстані");

           richTextBoxDRs.AppendText("\n");

           string route = "";

           int indmin1 = 0;

           for (int i = 0; i < n; i++)

           { for (int j = 0; j < n; j++)

               { route = (i + 1).ToString() + "->";

                   if (S[0, i, j] == D[i, j])

                   { route = route + (j + 1).ToString();

                       if (D[i, j] == inf)

                           richTextBoxDRs.AppendText("\tМаршрут " + route + "\t\t Довжина =Шляху не існує!\n");

                       else richTextBoxDRs.AppendText("\tМаршрут " + route + "\t\t Довжина =" + D[i, j] + "\n");

                   }

                   else

                   { int ind = i;

                       for (int i1 = (P[ind, j] - 1); i1 > -1; i1--)

                       {  int min = inf;

                           for (int k = 0; k < n; k++)

                           { if ((S[0, ind, k] * S[i1, k, j]) != 0)

                               { if ((S[0, ind, k] + S[i1, k, j]) < min)

                                   { min = S[0, ind, k] + S[i1, k, j];

                                       indmin1 = k;

                                   }  }  }

                           route = route + (indmin1 + 1).ToString() + "->";

                           ind = indmin1;

                       }

                       route = route + (j + 1).ToString();

                       if (D[i, j] == inf)

                           richTextBoxDRs.AppendText("\tМаршрут " + route + "\t\t Довжина =Шляху не існує!\n");

                       else richTextBoxDRs.AppendText("\tМаршрут " + route + "\t\t Довжина =" + D[i, j] + "\n");

                  }  }

               richTextBoxDRs.AppendText("\n");

           }  }


 

А также другие работы, которые могут Вас заинтересовать

84042. Электронное правительство: понятие и роль в развитии документооборота 38.19 KB
  Электронное правительство система электронного документооборота государственного управления основанная на автоматизации всей совокупности управленческих процессов в масштабах страны и служащая цели существенного повышения эффективности государственного управления и снижения издержек социальных коммуникаций для каждого члена общества. Создание электронного правительства предполагает построение общегосударственной распределенной системы общественного управления реализующей решение полного спектра задач связанных с управлением документами и...
84043. Нормативное правовое обеспечение создания электронного правительства в РФ 37.84 KB
  К целям Федерального закона № 126ФЗ отнесены содействие внедрению перспективных технологий и стандартов; создание условий для развития российской инфраструктуры связи обеспечения ее интеграции с международными сетями связи; создание условий для обеспечения потребностей в связи для нужд государственного управления обороны страны безопасности государства и обеспечения правопорядка. Кроме того Федеральным законом № 126ФЗ устанавливается универсальная услуга связи услуга связи...
84044. Нормативное обеспечение создания электронного правительства в РФ с 2008 г. по настоящее время 40.25 KB
  № 8ФЗ Об обеспечении доступа к информации о деятельности государственных органов и органов местного самоуправления далее Федеральный закон № 8ФЗ. Действие Федерального закона № 8ФЗ распространяется на отношения связанные с обеспечением доступа пользователей информацией к информации о деятельности государственных органов и органов местного самоуправления. Федеральный закон № 8ФЗ определяет принципы и способы обеспечения доступа к информации о деятельности государственных органов и органов местного самоуправления закрепляет права...
84045. Федеральный закон от 27 июля 2010 г. № 210-ФЗ «Об организации предоставления государственных и муниципальных услуг»: новации в документообороте при предоставлении государственных (муниципальных) услуг 38.91 KB
  № 210ФЗ Об организации предоставления государственных и муниципальных услуг: новации в документообороте при предоставлении государственных муниципальных услуг. N 210ФЗ Об организации предоставления государственных и муниципальных услуг направлен на регулирование вопросов предоставления государственных и муниципальных услуг в том числе вопросов предоставления таких услуг в электронном виде. Закона также устанавливает требования к процедурам предоставления государственных муниципальных услуг в электронном виде; Закон регламентирует...
84046. Документационное обеспечение управления как наука и учебная дисциплина 36.63 KB
  Документационное обеспечение управления ДОУ это деятельность направленная на организацию документирования в организации и управления технологическим циклом движения документов. Поэтому термин ДОУ подчеркивает информационносоставляющую в современной организации делопроизводства. Документационное обеспечение управления это деятельность аппарата управления охватывающая вопросы документирования и организации работы с документами в процессе осуществления им управленческих функций. Деятельность каждой организации осуществляется в...
84047. История развития делопроизводства в России 44.78 KB
  В этих условиях единая система делопроизводства не была востребована самой системой управления. Рассмотренный период можно охарактеризовать как период постепенного складывания традиций русской системы делопроизводства накопления опыта документирования обработки и хранения документов обеспечения их сохранности. Система государственного делопроизводства начинает складываться только в середине 15 века с развитием Московского княжества в государство.
84048. Документооборот: понятие, функции, составные части. Объем документооборота, способы его учета 40.09 KB
  Документооборот организации это движение документов в организации с момента их создания или получения до завершения исполнения или отправления. Характеристикой документооборота является его объем под которым понимается количество документов поступивших в организацию и созданных ею за определенный период. Кроме этого регистрация позволяет осуществлять контроль исполнения документов а также вести их поиск. Наряду с организацией документооборота в понятие организация работы с документами входит хранение документов и их использование в...
84049. Виды документов ИОГВ Пермского края их роль в документационном обеспечении управления 34.29 KB
  Деятельность губернатора Пермского края руководителя администрации губернатора Пермского края председателя Правительства Пермского края заместителей председателя Правительства Пермского края руководителя аппарата Правительства Пермского края обеспечивается комплексом документов составляющим организационнораспорядительную документацию. Губернатор Пермского края издает указы и распоряжения во исполнение Конституции Российской Федерации федеральных законов нормативных актов Президента Российской Федерации постановлений Правительства...
84050. Способы документирования. Способы записи и воспроизводства информации документа 35.53 KB
  Способы записи и воспроизводства информации документа. Документирование запись информации на различных носителях по установленным правилам. Носитель документированной информации материальный объект используемый для закрепления и хранения на нем речевой звуковой или изобразительной информации в том числе в преобразованном виде. Запись информации это способ фиксирования информации на материальном носителе.