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

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

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

Ще одним варіантом циклу є цикл, який задає виконання певної операції для об’єктів з заданого множини, без явної вказівки порядку перерахування цих об’єктів. Такі цикли називаються спільними (а також циклами по колекції, циклами перегляду) і являють собою формальний запис інструкції виду: «Виконати операцію X для всіх елементів, що входять в безліч M». Спільний цикл, теоретично, ніяк не визначає, в якому порядку операція буде застосовуватися до елементів множини, хоча певні мови програмування, зрозуміло, можуть задавати конкретний порядок перебору елементів. Довільність дає можливість оптимізації виконання циклу за рахунок організації доступу не в заданому програмістом, а в найбільш вигідному порядку. При наявності можливості паралельного виконання декількох операцій можливо навіть паралельне виконання спільного циклу, коли одна й та сама операція одночасно виконується на різних обчислювальних модулях для різних об’єктів, при тому що логічно програма залишається послідовною.

Спільні цикли є в деяких мовах програмування (VB.Net, C #, Java, JavaScript, Perl, Python, PHP, LISP, Tcl та ін) - вони дозволяють виконувати цикл по всім елементам заданої колекції об’єктів. У визначенні такого циклу потрібно вказати тільки колекцію об’єктів та змінну, якій в тілі циклу буде присвоєно значення об’єкту, який в даний момент обробляється (або посилання на нього). Синтаксис в різних мовах програмування синтаксис оператора різний, але в мові VB.Net мае наступний синтаксис:Each element [ As datatype ] In group

[ statements ]

[ Exit For ]

[ statements ][ element ]

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

Оператори, які виконують роль розгалуження програми на підставі якої-небудь умови, називаються операторами умовного переходу.

Найпростішими операторами умовного переходу є оператори Ifумова Then [ Оператори 1 ] [ Else [ Оператори 2 ] ]

Умовою завжди має бути логічний вираз (тобто результат якого або true або false). Після ключового слова Then пишуться оператори, які виконуються, якщо умова істинна, після ключового слова Else пишуться оператори, які виконуються, якщо умова хибна. Частина else є необов’язковою, якщо вона відсутня, то якщо умова хибна, буде виконуватися наступний за if оператор.

Виходячи з поставлених вимог для розробки модуля реалізації алгоритмів на графах з візуалізацією етапів розробки доцільно для розробки використати Object-технологію - інтерфейс користувача розробити в середовищі програмування Visual Studio 2010, використовуючи мову програмування Visual Basic .Net.

Платформа Microsoft. NET надає:

      Стійке середовище виконання CLR (Common Language Runtime), яке входить до складу даної платформи;

      Засоби розробки додатків на будь-якій з багатьох мов програмування, що підтримуються платформою.NET;

      Величезну бібліотеку класів NET Framework, що лежить в основі відкритої моделі програмування. Вони доступні в будь-якій мові програмування, що підтримується платформою.NET;

      Підтримку мережевої інфраструктури, побудованої на верхньому рівні стандартів Internet, внаслідок чого забезпечується високий рівень взаємодії між додатками;

      Підтримку нового промислового стандарту, а саме технології Web-служб. Технологія Web-служб надає новий механізм створення розподілених додатків. По суті, вона є поширенням технології створення додатків на базі компонентів і на сферу Internet;

      Модель безпеки, що програмісти можуть легко використовувати у своїх програмах;

      Потужні інструментальні засоби розробки.

2. Основні алгоритми на графах

.1 Пошук завширшки

Пошук завширшки (breadth-first search)є одним з простих алгоритмів для обходу графа і є основою для багатьох важливих алгоритмів для роботи з графами. Наприклад, алгоритм Прима (Prim) пошуку мінімального остовного дерева або алгоритм Дейкстры (Dijkstra) пошуку найкоротшого шляху з однієї вершини використовують ідеї, схожі з ідеями, використовуваними при пошуку завширшки.

Пошук завширшки був формально запропонований Э. Ф. Муром в контексті пошуку шляху в лабіринті. Лі незалежно відкрив той же алгоритм в контексті розводки провідників на друкованих платах.

Пошук завширшки може застосовуватися для вирішення завдань, пов'язаних з теорією графів, :

хвилевий алгоритм пошуку шляху в лабіринті (алгоритм Лі);

хвилеве трасування друкованих плат;

пошук компонент зв'язності в графі;

пошук найкоротшого шляху між двома вузлами незваженого графа;

пошук в просторі станів: знаходження рішення задачі з найменшим числом ходів, якщо кожен стан системи можна представити вершиною графа, а переходи з одного стану в інше - ребрами графа;

знаходження найкоротшого циклу в орієнтованому незваженому графові;

знаходження усіх вершин і ребер, що лежать на якому-небудь найкоротшому шляху між двома вершинами a і b;

пошук збільшуючого шляху в алгоритмі Форда-Фалкерсона (алгоритм Едмондса-Карпа).

Нехай заданий граф G = (V, Е) і виділена початкова (source) вершина s. Алгоритм пошуку завширшки систематично обходить усі ребра G для "відкриття" усіх вершин, досяжних з s, обчислюючи при цьому відстань (мінімальну кількість ребер) від s до кожної досяжної з s вершини. Крім того, в процесі обходу будується "дерево пошуку завширшки" з коренем s, що містить усі досяжні вершини. Для кожної досяжної з s вершини v шлях в дереві пошуку завширшки відповідає найкоротшому (тобто що містить найменшу кількість ребер) шляху від s до v в G. Алгоритм працює як для орієнтованих, так і для неорієнтованих графів.

Пошук завширшки має таку назву тому, що в процесі обходу ми йдемо вшир, тобто перш ніж приступити до пошуку вершин на відстані k +1, виконується обхід усіх вершин на відстані k.

Для відстежування роботи алгоритму пошук завширшки розфарбовує вершини графа в білий, сірий і чорний кольори. Спочатку усі вершини білі, і пізніше вони можуть стати сірими, а потім чорними. Коли вершина відкривається (discovered) в процесі пошуку, вона забарвлюється. Таким чином, сірі і чорні вершини - це вершини, які вже були відкриті, але алгоритм пошуку завширшки по-різному працює з ними, щоб забезпечити оголошений порядок обходу. Якщо  і вершина u чорного кольору, то вершина v або сіра, або чорна, тобто усі вершини, суміжні з чорною, вже відкриті. Сірі вершини можуть мати білих сусідів, будучи межею між відкритими і невідкритими вершинами.

Приведена нижче процедура пошуку завширшки BFS припускає, що вхідний граф G = (V, Е) представлений за допомогою списків суміжності. Крім того, підтримуються додаткові структури даних в кожній вершині графа. Колір кожної вершини u і v зберігається в змінній color [u], а попередник - в змінній π [u]. Якщо попередника у і немає (наприклад, якщо u = s або u не відкрита), то π [u]= NIL. Відстань від s до вершини u, що обчислюється алгоритмом, зберігається в полі d[u]. Алгоритм використовує чергу Q типу FIFO для роботи з множиною сірих вершин

Взагалі черга в програмуванні це динамічна структура даних, що працює за принципом "перший прийшов - перший пішов" (англ. FIFO - first in, first out). У черги є голова (англ. head) та хвіст (англ. tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові. Така черга повністю аналогічна звичній "базарній" черзі, в якій хто перший встав в неї, той першим буде обслуженим (але, на відміну від реальної черги, імовірність пройти поза чергою виключена)

Основні операції з чергою:

 <#"792034.files/image011.jpg">

Процедура BFS працює таким чином. У рядках 1-4 усіх вершини, за винятком початкової вершини s, забарвлюються в білий колір, для кожної вершини u полю d [u] привласнюється значення ∞, а як батько для кожної вершини встановлюється nil. У рядку 5 початкова вершина s забарвлюється в сірий колір, оскільки вона розглядається як відкрита на початку процедури. У рядку 6 її полю привласнюється значення 0, а в рядку 7 її батьком стає nil. У рядках 8-9 створюється порожня черга Q, в яку поміщається один елемент s.

Цикл while в рядках 10-18 виконується до тих пір, поки залишаються сірі вершини (тобто відкриті, але списки суміжності яких ще не проглянуті). Інваріант цього циклу виглядає таким чином: При виконанні перевірки в рядку 10 черга Q складається з множини сірих вершин.

Легко побачити, що він виконується перед першою ітерацією і що кожна ітерація циклу зберігає інваріант. Перед першою ітерацією єдиною сірою вершиною і єдиною вершиною в черзі Q, являється початкова вершина s. У рядку 11 визначається сіра вершина u в голові черги Q, яка потім віддаляється з черги. Цикл for в рядках 12-17 переглядає усі вершини v в списку суміжності u. Якщо вершина v біла, значить, вона ще не відкрита, і алгоритм відкриває її, виконуючи рядки 14-17. Вершині призначається сірий колір, дистанція d [v] встановлюється рівною d[u] + 1, а як її батько вказується вершина u. Після цього вершина поміщається в хвіст черги Q. Після того, як усі вершини із списку суміжності u проглянуті, вершині u привласнюється чорний колір. Інваріант циклу зберігається, оскільки усі вершини, які забарвлюються в сірий колір (рядок 14), вносяться до черги (рядок 17), а вершина, яка віддаляється з черги (рядок 11), забарвлюється в чорний колір (рядок 18).

Результат пошуку завширшки може залежати від порядку перегляду вершин, суміжних з цією вершиною, в рядку 12. Дерево пошуку завширшки може змінюватись, але відстані d, вичислені алгоритмом, не залежать від порядку перегляду.

Оцінимо час роботи алгоритму для вхідного графа G = (V, E). Після ініціалізації жодна вершина не забарвлюється в білий колір, тому перевірка в рядку 13 гарантує, що кожна вершина вноситься до черги не більше одного разу, а отже, і віддаляється з черги вона не більше одного разу. Операції внесення до черги і видалень з неї вимагають O(1) часу, так що загальний час операцій з чергою складає О(V). Оскільки кожен список суміжності сканується тільки при видаленні відповідної вершини з черги, кожен список сканується не більше одного разу. Оскільки сума довжин усіх списків суміжності рівна Θ (Е), загальний час, необхідний для сканування списків, рівний О(Е). Накладні витрати на ініціалізацію рівні О (V), так що загальний час роботи процедури BFS складає Про (V + Е). Таким чином, час пошуку завширшки лінійно залежить від розміру представлення графа G з використанням списків суміжності.

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

.2 Пошук в глибину

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

Як і у разі пошуку завширшки, коли вершина V відкривається в процесі сканування списку суміжності вже відкритої вершини u, процедура пошуку записує цю подію, встановлюючи поле попередника v π[v] рівним u. На відміну від пошуку завширшки, де підграф передування утворює дерево, при пошуку в глибину підграф передування може складатися з декількох дерев, оскільки пошук може виконуватися з декількох початкових вершин.

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

Пошук в глибину також проставляє у вершинах мітки часу (timestamp). Кожна вершина має дві такі мітки - першу d [v], у якій вказується, коли вершина v відкривається (і зафарбовується в сірий колір), і друга - f[v], яка фіксує момент, коли пошук завершує сканування списку суміжності вершини v і вона стає чорною. Ці мітки використовуються багатьма алгоритмами і корисні при розгляді поведінки пошуку в глибину.

Приведена нижче процедура DFS записує в полі d [u момент, коли вершина u відкривається, а в полі f [u] - момент завершення роботи з вершиною u. Ці мітки часу є цілими числами в діапазоні від 1 до 2 |V|, оскільки для кожної з |V| вершин є тільки одна подія відкриття і одне - завершення. Для кожної вершини u виконується співвідношення:

До моменту часу d [u] вершина має колір WHITE, між d[u] і f[u] - колір GRAY, а потім f [u] - колір BLACK.

Далі представлений псевдокод алгоритму пошуку в глибину. Вхідний граф G може бути як орієнтованим, так і неорієнтованим. Змінна time - глобальна і використовується нами для міток часу.

Процедура DFS працює таким чином. У рядках 1-3 усіх вершини забарвлюються в білий колір, а їх поля π ініціалізувалися значенням nil. У рядку 4 виконується скидання глобального лічильника часу. У рядках 5-7 по черзі перевіряються усі вершини з V, і коли виявляється біла вершина, вона оброблюється за допомогою процедури DFS_VISIT. Кожного разу при виклику процедури DFS_Visit(u) в рядку 7, вершина u стає коренем нового дерева лісу пошуку в глибину. При поверненні з процедури DFS кожній вершині u зіставляються два моменти часу - час відкриття (discovery time) d [u] і час завершення (finishing time) f[u].

При кожному виклику DFS_visit(u) вершина u спочатку має білий колір. У рядку 1 вона забарвлюється в сірий колір, в рядку 2 збільшується глобальна змінна time, а в рядку 3 виконується запис нового значення змінній time в полі часу відкриття d[u]. У рядках 4-7 досліджуються усі вершини, суміжні з u, і виконується рекурсивне відвідування білих вершин. При розгляданні в рядку 4 вершини v, суміжною з u, ми говоримо, що ребро (u, v) досліджується (explored) пошуком в глибину. І нарешті, після того, як будуть досліджені усі ребра, що покидають u, в рядках 8-9 вершина і забарвлюється в чорний колір, а в полі f [u] записується час завершення роботи з нею.