43341

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

Курсовая

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

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

Украинкский

2013-11-04

871 KB

31 чел.

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");

           }  }


 

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

53547. Система показателей оценки имущественного положения организации 13.86 KB
  Основными характеристиками имущественного положения компании являются: сумма хозяйственных средств, доля внеоборотных активов в валюте баланса, доля активной части основных средств, коэффициент износа, коэффициент выбытия, коэффициент обновления.
53548. Квіти - це життя, надія, радість і натхнення 1.31 MB
  Мета: ознайомити учнів з фрагментами життєвого та творчого шляху видатної української художниці Катерини Білокур; розвивати вміння правильно сприймати і розуміти зміст картини; вчити вдало висловлюватися про побачене; розвивати вміння самостійно підбирати кольори і їх відтінки для вдалого відтворення краси квітки у малюнку; розвивати естетичні смаки; виховувати почуття глибокої поваги до творців прекрасного;...
53550. Використання елементів методів проектів та комп’ютерної підтримки на уроках фізики 646.5 KB
  Важливим аспектом застосування інтерактивних технологій є оновлення структури уроків. Кожен вчитель знає, що такі уроки краще запам’ятовуються учнями, викликають зацікавленість і бажання взяти участь в уроці. В нашій роботі ми пропонуємо використання різних форм роботи на уроках математики, фізики та інформатики.
53551. Все про каву 127.5 KB
  Мета: поглибити знання учнів про каву як рослину її біологічні особливості; ознайомитися з хімічним складом кавових зерен їх корисність та шкідливість вплив на організм; розглянути технологію обробки кавових зерен історію поширення кави по світу; ознайомитися з найбільшими країнамивиробниками кави традиції та звичаї які з нею пов’язані. Розглянути різноманітні рецепти приготування кави цікаві факти про цю рослину та використання кави не за призначенням. Оформлення: назви лабораторій вислови про каву: Говорять все прекрасне в житті...
53552. Показатели оценки рыночной активности 25 KB
  Этот раздел анализа выполняется участниками фондового рынка. Показатели рыночной привлекательности позволяют оценить ожидания рынка относительно доходности и риска ценных бумаг эмитента. Для проведения анализа рыночной привлекательности используется как данные бухгалтерской отчетности...
53554. Казка казкою, а в ній наука 46 KB
  Пріоритетні лінії розвитку: соціально-моральний емоційноціннісний пізнавальний 6й рік життя Тема: Казка казкою а в ній наука Автор: Царенко Вікторія Миколаївна вихователь ДНЗ №8 Золотий півник м. Вихователь. Вихователь. Де ви могли чути ці слова Вихователь.
53555. Додатні та від’ємні числа. Протилежні числа. Координатний промінь 923.5 KB
  Протилежні числа. Мета модуля: сформувати уявлення учнів про зміст понять додатні числа від'ємні числа протилежні числа зміст поняття координати точки на координатній прямій; виробити вміння: відрізняти додатні числа від від'ємних й виконувати прості вправи що передбачають таку класифікацію; за готовими рисунками визначити координати вказаних точок звіряток та будувати на координатній прямій точки з вказаними координатами; розвивати логічне мислення та пізнавальну активність учнів при розв’язуванні вправ. Розв’язування...