Час роботи алгоритму Дейкстри

Складність алгоритму Дейкстри залежить від способу знаходження вершини V, а також способу зберігання множени невідвіданих вершин та способу оновлення міток. Позначимо через N кількість вершин, а через M - кількість ребер у графі G.

· У найпростішому випадку, коли для пошуку вершини з мінімальним D[V] проглядається уся множена вершин, а для зберігання величин D - масив, час роботи алгоритму є O(N ² + M). Основний цикл виконується порядку N разів, в кожному з них на знаходження мінімуму витрачається близько N операцій, плюс кількість змін міток, яка не перевершує кількості ребер у вихідному графі.

· Для розріджених графів (тобто таких, для яких M багато менше N ²) невідвіданих вершини можна зберігати в двійковій купі, а в якості ключа використовувати значення D[і], тоді час вилучення вершини з W стане log N, при тому, що час модифікації D[і] зросте до log N. Так як цикл виконується порядку N разів, а кількість змін міток не більше М, швидкість роботи такої реалізації O(n*log n + m*log n).

· Якщо для зберігання невідвіданих вершин використовувати фібоначчіву купу, для якої видалення відбувається в середньому за O(log n), а зменшення значення в середньому за O(1), то час роботи алгоритму складе O(n*log n + m).

 

Завдання для виконання лабораторної роботи №6.

1. Знайти найкоротшу відстань між містами. Міста представлені у вигляді вершин. Вагою ребер є пряма відстань між двома містами. Граф представлений матрицею суміжності.

2. Знайти шлях найменшого опору для струму в електричній схемі. Вузли схеми - вершини графа. Ваги ребер - опір прямого провідника між двома вузлами. Граф представлений матрицею суміжності.

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

4. Знайти найкоротший шлях з одного маршрутизатора мережі в іншій. Вершини графа - маршрутизатори мережі. Ваги ребер - час на передачу даних з одного маршрутизатора в іншій. Граф представлений матрицею суміжності.

5. Знайти найкоротшу відстань між містами. Міста представлені у вигляді вершин. Ваги ребер є пряме відстань між двома містами. Граф представлений списком суміжності.

6. Знайти шлях найменшого опору для струму в електричній схемі. Вузли схеми - вершини графа. Ваги ребер - опір прямого провідника між двома вузлами. Граф представлений списком суміжності.

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

8. Знайти найкоротший шлях з одного маршрутизатора мережі в іншій. Вершини графа - маршрутизатори мережі. Ваги ребер - час на передачу даних з одного маршрутизатора в іншій. Граф представлений списком суміжності.

9. Знайти найкоротшу відстань між містами. Міста представлені у вигляді вершин. Ваги ребер є пряме відстань між двома містами. Граф представлений матрицею суміжності.

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

11. Знайти шлях найменшого опору для струму в електричній схемі. Вузли схеми - вершини графа. Ваги ребер - опір прямого провідника між двома вузлами. Граф представлений списком суміжності.

12. Знайти найкоротший шлях з одного маршрутизатора мережі в іншій. Вершини графа - маршрутизатори мережі. Ваги ребер - час на передачу даних з одного маршрутизатора в іншій. Граф представлений списком суміжності.

 

Вимоги до звіту:

 

Звіт з лабораторної роботи повинен відповідати наступній структурі:

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

2. Математична модель. У цьому підрозділі вводяться математичні описи фізичних величин і математичний опис їх взаємодій. Мета підрозділу - представити вирішувану задачу в математичній формулюванні.

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

4. Лістинг програми.

5. Контрольний тест. Підрозділ містить набори вихідних даних і отримані в ході виконання програми результати.

6. Висновки з лабораторної роботи.

Лабораторна робота №7

 

Тема: Пошук елемента в відсортованому списку.

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

 

Завдання пошуку.

Нехай задані лінійні списки: список елементів В = <К1, К2, К3,..., Кn> і список ключів V = (у простому випадку це цілі числа). Потрібно для кожного значення Vi з V знайти множену всіх співпадаючих з ним елементів з В. Найчастіше зустрічається ситуація коли V містить один елемент, а в В є не більше одного такого елемента.

Розглянемо такі методи пошуку:

1. бінарний;

2. М-блоковий;

3. Хешування.

 

Бінарний пошук.

Бінарний пошук полягає в тому, що ключ V порівнюється із середнім елементом списку. Якщо ці значення виявляться рівними, то шуканий елемент знайдений, в іншому випадку пошук триває в одній з половин списку.

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

Приклад.

Розглянемо наступну послідовність цілих чисел, відсортованих в порядку зростання. Будемо шукати число 55:

 

1	2	3	4	5	6	7	8	9	10	11

 

Спочатку, простір пошуку містить індекси від 1 до 11. Треба вибрати середнє значення, яке є значення з індексом 6 (середина між 1 і 11): це значення становить 41, і це менше, ніж задане значення. З цього ми робимо висновок, що не тільки елемент з індексом 6 не цільове значення, але також, що жоден елемент на індекси від 1 до 5, не може бути цільовим значенням, оскільки всі елементи на ці показники менше, ніж 41, що менше цільового значення. Це призводить простір пошуку до індексів з 7 по 11:

 

7	8	9	10	11

 

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

 

7	8

 

Залежно від того, як ми вибираємо середній з парного числа елементів, ми або знайдемо 55 в наступному кроці або відрубемо 68, щоб отримати простір пошуку тільки з одного елемента. У кожному разі, ми робимо висновок, що індекс елемента з цільовим значенням знаходиться в 7.

 

М-блоковий пошук.

Цей спосіб зручний при індексному зберіганні списку. Передбачається, що вихідний впорядкований список B довжини N розбитий на M підсписків B1, B2,..., Bm довжини N1, N2,..., Nm, таким чином, що B = B1, B2,.., Bm.

Для знаходження ключа V, потрібно спочатку визначити перший зі списків Bi, i = 1, M, останній елемент якого більше V, а потім застосувати послідовний пошук до списку Bi.

Зберігання списків Bi може бути зв'язним або послідовним. Якщо довжини всіх підсписків приблизно рівні та M = N, то оцінка найгіршого випадку М-блочного пошуку дорівнює 2*N. При однаковій частоті використання елементів середня оцинка сложності М-блочного пошуку дорівнює N.

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

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