Алгоритми сортування пошуку найкоротшого шляху в графі та пошуку покриття близького до найкоротшому

Зміст

Введення

1 Вибір варіанта завдання

2 Алгоритм сортування Шейкер

2.1 Математичне опис завдання

2.2 Словесне опис алгоритму і його роботи

2.3 Опис схеми алгоритму

2.4 Контрольний приклад

3 Алгоритм покриття: побудова одного найкоротшого покриття

3.1 Математичне опис завдання

3.2 Словесне опис алгоритму і його роботи

3.3 Опис схеми алгоритму

3.4 Контрольний приклад

4 Алгоритм на графах: знаходження найкоротшого шляху

4.1 Математичне опис завдання

4.2 Словесне опис алгоритму і його роботи

4.3 Опис схеми алгоритму

4.4 Контрольний приклад

Висновок

Перелік літератури

Введення

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

Як зауважив Кнут: «Алгоритм повинен бути визначений настільки чітко, щоб його вказівкам міг слідувати навіть комп'ютер».

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

Ефективність алгоритму визначається аналізом, який повинен дати чітке уявлення, по-перше, про ємнісний і, по-друге, про часової складності процесу.

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

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

1. ВИБІР ВАРІАНТА

Номер варіанту визначається знаходженням залишку від цілочисельного ділення числа У, яке є сумою числа Х і номери за списком у журналі. Номер за списком у журналі N = 9. Таким чином:

X = N гр * 100 = 5 * 100 = 500;

Y = N + X = 9 +500 = 509.

За формулами знаходжу відповідні види алгоритмів.

1) (Y mod 4) + 1 = (509 mod 4) + 1 = 1 + 1 = 2; Алгоритм покриття: побудова одного найкоротшого покриття.

2) (Y mod 6) + 1 = (509 mod 6) + 1 = 5 + 1 = 6; Алгоритм на графах: пошук найкоротшого шляху.

3) (Y mod 5) + 1 = (509 mod 5) +1 = 4 + 1 = 5; Алгоритм сортування: сортувати-шейкер.

2 АЛГОРИТМ СОРТУВАННЯ: СОРТУВАННЯ Шейкер

2.1 Математичне опис завдання

Сортування - це перестановка елементів деякої множини в заданому порядку при деякій впорядкує функцію.

Сортування використовується для полегшення пошуку елемента в такому відсортованому множині.

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

2.2 Словесне опис алгоритму і його роботи

Сортування Шейкер є вдосконаленою сортуванням методом бульбашки. Ідея методу: крок сортування полягає в проході знизу вгору по масиву. По дорозі проглядаються пари сусідніх елементів. Якщо елементи деякої пари знаходяться в неправильному порядку, то міняємо їх місцями. (Див. Таб. 1)

Таблиця 1

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

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

Тим не менш, у нього є величезний плюс: він простий і його можна по-всякому покращувати. Чим ми зараз і займемося. По-перше, розглянемо ситуацію, коли на якому-небудь з проходів не відбулося жодного обміну. Що це означає? Це означає, що всі пари розташовані в правильному порядку, так що масив вже відсортований. І продовжувати процес не має сенсу (особливо, якщо масив був відсортований з самого початку!). Отже, перше поліпшення алгоритму полягає в запам'ятовуванні, виконувався на даному проході будь-якої обмін. Якщо ні - алгоритм закінчує роботу. Процес поліпшення можна продовжити, якщо запам'ятовувати не тільки сам факт обміну, але й індекс останнього обміну k. Справді: всі пари сусіди елементів з індексами, меншими k, вже розташовані в потрібному порядку. Подальші проходи можна закінчувати на індексі k, замість того щоб рухатися до встановленої заздалегідь верхньої межі i.

Якісно інше поліпшення алгоритму можна отримати з наступного спостереження. Хоча легкий пляшечку знизу підніметься вгору за один прохід, важкі бульбашки опускаються зі мінімальною швидкістю: один крок за ітерацію. Так що масив 2 3 4 5 6 1 буде відсортований за 1 прохід, а сортування послідовності 6 1 2 3 4 5 зажадає 5 проходів.

Щоб уникнути подібного ефекту, можна змінювати напрямок наступних один за іншим проходів. Одержаний алгоритм називають "шейкер-сортуванням". Далі проведена програма на мові С + +, що реалізує сортування Шейкер.

template <class T>

void shakerSort (T a [], long size) {

long j, k = size -1;

long lb = 1, ub = size-1; / / межі невідсортованої частині масиву

T x;

do {

/ / Прохід знизу вгору

for (j = ub; j> 0; j -) {

if (a [j-1]> a [j]) {

x = a [j-1]; a [j-1] = a [j]; a [j] = x;

k = j;

}

}

lb = k +1;

/ / Прохід зверху вниз

for (j = 1; j <= ub; j + +) {

if (a [j-1]> a [j]) {

x = a [j-1]; a [j-1] = a [j]; a [j] = x;

k = j;

}

}

ub = k-1;

} While (lb <ub);

}

Наскільки описані зміни вплинули на ефективність методу? Середня кількість порівнянь, хоч і зменшилася, але залишається O (n ^2), в той час як число обмінів не змінилося взагалі ніяк. Середнє (воно ж найгірше) кількість операцій залишається квадратичним, кількість зайвих подвійних перевірок скоротилася.

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

На практиці метод бульбашки, навіть з поліпшеннями, працює, на жаль, занадто повільно. А тому - майже не застосовується.

2.3 Опис схеми алгоритму

Алгоритми сортування дуже сильно залежать від структури даних .. У даній роботі розглядається сортування масивів. Тип даних «масив» зручний тим, що зберігається у внутрішній пам'яті і має випадковий доступ до елементів, то є більш швидкий, ніж у послідовності. Тому масиви доцільно використовувати для зберігання невеликих, часто використовуваних множин

З вище сказаного випливає, що в процесі роботи будуть потрібні наступні змінні:

n - кількість елементів масиву;

A - сортований масив;

j - змінна;

x - i-й ключ (переносимий елемент);

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

l - номер останнього обміну при перегляді вхідної послідовності праворуч -

наліво.

Всі змінні цілого типу.

Опис схеми алгоритму. Блок-схема даного алгоритму зображена на рис. 1 в Додатку.

Алгоритм працює наступним чином. Спочатку вводяться вихідні дані: довжина масиву та його елементи (блок 1, 2), потім організується цикл по всій довжині масиву, під час якого (блоки 3 -7) і проводиться порівняння елементів а [j -1]> a [j] і їх обмін при проході справа-наліво. Номер останнього обміну l запам'ятовується. Далі організовується цикл, в якому проводиться перевірка умови а [j -1]> a [j] при проході масиву зліва-направо (блоки 8 - 12).

2.4 Контрольний приклад

Розглянемо приклад роботи алгоритму сортування Шейкер.

Задано масив A, що складається з 8 елементів: 44, 55, 12, 42, 94, 18, ​​6, 67.

Крок 1. L = 2, r = 8

Таблиця 2

1. j = r = 8

2. A [7] <A [8], j = j -1 = 7

3. A [6]> A [7], x = 18, A [6] = 6, A [7] = x = 18 ; J = 6

4. A [5]> A [6], A [5] = 6, A [6] = 94

5. A [4]> A [5], A [4] = 6, A [5] = 42

6. A [3]> A [4], A [3] = 6, A [4] = 12

7. A [2]> A [3], A [2] = 6, A [3] = 55

8. A [1]> A [2], A [1] = 6, A [2] = 44

9. l = 3.

Крок 2. A [7] <A [8], j = j -1 = 7

1) A [1]> A [2]; j = 6

2) A [2]> A [3], A [1] =, A [2] = 44, j = 4

3) A [3]> A [4], A [2] = 6, A [3] = 12, j = 5

4) A [4]> A [5], A [3] = 6, A [4] = 12, j = 6

5) A [5]> A [6], j = 7

6) A [6]> A [7], A [5] = 6, A [6] = 18, j = 8

7) r = 7.

Крок 3.

1. A [7]> А [8], j = j -1 = 7

2. A [6]> A [7], x = 18, A [6] = 6, A [7] = x = 18 ; J = 6

3. A [5]> A [6], A [5] = 6, A [6] = 94; j = 5

4. A [4]> A [5], A [4] = 6, A [5] = 42; j = 4

5. A [3]> A [4], A [3] = 6, A [4] = 12; j = 3

6. A [2]> A [3], A [2] = 6, A [3] = 55; j = 2

7. A [1]> A [2], A [1] = 6, A [2] = 44; j = 1

8. l = 3.

Крок 4.

1) A [1]> A [2], x = 18, A [6] = 6, A [7] = x = 18 ; J = 6

2) A [2]> A [3], A [1] =, A [2] = 94, j = 4

3) A [3]> A [4], A [2] = 6, A [3] = 42, j = 5

4) A [4]> A [5], A [3] = 6, A [4] = 12, j = 6

5) A [5]> A [6], j = 7

6) A [6]> A [7], A [5] = 6, A [6] = 44, j = 8,

7) r = 7. → кінець алгоритму.

Таким чином, ми отримали вихідний масив, відсортований методом Шейкер:

6, 12, 18, ​​42, 44, 55, 67, 94.

3 АЛГОРИТМ ПОКРИТТЯ: ПОБУДОВА ОДНОГО НАЙКОРОТШИЙ ПОКРИТТЯ

3.1 Математичне опис завдання і методів її рішення

Нехай -Опорна множина. Є безліч

підмножин множини B ( ). Кожному підмножині зіставлять число , Званої ціною. Безліч називається рішенням задачі про покриття, або просто покриттям, якщо виконується умова , При цьому ціна . Термін «покриття» означає, що сукупність множин містить всі елементи множини В, тобто «Покриває» безліч B

Безізбиточним називається покриття, якщо при видаленні з нього хоча б одного елемента воно перестає бути покриттям. Інакше - покриття надлишково.

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

Покриття Р називається найкоротшим, якщо l - найменше серед всіх покриттів даної задачі.

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

А:

Нулі в матриці T не проставляються.

Є такі варіанти формулювання завдання про покриття:

1. Потрібно знайти всі покриття. Для вирішення завдання необхідно виконати повний перебір всіх підмножин множини А.

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

Потрібно знайти одне безізбиточное покриття. Рішення завдання грунтується на скороченні таблиці.

Завдання про покриття можуть бути вирішені точно (при невеликій розмірності) або наближено (див. [2]).

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

1) Алгоритм повного перебору. (Заснований на методі впорядкування перебору підмножин множини А).

2) Алгоритм граничного перебору по увігнутому безлічі. (Заснований на однойменному методі скорочення перебору).

3) Алгоритм розкладання по стовпцю таблиці покриття. Заснований на методі скорочення перебору, який полягає в розгляді тільки тих рядків таблиці покриття, в яких є "1" в обраному для розкладання стовпці.

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

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

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

3.2 Словесне опис алгоритму і його роботи

0) Вважаємо вихідну таблицю покриттів поточної, а безліч ядерних рядків - порожнім.

1) Знаходимо ядерні рядки, запам'ятовуємо безліч ядерних рядків. Поточну таблицю покриттів скорочуємо, викреслюючи ядерні рядка і всі стовпці, покриті ними.

2) викреслюємо антиядерні рядка.

3) викреслюємо поглинають стовпці.

4) викреслюємо поглинаються рядка.

5) Якщо в результаті виконання пунктів з 1 по 4 поточна таблиця покриттів змінилася, знову виконуємо пункт 1, інакше перетворення закінчуємо.

Тому алгоритм роботи наступний:

1) введення числа рядків і стовпців таблиці покриття;

2) введення таблиці покриття;

3) пошук ядерних рядків. Якщо їх немає, то п.4. Інакше, запам'ятовуємо ці ядерні рядка. Шукаємо стовпці, вкриті ядерними рядками. Викреслюємо всі ядерні рядки і стовпці, покриті ними.

4) викреслення антиядерних рядків. Перехід у п.5.

6) викреслення поглинаючих стовпців.

7) викреслення поглинаються рядків.

8) якщо в результаті перетворень таблиця покриттів змінилася, виконуємо пункт 3. Інакше - висновок безлічі покриття, кінець алгоритму.

3.3 Вибір структур даних

З аналізу задачі та її даних видно, що алгоритм повинен працювати з таблицею покриття і з деякими змінними, які представлені нижче (всі змінні цілого типу):

m - кількість рядків таблиці покриття;

n - кількість стовпців таблиці покриття;

i, j - змінні циклу по рядках і стовпцях відповідно;

S _prev - попередня сума стовпця або рядка;

S _curr - поточна сума стовпця або рядка.

Таблиця покриття - це двовимірна матриця. Її доцільно представити у вигляді двовимірного масиву A (m, n).

P - одномірний масив для зберігання номерів рядків, що покривають матрицю. Для зберігання номерів обраний масив, оскільки кількість рядків, хоча й невідомо заздалегідь, обмежена кількістю рядків матриці покриття (m).

3.4 Опис схеми алгоритму

Блок-схема даного алгоритму зображена на рис. 3 в Додатку.

Спочатку вводяться вихідні дані: розмірність таблиці m і n і сама таблиця покриття (блок 1). Далі відбувається пошук пустого стовпця (блок 2): це доцільно, оскільки, якщо хоча б один стовпець не покритий, то й не існує покриття цієї таблиці, і, отже, кінець алгоритму. Далі, якщо не знайдено порожнього стовпця (перевірка в блоці 3), - пошук ядерних рядків (блок 4), після-стовпців, покритих ними (блок 5). Після цього викреслюються всі стовпці і рядки, знайдені в блоках 4,5 (блок 6). Викреслюються антиядерні рядка (блок 7). Викреслюються поглинають стовпці (блок 8). Викреслюються поглинаються рядка (блок 9). Якщо в результаті виконання блоків 6-9 поточна таблиця покриттів змінилася, то виконується блок 4; інакше випливає висновок знайденого найкоротшого покриття у вигляді номерів рядків, що покривають таблицю. Потім кінець алгоритму.

3.5 Підпрограми основного алгоритму

Функція MOJNO _ LI (A) веде пошук порожніх стовпців, тобто не покриваються ні одним рядком. Блок-схема цієї функції представлена ​​на рис. 3.1 Програми. Організовується цикл по всіх стовпцях (блоки 1-6). У кожному стовпці йде рахунок нулів (лічильник l ініціалізується в кожному проході - блок 2; рахунок ведеться в блоці 5), тобто якщо зустрічається хоча б одна одиниця (перевірка в блоці 3), то відбувається перехід у наступний стовпець. Алгоритм працює до тих пір, поки не буде досягнутий кінець таблиці (тобто кінець циклу по j, блок6) або поки не буде пораховано m нулів в одному стовпці (перевірка умови в блоці 4), тобто l = m. Функція повертає 0, якщо знайдено m нулів, і 1, якщо досягнуто кінець таблиці.

Функція YAD - LINE (A) веде пошук ядерних рядків .. У блоці 1 S ініціалізується значенням 0. Далі організовується цикл по всіх стовпцях (блок 2). Обнуляємо поточну суму (блок 4) і вважаємо суму в j-му стовпці (цикл у блоках 5-7 і власне підсумовування елементів у блоці 6). Далі порівнюємо отриману суму S з 1 (блок 8). Якщо поточна сума дорівнює 1, запам'ятовуємо її і номеру цього стовпця присвоюємо 0 (блок 9. Таким чином, після закінчення циклу по j у змінній yad _ line (A) буде зберігається масив ядерних рядків. Блок-схема даного алгоритму зображена на рис. 3.2 в Додатку.

Функція ANTI _ LINE веде пошук антиядерних рядків. Змінної S 2 присвоюється значення 0. Організовується цикл по рядках. Шукається сума кожного рядка і якщо вона дорівнює 0, то рядок викреслюється. Якщо ні, то переходимо до наступного рядка. Блок-схема даного алгоритму зображена на рис. 3.3 у Додатку.

Процедура ERASE (A) реалізує викреслювання стовпців, покритих ядерними рядками. Аналогічно дана процедура працює і для самих ядерних рядків, і для антиядерних рядків, поглинаючих стовпців, що поглинаються рядків. Щоб даний стовпець (рядок) «викреслити», необхідно поставити 1 на його (її) перетині з нульовою рядком (стовпчиком). Блок-схема даного алгоритму зображена на рис. 3.4 у Додатку.

Процедура VIVOD (P) реалізує висновок отриманого безлічі рядків з масиву P. Для цього організується цикл за елементами масиву Р (блоки 1-4), в якому перевіряється відзначений чи номер рядка i одиницею (блок 2). Якщо так, то виводиться номер рядка i (блок 3). Блок-схема даного алгоритму зображена на рис. 3.5 в Додатку.

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

Нехай задана таблиця покриттів (див. Таб. 3). Розглянемо приклад роботи алгоритму.

1. Безліч ядерних рядків пусте.

2. Безліч антиядерних рядків пусте.

3. Викреслюємо стовпці В1, В3, В5, В6 як поглинаючі

4. Викреслюємо рядок А2 як поглинену.

Тепер таблиця покриттів буде мати вигляд

(Див. Таб .4)

Таб. 4.

1. Безліч ядерних рядків Р = {A 3, A 4}.

2. Безліч антиядерних рядків А = {А1}.

3. Безліч поглинаючих стовпців пусте.

4. Безліч поглинаються рядків пусте.

Тепер таблиця покриттів прийме вигляд (див. Таб 5)

Таким чином найкоротший покриття {A 3, A 4} Таб. 5.

4 АЛГОРИТМ Знаходження найкоротшого шляху в графі

4.1 Математичне опис завдання і методів її рішення

Графом (G, X) називається сукупність двох кінцевих множин: множини точок, які називаються вершинами (X = {Х ₁ ,..., Х _n}), і безлічі зв'язків у парах вершин, які називаються дугами, або ребрами ((Х _i, Х _j) Î G) в залежності від наявності або відсутності спрямованості зв'язку.

Ребром називаються дві зустрічні дуги (Х _i, Х _j) і (Х _j, Х _i). На графі вони зображуються однією лінією без стрілки. Ребро, або дуга, кінцеві вершини якого збігаються, називається петлею.

Якщо на кожному ребрі задається напрямок, то граф (G, Х) називається орієнтованим. В іншому випадку граф називається неорієнтованим.

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

Матрицею інцидентності називається прямокутна матриця із кількістю рядків, що дорівнює кількості вершин графа, і з кількістю стовпців, що дорівнює кількості ребер (дуг) графа. Елементи матриці а задаються наступним чином: "1" ставиться у випадку якщо вершина v _i, инцидентна ребру u _j; "0" - в іншому випадку.

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

Шлях з початкової вершини х _н до кінцевої вершині х _до - послідовність дуг, що починається у вершині х _н Î Х, що закінчується у вершині х _до Î Х, і така, що кінець черговий дуги є початком наступної:

(Х _н, х _{i 1)} (х _{i 1,} х _{i 2)} (х _{i 2} ... х _ik) (х _ik, x _k) = (x _н, х _к).

Елементарний шлях - шлях, в якому вершини не повторюються.

Простий шлях - шлях, в якому дуги не повторюються.

Маршрут - послідовність ребер, що складають, як і шлях, ланцюжок.

Довжина шляху зваженого графа визначається як сума ваг - його дуг. Якщо граф не зважений, то можна вважати ваги дуг рівними 1.

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

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

4.2 Словесне опис алгоритму і його роботи

0. Ініціалізація найкоротших шляхів від вершини s до кожної вершини графа ∞, а всі вершини 0, v = s.

1. Для кожної вершини u, суміжній v, перевіряємо, відзначена вона і яка довжина шляху між u і v. Якщо менше, то запам'ятовуємо довжину шляху і поточну вершину u.

2. T = ∞, v = 0. Для кожної вершини графа перевіряємо, відзначена вона, і чи менше чи шлях від неї до s, ніж t. Якщо так, то запам'ятовуємо її v = u, і її шлях t = T [u].

3. Якщо v = 0, то шляху немає, інакше якщо v = f, то шлях знайдений і кінець алгоритму.

4. Позначаємо вершину v. Перехід в п.1.

4.3 Вибір структур даних

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

З: array [1 .. p, 1 .. p].

Використовуються такі змінні і масиви:

s, f - вершини, між якими слід знайти найкоротший шлях;

u, v - змінні циклів по вершинах;

T: array [1 .. p] of real - вектор, якщо вершина v лежить на найкоротшому шляху від s до t, то T [v] - довжина найкоротшого шляху від s до v;

H: array [1 .. p] of 0 .. p - вектор, H [v] - вершина, безпосередньо попередня v на найкоротшому шляху;

X: array [1 .. p] of 0 .. 1 - вектор відміток.

4.4 Опис схеми алгоритму

Блок-схема даного алгоритму зображена на рис. 4 в Додатку.

У блоці 1 відбувається введення графа у формі матриці довжин дуг, а також номерів вершин s і f. Далі організовується цикл по вершинах графа (блок 2). У ньому не започатковано масив найкоротших шляхів і масив міток (блок 3): оскільки шляху не відомі, то вони не започатковано нескінченністю, а мітки - нулем. Далі відзначається вершина s, найкоротший шлях від неї до неї ж самої дорівнює 0, і їй ніхто не передує; поточної вершиною v стає s (блок 5). Далі організовується цикл по суміжних з поточною вершин (блок 6). У блоці 7 відбувається перевірка суміжні Чи вершини. У блоці 8 порівнюється вже наявний шлях з шляхом між u і v. Якщо поточний менше, то він і номер вершини запам'ятовуються (блок 9).

В інших блоках відбувається пошук кінця найкоротшого шляху. Спочатку його довжина не відома (дорівнює ∞), і вершина, закінчую його також не відома (блок 11). У блоці 12 організується цикл по всіх невідміченим вершин. У блоці 13 проводитися порівняння вже наявного найкоротшого шляху t з поточним T [u]. Якщо поточний менше, то запам'ятовуємо його і вершину (блок 14). Далі проводиться аналіз отриманого кінця шляху. Якщо v = 0 (блок 16), то не була знайдена вершина кінця найкоротшого шляху, і, отже, немає такого шляху (блок 17). Якщо ж v = f (блок 18), тобто кінець збігається із заданою вершиною, то між ними існує найкоротший шлях (блок 19). В обох випадках кінець алгоритму.

Якщо ж не досягне потрібної вершина f, то поточна вершина v позначається (блок 20) і перехід до блоку 6.

Алгоритм працює, поки не буде вершина t або поки не стане ясно, що шляхи з s в f немає.

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

Нехай заданий граф, зображений на рис. 1. Розглянемо на цьому прикладі роботу алгоритму.

0. for v = 1 .. p

T [v] = ∞;

X [v] = 0;

H [s] = 0;

T [s] = 0;

X [s] = 1;

v = s;

1. X2 € G (1) →

X [2] = 0 & (∞> 0 +4) →

T [2] = T [1] + C [1,2] = 4;

H [2] = 1;

X3 € G (1) →

X [3] = 0 & (∞> 0 +5) →

T [3] = T [1] + C [1,3] = 5;

H [3] = 1;

2. t = ∞; v = 0;

for u = 1 .. p

X [2] = 0 & T [2] = 4 <∞ →

v = 2; t = T [2] = 4;

X [3] = 0 & T [3] = 5! <∞

3. v = 2 ≠ 0;

v = 2 ≠ f = 6;

4. X [2] = 1 → п .1;

1. X4 € G (2) →

X [4] = 0 & (∞> 0 +2) →

T [4] = T [2] + C [2,4] = 6;

H [4] = 2;

2. t = ∞; v = 0;

for u = 1 .. p

X [4] = 0 & T [4] = 6 <∞ →

v = 4; t = T [4] = 6;

3. v = 4 ≠ 0;

v = 4 ≠ f = 6;

4. X [4] = 1 → п .1;

1. X3 € G (4) →

X [3] = 0 & (5!> 6 +3)

X5 € G (4) →

X [5] = 0 & (∞> 0 +7) →

T [5] = T [4] + C [4,5] = 13;

H [5] = 4;

X6 € G (4) →

X [6] = 0 & (∞> 0 +1) →

T [6] = T [4] + C [4,6] = 7;

H [6] = 4;

2. t = ∞; v = 0;

for u = 1 .. p

X [3] = 0 & T [3] = 5 <∞ →

v = 3; t = T [3] = 5;

X [5] = 0 & T [5] = 13! <5

X [6] = 0 & T [6] = 1 <5 →

v = 5; t = T [5] = 7;

3. V = 6 ≠ 0;

v = 6 = f = 6; → кінець алгоритму.

ВИСНОВОК

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

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

Розглянуто складність кожного алгоритму, її залежність від умов даної задачі, методи спрощення і полегшення розуміння алгоритму.

ЛІТЕРАТУР А

1. Вірт Н. Алгоритми і структури даних. - С.-П.: Невський діалект, 2001. - 350 с.

2. Новіков Ф.А. Дискретна математика для програмістів. - С.-П.: Пітер, 2003.-292 с.

3. Шендрик Є.В. Конспект лекцій з дисципліни «Теорія алгоритмів». - Одеса, 2003.