Дипломная (вкр): Алгоритми на графах та їх практичне застосування

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

Чому дорівнює час роботи процедури DFS? Цикли в рядках 1-3 і 5-7 процедури DFS виконуються за час Θ(V), виключаючи час, необхідний для виклику процедури DFS_visit. Процедура DFS_visit викликається рівно по одному разу для кожної вершини, оскільки вона викликається тільки для білих вершин, і перше, що вона робить, - це забарвлює передану як параметр вершину в сірий колір. В процесі виконання DFS_Visit(v) цикл в рядках 4-7 виконується  раз. Оскільки , загальна вартість виконання рядків 4-7 процедур DFS_VlSlT рівна Θ(Е). Час роботи процедури DFS, таким чином, рівний Θ(V + Е).

.3 Побудова мінімального остового дерева. Алгоритм Прима

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

Опишемо процедуру виконання цього алгоритму. Позначимо через N={1,2,…,n}множина вузлів мережі і введемо нові позначення:- множина вузлів мережі, з'єднаних алгоритмом після виконання k-й ітерації цього алгоритму,

- множина вузлів мережі, з'єднаних з вузлами безлічі Ck після виконання k-й ітерації цього алгоритму.

Крок 0. Думаємо C0 =  і  = N.

Крок1. Вибираємо будь-який вузол і з множини  визначаємо C1 = {i}, тоді  = N-{i}. Думаємо k = 2.

Основний крок k. У множини вибираємо вузол j*, що з'єднаний самою короткою дугою з яким-небудь вузлом з множини Ck-1. Вузол j* приєднується до множини Ck-1 і видаляється з множини . Таким чином, Ck = Ck-1 + {j*},  = - {j*}.

Якщо множина  порожня, то виконання алгоритму закінчується. У противному випадку думаємо k = k + 1 і повторюємо останній крок.

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

Алгоритм Дейкстры вирішує задачу про найкоротший шлях з однієї вершини в зваженому орієнтованому графові G = (V, Е) у тому випадку, коли ваги ребер не негативні.

Існують дві реалізації алгоритму: для пошуку найкоротшого шляху між двома парами вершин і від однієї вершини до усіх інших. Розглянемо реалізацію першого алгоритму на основі списку суміжних вершин

Особливості програмної реалізації:

·   Нумерація вершин - цілі числа, починаючи з 0

·        Список вершин виду  реалізовується у вигляді двовимірної матриці з 3 стовпців. Кожен рядок матриці описує вершину. У 0 стовпці збережений статус вершини (тимчасова/постійна/перевірена постійна). У 1 стовпці зберігаємо компоненту відстані. У 2-му стовпці - номер попередньої вершини.

·        Нескінченність представляємо як дуже велике число (на порядок більше суми усіх ребер графа)

Терміни:

Тимчасова вершина (0): вершина графа, до якої вже відомий який-небудь шлях

Постійна вершина (1): вершина графа, до якої вже відомий мінімальний шлях

Перевірена постійна вершина (2) : вершина графа, до якої вже відомий мінімальний шлях і прораховані усі шляхи до суміжних вершин

Початкові установки:

Кожній вершині графа ставимо у відповідність впорядковану пару . Перша координата пари : відстань від початкової вершини до поточної вершини. Друга координата пари : попередній вузол в дорозі від початку до цієї вершини.

Алгоритм.

) Починаємо у вузлі . В списку вершин привласнюємо їй значення (0, 0) і робимо її постійною.

) Основний крок. Для останньої вершини , визначеної як постійну, оцінюємо відстані з початку шляху через постійну вершину k до усіх суміжних вершин. Для цього знаходимо суму m і ваги ребра t з вершини vk до суміжної вершини vs і порівнюємо з наявним значенням в списку вершин. Якщо отриманий шлях менший за наявний, привласнюємо вершині vs значення (m+t, k). Статус вершини vs встановлюємо як тимчасова вершина.

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

) Якщо остання постійна вершина не кінцева, переходимо до пункту 2. Інакше відстань, присвоєна їй, є мінімальною відстанню між заданими вершинами

) Для знаходження шляху необхідно почати з кінцевої вершини і переглядати список вершин в зворотному порядку, поки не доберемося в початок.

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

.5 Модель Флойда-Уоршалла

Розглянемо завдання про пошук найкоротших шляхів між усіма парами вершин в орієнтованому графові G = (V, Е). Час роботи отриманого в результаті алгоритму, відомого як алгоритм Флойда-Уоршалла (Floyd - Warshall algorithm), рівно Θ(V3). Наявність ребер з негативною вагою допускається, але передбачається, що цикли з негативною вагою відсутні.

У цьому алгоритмі мережа представлена у вигляді квадратної матриці з n рядками і n стовпцями. Елемент (i,j) дорівнює відстані dij від вузла i до вузла j, що має кінцеве значення, якщо існує дуга (i,j), і дорівнює нескінченності в противному випадку.

Покажемо спочатку основну ідею методу Флойда-Уоршалла. Нехай є три вузли i,j і k і задані відстані між ними (рисунок 2.1). Якщо виконується нерівність dij+djk<dik, то доцільно замінити шлях i ® k шляхом i ® j ® k. Така заміна (далі її будемо умовно називати трикутним оператором) виконується автоматично в процесі виконання алгоритму Флойда.

Рисунок 2.1 - Трикутний оператор

Алгоритм Флойда-Уоршалла вимагає виконання наступних дій.

Крок 0. Визначаємо початкову матрицю відстаней D0 і матрицю послідовності вузлів S0. Діагональні елементи обох матриць позначаються знаком ''- '', що показує, що ці елементи в обчисленнях не беруть участь. Думаємо k = 1.

Основний крок k. Задаємо рядок k і стовпець k як ведучий рядок і ведучий стовпець. Розглядаємо можливість застосування трикутного оператора до всіх елементів dij матриці Dk-1. Якщо виконується нерівність dik+dkj<dij, (i≠k,j¹k і i¹j), тоді виконуємо наступні дії:) створюємо матрицю Dk шляхом заміни в матриці Dk-1 елемента dij на суму dik+dkj,

б) створюємо матрицю Sk шляхом заміни в матриці Sk-1 елемента sij на k. Думаємо k=k+1 і повторюємо крок k.

Після реалізації n кроків алгоритму визначення по матрицях Dn і Sn найкоротшого шляху між вузлами i і j виконується за наступними правилами.

. Відстань між вузлами i і j дорівнює елементові dij у матриці Dn.

. Проміжні вузли шляху від вузла i до вузла j визначаємо по матриці Sn. Нехай sij=k, тоді маємо шлях i-k-j. Якщо далі sik=k і skj=j, тоді вважаємо, що весь шлях визначений, тому що знайдені всі проміжні вузли. У противному випадку повторюємо описану процедуру для шляхів від вузла i до вузла k і від вузла k до вузла j.

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

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

3. Програмна реалізація алгоритмів

.1 Огляд можливостей мови програмування

Середовище виконання (runtime) було завжди присутнє в Visual Basic, тому наступне твердження спочатку виглядає декілька дивно. Отже, одним з найсерйозніших нововведень VB.NET являється наявність середовища виконання CLR (Common Language Runtime), загального для усіх мов .NET. Хоча на перший погляд CLR нагадує звичайну бібліотеку часу виконання на кшталт бібліотеки С MSVCRTXX.DLL, бібліотека VB MSVBVMXX.DLL має значно великі розміри і має набагато більші можливості. З цієї причини написання програм, повною мірою використовуючих CLR, більше схожий на програмування для API нової операційної системи Проте, можливості бібліотеки класів .NET Framework настільки широкі, що вам практично не доведеться використовувати функції API.

Наступне принципове нововведення - загальний формат виконуваного коду .NET, так званий Microsoft Intermediate Language (проміжна мова Microsoft), MSIL або просто IL Він є кодом, що частково відкомпілювався, перетворюється в машинний код середовищем .NET під час виконання. Перед нами принципове удосконалення схеми, що існувала в усіх версіях VB до версії 5. Раніше додатка VB компілювалися в Р-код (псевдокод, машинна мова абстрактної машини), свого роду проміжне представлення остаточного виконуваного коду.

Механізм часу виконання інтерпретував Р-код при запуску програми користувачем. Користувачі постійно скаржилися на погану швидкодію і прохали Microsoft включити в VB підтримку компіляції в машинний код. Починаючи з версії 5 з'явилася можливість вибору між компактним Р-кодом і машинним (native) кодом, який займав більше місця, але теоретично швидше працював.

У мовах .NET переваги Р-коду об'єдналися з перевагами компільованих мов. Спочатку програма, написана на будь-якій мові, компілюється в IL (віддалений аналог Р-коду), а потім отриманий IL -код перетвориться в машинний код. Подібна двокрокова схема відносно легко забезпечує міжмовну сумісність, а підсумкове використання машинного коду забезпечує хорошу швидкодію.

Об'єктно-орієнтовані засоби VB5 і VB6 були, м'яко кажучи, обмеженими. Зокрема, ці версії VB не дозволяли автоматично ініціалізувати дані класу при створенні екземпляра. В результаті об'єкт створювався в невизначеному стані, що підвищувало вірогідність помилок і примушувало програміста приймати додаткові заходи обережності при роботі з об'єктами. Для вирішення цієї проблеми в VB.NET з'явилися конструктори, що параметризувалися.

Іншим недоліком була відсутність повноцінного спадкоємства. Спадкоємством називається особлива форма багатократного використання кода, при якій програміст визначає нові об'єкти на базі існуючих об'єктів. Спадкоємство дуже добре підходить для таких завдань, як створення нового текстового поля з розширеними можливостями на підставі стандартного текстового поля. У VB версій 5 і 6 спадкоємство не підтримувалося, тому для побудови поліпшеного текстового поля доводилося удаватися до послуг незручної і ненадійної програми-майстри (wizard).

Розглянемо інший приклад, в якому було б доречне спадкоємство, - створення класів для роботи із спеціалізованими колекціями. Щоб створити колекцію, що спеціалізувалася на зберіганні строкових даних, в VB5 і 6 в клас включалося закрите поле:mCollection As Collection

У обробниках подій Initialize і Terminate відбувалося виділення і звільнення пам'яті, використовуваною закритою колекцією. Потім програмувалися методи спеціалізованої колекції, призначені для зовнішнього використання. Більшість таких методів зводилися до простого виклику відповідного методу закритої колекції, наприклад:Add(Item As String).Add ItemSub

Але найосоружніше починалося у тому випадку, якщо вміст колекції вимагалося перебирати в циклі For Each. Для цього в модуль класу доводилося включати фрагменти виду:Function NewEnum As lUnknownNewEnum = mCollection.[_NewEnum]Function

Але і це не усе - цій функції слід було присвоїти ідентифікатор! Принцип "абракадабра - дістаємо з капелюха кролика"! хороший для фокусника, але не для програміста. При використанні спадкоємства уся ця нісенітниця не потрібна. У VB.NET досить написати:MyCollectionCollection

...і ви отримуєте автоматичну підтримку For Each.

У програмістів, що працюють на Visual Basic, завжди виникали проблеми з витоком пам'яті із-за так званих циклічних посилань (ситуація, при якій об'єкт А посилається на об'єкт В, а об'єкт В посилається на об'єкт А). Якщо поява циклічних посилань була обумовлена логікою програми, компілятор VB не розпізнавав їх, внаслідок чого пам'ять, займана цими об'єктами, не звільнялася.

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

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

Простір імен System.Collections бібліотеки .NET Framework містить інтерфейси і класи, які визначають різні колекції об'єктів, такі як списки, черги, двійкові масиви, хэш-таблицы і словники. Колекції настільки важливі, що вони за умовчанням автоматично імпортуються в кожне рішення VB .NET.

В сукупності ці класи залишають далеко позаду примітивний клас Collection з VB6. Найкорисніші класи колекцій перераховані в таблиці 3.1.

Детальніше розглянемо основні принципи роботи з двома найважливішими класами: ArrayList і HashTable.

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

Таблиця 3.1 - Основні класси коллекций