Завдання

1. Розробити і реалізувати у вигляді програми алгоритм пошу-ку в ширину.

2. Виконати завдання 1 для графа з кількістю вершин N = 5, в якому досліджувані вершини є досяжними. Результат вико-нання програми вивести у файл.

3. Виконати завдання 1 для графа з кількістю вершин N = 5, в якому досліджувані вершини є недосяжними. Результат ви-конання програми вивести у файл.

4. Виконати завдання 2-3 для N = 100, вивівши результат ви-конання програми у файл.

Пошук у глибину

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

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

Розглянемо той самий граф, що й у попередньому випадку (мал. 1, а), і його таблицю суміжності (мал. 1, б). Будемо знову шукати шлях від вершини 1 до вершини 7. Під час по-шуку будемо так само, як і в попередньому алгоритмі, будува-ти дерево пошуку, послідовність переглянутих і нових «видимих» вершин та множину «відвіданих» вершин. На малюнку 9, а, б, в зображено перший крок нашого алгоритму, який повністю збігається з першим кроком алгоритму пошуку в ширину.

а) б)

Мал.9

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

а) б) в)

г) 10 д) е)

Перейшовши тепер у вершину 2, згідно з таблицею суміж-ності першою новою «видимою» вершиною є вершина З, оскільки вершину 1 ми вже відвідали. Додамо цю нову вершину до нашого дерева пошуку, в послідовність та множину (мал. 10, г, д, є) і перейдемо у послідовності до неї.

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

Що нового ми побачимо з вершини 4? Згідно з малюнком 11, а, б, ми побачимо вершини 1 і 3. Але жодна з них не є новою. Невже ми потрапили в тупик? Мабуть, ні, оскільки з попереднього методу пошуку в ширину ми дійшли до шуканої вершини. Можливо, ми пішли не тим шляхом і треба спробу-вати повернутися назад? Попередньою вершиною була вершина 3, і ми повернемося саме до неї (мал. 12, б)

а) б)

мал.11

б)

мал.12

Подивимося на заданий граф: чи є з вершини 3 інший шлях, відмінний від верпіини 4? Так, це шлях через вершину 5. І ця вершина є наступною новою вершиною, яку ми можемо поба-чити з вершини 3. Перейдемо до неї, записавши її у дерево по-шуку, замінивши у послідовності нею вершину 4 та дописавши її у множину (мал. 13, о, б, в).

Застосуємо нашу стратегію до останньої «переглянутої» вер-шини 5. З неї ми бачимо вершини 2, 3, 7. Але серед них вершина 7 є новою і одночасно шуканою. Саме тому дописуємо її в усі три інформаційні схеми (мал. 14, а, б, в) та вважатимемо пошук

завершеним

б)

мал.13

Ми знайшли відповідь на запитання за допомогою алгорит­му пошуку в глибину: у заданому графі вершина 7 є досяжною з вершини 1 і шлях до неї міститься у послідовності, зобра-женій на малюнку 14, б.

Дивлячись на малюнок 11, а, де зображено досліджуваний граф, можна переконатися, що це справді шлях від вершини 1 до вершини 7. Однак отримана відповідь не збігається з відпо-віддю, одержаною за допомогою алгоритму пошуку в ширину. У чому ж справа? Ми повернемося до цього питання трохи зго-дом, порівнюючи ці два методи, а зараз визначимося з питан-ням реалізації цього алгоритму.

Як видно з покрокового виконання описаного алгоритму, ми весь час працюємо з таблицею суміжності, беручи звідти інфор-мацію про одну нову «видиму» вершину із поточної вершини графа. Ця нова вершина записується у послідовність, яка оброб-ляється за алгоритмом роботи зі стеком: ми дописуємо нову інформацію в кінець цієї послідовності і, у разі потрапляння у тупик, повертаємося до її передостаннього елемента, не роз-глядаючи надалі останній записаний елемент послідовності. І на останок: для запобігання повернення у тупикові вершини інфор-мацію про всі відвідані вершини зберігатимемо у множині.

Ми розглянули алгоритм пошуку в глибину на прикладі графа, де шукана вершина є досяжною із заданої, і отримали пози-тивну відповідь стосовно існування шляху між цими двома вершинами. А в іншій ситуації як дізнатися, що шлях відсутній? Згадаємо, як ми діяли у випадку, коли потрапляли у тупик. Ми поверталися до попередньої «переглянутої» вершини і намагалися знайти іншу нову, ще не «побачену», вершину. Логічно, що коли такої немає, то ми повернемося до попередньої віднос-но неї і будемо шукати вихід із цієї вершини і т. д. У разі відсутності шляху між двома заданими вершинами ми завершимо перегляд усіх записаних у стек вершин, повертаючись кожного разу до попередньої, спорожнивши тим самим стек. Отже, ознакою відсутності шляху в графі між двома заданими вершинами є те, що на деякому кроці алгоритму стек стане порожнім. Сформулюємо описаний алгоритм пошуку в глибину у словесній формі.

1. Вказати номер вершини k, з якої починається пошук за-даної шуканої вершини І. •

2. Почати перегляд вершин заданого графа з вершини k, за­писавши її у стек: і:= k.

3. Якщо існує нова вершина з найменшим порядковим но­мером, яку можна побачити з вершини і, то зафіксувати її, за­писавши у стек і збільшивши при цьому індекс вершини сте­ку і на 1: і:= і + 1. У протилежному випадку перейти до п. 5.

4. Якщо нова «побачена» вершина, записана у стек, є шука-ною, то перейти до п. 7.

5. Якщо з поточної вершини графа, яка записана у вершині стеку, не видно жодної нової вершини, то відкинути цю верши­ну, перейшовши до попередньої у стеку, зменшивши для цього значення індексу вершини стеку на 1: і:= і - 1. Якщо після цьо-го стек став порожнім, тобто і = 0, то перейти до п. 9.

6. Перейти до перегляду наступної «побаченої» вершини і (п. 3).

7. Вивести інформацію про те, що шукану вершину / досяг-нуто і шлях до неї від вершини k існує.

8. Перейти до п. 10.

9. Вивести інформацію про те, що шукана вершина І недо-сяжна від вершини k і шлях до неї відсутній.

10. Завершити алгоритм.

Тепер ми вже готові до порівняння двох пошукових методів на графах у ширину та в глибину.

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

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

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

Оцінка ефективності роботи алгоритму пошуку в глибину така сама, як і для пошуку в ширину, і становить 0(п + т).

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

Дата добавления: 2014-01-07