Материал: 62_201
коротший шлях від заданої вершини до шуканої. Для того щоб остаточно у цьому пересвідчитися, далі ми перейдемо до іншого методу - пошуку в глибину.
Спробуємо провести оцінку алгоритму пошуку в ширину. Під час формування черги з вершин заданого графа, що скла дається з п вершин і т ребер, кожна вершина переглядається лише один раз. Це відповідає оцінці О(п). Але при цьому пере глядаються всі ребра, яким належить поточна вершина. Отже, оцінка перегляду ребер становить О(т). Оскільки перегляд ребер іде паралельно з переглядом вершин, що їм належать, то остаточна оцінка алгоритму визначається як 0(п + пі). Отже, можна зробити висновок, що час роботи алгоритму прямо пропорційний розміру заданого графа.
Завдання
1.Розробити і реалізувати у вигляді програми алгоритм пошу ку в ширину.
2.Виконати завдання 1 для графа з кількістю вершин N = 5, в якому досліджувані вершини є досяжними. Результат вико нання програми вивести у файл.
3.Виконати завдання 1 для графа з кількістю вершин N = 5, в якому досліджувані вершини є недосяжними. Результат ви конання програми вивести у файл.
4.Виконати завдання 2-3 для N = 100, вивівши результат ви конання програми у файл.
Пошук у глибину
Якщо під час пошуку в ширину ми захоплювали усі нові вер шини, що нам було видно з поточної вершини, у яку переміщува лися на кожному наступному кроці, то під час пошуку в глибину дещо змінимо нашу стратегію. А полягатиме вона ось у чому.
На кожному кроці алгоритму, знаходячись у наступній по точній вершині, будемо бачити лише одну нову, досі не «види му», вершину і переходити до неї.
Розглянемо той самий граф, що й у попередньому випадку (мал. 21, а), і його таблицю суміжності (мал. 21, б). Будемо знову шукати шлях від вершини 1 до вершини 7. Під час по шуку будемо так само, як і в попередньому алгоритмі, будува ти дерево пошуку, послідовність переглянутих і нових «види мих» вершин та множину «відвіданих» вершин. На малюнку 29, а, б, в зображено перший крок нашого алгоритму, який повністю збігається з першим кроком алгоритму пошуку в ширину.
62
® 4
a) |
6) |
в) |
Мал. 29
Наступний крок буде таким: згідно з таблицею суміжності першою новою вершиною, яку ми бачимо з вершини 1, є вер шина 2. Перейдемо до неї, додавши її у дерево пошуку, в по слідовність «відвіданих» вершин і у множину (мал. ЗО, а, б, в).
-0
1 2
б) |
в) |
4
1 2 3
д) |
є) |
г)
Мал. ЗО
Перейшовши тепер у вершину 2, згідно з таблицею суміж ності першою новою «видимою» вершиною є вершина З, оскільки вершину 1 ми вже відвідали. Додамо цю нову верши ну до нашого дерева пошуку, в послідовність та множину (мал. ЗО, г, д, є) і перейдемо у послідовності до неї.
Якщо на наступному кроці алгоритму ми подивимося з вер шини 3, то зможемо побачити вершини у такій послідовності (третій рядок таблиці суміжності): 1, 2, 4, 5. Серед них першою новою вершиною є вершина 4. Додамо її до переглянутих і пе рейдемо до неї (мал. 31, а, б, в).
Що нового ми побачимо з вершини 4? Згідно з малюн ком 21, а, б, ми побачимо вершини 1 і 3. Але жодна з них не є новою. Невже ми потрапили в тупик? Мабуть, ні, оскільки з попереднього методу пошуку в ширину ми дійшли до шуканої
63
4
1 2 3 4
б) |
в) |
Мал. 31
вершини. Можливо, ми пішли не тим шляхом і треба спробу вати повернутися назад? Попередньою вершиною була верши на 3, і ми повернемося саме до неї (мал. 32, б).
£
1 2 3 4
—і — і — і —
б) |
в) |
Мал. 32
Подивимося на заданий граф: чи є з вершини 3 інший шлях, відмінний від верпіини 4? Так, це шлях через вершину 5. І ця вершина є наступною новою вершиною, яку ми можемо поба чити з вершини 3. Перейдемо до неї, записавши її у дерево по шуку, замінивши у послідовності нею вершину 4 та дописавши її у множину (мал. 33, о, б, в).
Застосуємо нашу стратегію до останньої «переглянутої» вер шини 5. З неї ми бачимо вершини 2, 3, 7. Але серед них верши на 7 є новою і одночасно шуканою. Саме тому дописуємо її в усі три інформаційні схеми (мал. 34, а, б, в) та вважатимемо по шук завершеним.
|
|
|
4 |
1 |
2 |
3 |
5 |
|
|
б) |
в) |
Мал. 33
64
Мал. 34
Ми знайшли відповідь на запитання за допомогою алгорит му пошуку в глибину: у заданому графі вершина 7 є досяжною з вершини 1 і шлях до неї міститься у послідовності, зобра женій на малюнку 34, б.
Дивлячись на малюнок 21, а, де зображено досліджуваний граф, можна переконатися, що це справді шлях від вершини 1 до вершини 7. Однак отримана відповідь не збігається з відпо віддю, одержаною за допомогою алгоритму пошуку в ширину. У чому ж справа? Ми повернемося до цього питання трохи зго дом, порівнюючи ці два методи, а зараз визначимося з питан ням реалізації цього алгоритму.
Як видно з покрокового виконання описаного алгоритму, ми весь час працюємо з таблицею суміжності, беручи звідти інфор мацію про одну нову «видиму» вершину із поточної вершини графа. Ця нова вершина записується у послідовність, яка оброб ляється за алгоритмом роботи зі стеком: ми дописуємо нову інформацію в кінець цієї послідовності і, у разі потрапляння у тупик, повертаємося до її передостаннього елемента, не роз глядаючи надалі останній записаний елемент послідовності. І на останок: для запобігання повернення у тупикові вершини інфор мацію про всі відвідані вершини зберігатимемо у множині.
Ми розглянули алгоритм пошуку в глибину на прикладі гра фа, де шукана вершина є досяжною із заданої, і отримали пози тивну відповідь стосовно існування шляху між цими двома вер шинами. А в іншій ситуації як дізнатися, що шлях відсутній? Згадаємо, як ми діяли у випадку, коли потрапляли у тупик. Ми поверталися до попередньої «переглянутої» вершини і намага лися знайти іншу нову, ще не «побачену», вершину. Логічно, що коли такої немає, то ми повернемося до попередньої віднос но неї і будемо шукати вихід із цієї вершини і т. д. У разі відсут ності шляху між двома заданими вершинами ми завершимо перегляд усіх записаних у стек вершин, повертаючись кожного разу до попередньої, спорожнивши тим самим стек. Отже,
З Інформатика, 9-Ю кл. |
65 |
ознакою відсутності шляху в графі між двома заданими верши нами є те, що на деякому кроці алгоритму стек стане порожнім.
Сформулюємо описаний алгоритм пошуку в глибину у сло весній формі.
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.Завершити алгоритм.
Наведемо фрагменти алгоритму пошуку в глибину у вигляді Pascal-програми:
top '.- 1; а[1] := к; {Ініціалізація роботи алгоритму.}
flag := false; s := [к];
while (top > 0) and not flag do {Поки стек не порожній і не знайдено шукану}
begin |
{верш |
І := 1; |
{починаємо пошук нової «видимої» вершини.} |
while (І <= n) and not flag do {Пошук нової «видимої» вершини з /с-ї вершини.}
begin |
|
|
if ( d [ a [ t o p ] , І] = 1) and not (і in s) |
{Якщо існує нова «видима» вершина,} |
|
then |
|
|
begin |
|
|
inc(top); a[top] |
:= і; |
{то записуємо її у стек і} |
s : = S + [ i ] ; |
|
{заносимо у множину.} |
if І = І then flag := true; {Якщо нова вершина є шуканою, то фіксуємо це.} |
||
end |
|
|
else ІПС(І) |
{Інакше переходимо до нової «побаченої» вершини.} |
|
end; |
|
|
if not false then dec(top) |
{Якщо відсутні нові «видимі» вершини,} |
|
end; |
|
{т° повертаємося до попередньої.} |
66