Урок 09                                                                                     Інформатика 11 (АП)

Пошук у ширину.

Мета.

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

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

Виховна. Виховувати наполегливість, естетичність у оформленні, грамотно висловлювати свої думки.

Тип уроку. Засвоєння нових знань і навичок.

Матеріали для роботи з учнями:

Інформатика: Методи побудови алгоритмів та їх аналіз. Oбчисл. алгоритми: Навч. посіб. для 9-10 кл із поглибл. вивч. інформатики. - К.: Генеза, 2009.

Мультимедійне обладнання.

Основні поняття теорії графів

Теорія графів

План

• Організація класу.
• Мотивація навчальної діяльност.
• Структури даних: проста змінна, масив, стек.
• Практичні завдання.
• Типові запитання до уроку.
• Домашнє завдання.

Пам’ятка для учня!

• Пригадайте правила техніки безпеки при роботі з ПК.
• Через кожні 15 хв. виконуйте вправи для очей та для зняття м’язової втоми.

Хід уроку

1. Організаційний момент.

2. Актуалізація опорних знань.

        Фронтальне опитування тестування.

3. Мотивація навчальної діяльності.

Раніше ми вже розглядали різноманітні пошукові алгорит­ми: пошук заданої інформації в одновимірному масиві, в ме­режі, у рядку. Під час дослідження задач, що пов’язані з оброб­кою інформації, яку можна представити у вигляді графів, та­кож постає питання пошуку. У першу чергу - це пошук шляху від однієї заданої вершини до іншої.

Існує два підходи до здійснення такого пошуку. Розглянемо перший із них - пошук у ширину.

4. Вивчення нового матеріалу.

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

Для зручнішого пояснення цього методу розглянемо конкрет­ний приклад графа, зображеного на малюнку 21, а та відповідній йому матриці суміжності (мал. 21, б). Нехай також відомо, що необхідно визначити існування у даному графі шляху від вер­шини 1 до вершини 7.

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

І ще одна інформація, яка може бути нам надалі корисною. Якщо забігти наперед і розглянути заданий граф (мал. 21, а), то можна помітити, що вершину з номером 1 знову побачимо, коли перейдемо до перегляду вершин 2, 3 та 4. Але повертатися у неї немає сенсу, оскільки при цьому ми «зациклимося» і бу­демо крутитися на одному і тому самому місці. Тому варто за­пам’ятовувати номери вершин, у яких ми вже побували, для

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

Продовжимо пошук вершини 7. З малюнка 21, а видно, що з вершини 1 ми бачимо вершини 2, 3 і 4. Ту саму інформацію ми можемо отримати і з таблиці суміжності (мал. 21, б), пере­глянувши рядок, що відповідає номеру вершини, з якої ми дивимося, тобто перший рядок таблиці. Давайте зафіксуємо цю інформацію у дереві пошуку (мал. 23, а), у послідовності номерів вершин, які ми переглянули (1) і які ми бачимо (2, 3, 4) (мал. 23, в). Серед них поки що шуканої вершини 7 немає.

Для подальшого пошуку перейдемо до однієї з нових вершин, які ми побачили. Це вершини 2, 3 і 4. У нашій послідовності (мал. 23, б) першою записана вершина 2, тому й перейдемо до неї. Які вершини ми бачимо з вершини 2 (мал. 21, а)? Це верши­ни 1, 3, 5 і 6. Цю саму інформацію можна отримати з другого рядка таблиці суміжності (мал. 21,6). Однак лише вершини 5 і 6 є новими, а вершини 1 і 3 ми вже бачили на попередніх кроках нашого алгоритму. Доповнимо дерево пошуку (мал. 24, а), по­слідовність переглянутих і «видимих» вершин (мал. 24, б) та множину (мал. 24, в) новою інформацією.

Чи завершили ми наш пошук? Зрозуміло, що ні, оскільки ні у дереві пошуку, ні у послідовності ми ще не дісталися шуканої вершини 7. Тому переходимо у послідовності вершин до на­ступної «побаченої» вершини 3. Тепер її можна буде назвати не лише «побаченою», але ще й «переглянутою». Згідно із зобра­женням графа і відповідної йому таблиці суміжності з вершини З ми бачимо вершини 1, 2, 4 і 5. Але вони не є новими, тому ми їх не фіксуємо ні у дереві пошуку, ні у послідовності вершин, ні у множині (мал. 25, а, б, в).

Переходимо до наступної вершини у послідовності, якою є вершина 4. Звідси ми бачимо вершини 1 і 3. Але і ці вершини вже є «побаченими», тому у нашому алгоритмі змінюється лише вершина, яку ми переглядаємо наступною. Такою верши­ною є вершина з номером 4, тобто наступна у нашій послідов­ності «переглянутих» і «видимих» вершин (мал. 26, б). З вер­шини 4 ми знову-таки нічого нового не побачимо, оскільки вершини 1 та 3 ми вже бачили раніше. Інформація на малюн­ках 26, а та 26, в залишилася незмінною.

Продовжуючи логіку нашого алгоритму, переходимо до вер­шини 5 - наступної у нашій послідовності (мал. 27, б). З верши­ни 5 ми бачимо вершини 2,3,7. Перші дві з цих вершин уже бу­ли переглянуті, а от вершина 7 не тільки нова, але й ще шука­на. Тому алгоритм можна вважати завершеним, а відповідь на поставлене на початку запитання буде такою: «У заданому графі вершина 7 є досяжною з вершини 1».

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

Тепер ми можемо проаналізувати умови завершення роботи алгоритму пошуку в ширину. Таких випадків є два: шукана вершина знайдена і відомий шлях до неї, або шукана вершина є недосяжною і шлях до неї відсутній.

Ми розглянули саме перший випадок пошуку вершини в графі, коли шукана вершина 7 є досяжною із заданої верши­ни 1. Шлях від вершини 1 до вершини 7 присутній у черзі, але без додаткової інформації він дещо прихований. Для отриман­ня цього шляху необхідно запам’ятовувати також і номери вер­шин, з яких ми побачили кожну наступну вершину. На малюн­ку 28 ця інформація позначена індексами для кожної поточної вершини, записаної у чергу.

Другий випадок може бути розтлумачений так: «голова» чгрги досягнула її «хвоста», асеред нових «побачених» вершин так і не з’явилася шукана. Це означає, що ми переглянули всі досяжні вершини графа, але не змогли дістатися до шуканої.

Підіб’ємо підсумок наших міркувань і опишемо алгоритм пошуку в ширину в словесній формі.

1. Вказати номер вершини k, з якої починається пошук за­даної шуканої вершини І.
2. Почати перегляд вершин заданого графа з вершини k, за­писавши її в чергу: і := k. Одночасно ця вершина є і останньою «побаченою» вершиною: j := k.
3. Зафіксувати всі нові вершини, які можна побачити з вер­шини і, в порядку зростання їх номерів, записуючи їх у чергу і збільшуючи при цьому на кожному кроці індекс «хвоста» чер­ги j на 1 (j := j + 1).
4. Якщо серед нових «побачених» вершин, записаних у чер­гу, є шукана вершина, то перейти до п. 8.
5. Для переходу до перегляду наступної «побаченої» верши­ни збільшити значення індексу «голови» черги і (і := і + 1).
6. Якщо значення індексу «голови» черги і збіжиться зі зна­ченням індексу його «хвоста» j, то перейти до п.10.
7. Перейти до перегляду наступної «побаченої» вершини і (п. 3).
8. Вивести інформацію про те, що шукану вершину І досяг­нуто і шлях до неї від вершини k існує.
9. Перейти до п. 11.
10. Вивести інформацію про те, що шукана вершина І недо­сяжна від вершини k і шлях до неї відсутній.
11. Завершити алгоритм.

Перейдемо до реалізації описаного алгоритму у вигляді фрагмента Pascal-програми:

head := 1; tail := 2; а[1] := k;                          {Ініціалізація початкових значень.}

flag := false; s := [k];

while (head < tail) and not flag do                                 {«Голова» менша за «хвіст» та}

   begin                                                                             {не досягнуто шуканої вершини.}

       і := 1;                                              {Перегляд к-го рядка таблиці суміжності спочатку.}

         while (І <= n) and not flag do {Вести пошук, доки не досягнуто кінця рядка}

begin             {або не знайдено шуканої вершини.}

  if (d[a[head], І]= 1) and not (І in S) {Якщо поточна вершина є «видимою»}

   then                 {і ще не переглядалася, тоді}

begin

   a[tail] := І; S := S + [і];                         {записуємо її у «хвіст» черги та додаємо}

   inc(tail);                               {до множини, збільшуємо індекс «хвоста» черги.}

   if і = I then flag := true; {Фіксуємо умову досягнення шуканої вершини.}

end;

          inс(і) {Перехід до наступного елемента к-го рядка таблиці суміжності.}

        end;

     if not false                                                      {Якщо не досягнуто шуканої вершини,}

     then inc(head)                                            {то збільшуємо індекс «голови» черги.}

end;

        If flag then write(f_OUt, ’YES’) {Інформація про те, що знайдено шукану вершину.}

{Інформація про те, що}

        else write(f out, ’NO’);                                         {не знайдено шукану вершину.}

Для реалізації алгоритму, що визначає шлях від заданої до шуканої вершини, необхідно зробити корективи.

Опис одновимірного масиву, який реалізує структуру даних «черги», можна запропонувати такий:

а: аггау[1 ..100] of record

top, prev: byte; end;

Початкові значення параметрів «черги» будуть такими: head := 1; tail := 2; a[l].top := k; a[i].prev := 0; а фрагмент програми, що поповнює «чергу» новими «видими­ми» вершинами, такий:

if (d[a[head].top, і] = 1) and not (і in s)

     then

         begin

a[tail].top := i; a[tail].prev := head;

inc(tail); s := s + [i];

if і = I then flag := true;

    end;

Для виведення інформації про існуючий шлях від заданої вершини до шуканої можна запропонувати такий фрагмент програми мовою Pascal:

if flag then

begin

writeln(f_out, ’YES’);

repeat                                                            {Виведення номера поточної вершини}

      write(f_out, a[tail]-top, ’ ’);                                                    {визначеного шляху.}

{Перехід до вершини, з якої було видно}

tail := a[tail].prev;           {поточну вершину шляху.}

     until a[tail].prev = 0;                                {Завершення визначення шляху.}

      write(f_OUt, a[tail].top); {Виведення номера вершини, що є початком шляху.}

  end

else write(f_out, ’NO’);

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

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

Спробуємо провести оцінку алгоритму пошуку в ширину. Під час формування черги з вершин заданого графа, що скла­дається з п вершин і т ребер, кожна вершина переглядається лише один раз. Це відповідає оцінці О(п). Але при цьому пере­глядаються всі ребра, яким належить поточна вершина. Отже, оцінка перегляду ребер становить 0(т). Оскільки перегляд ребер іде паралельно з переглядом вершин, що їм належать, то остаточна оцінка алгоритму визначається як 0(п + пі). Отже, можна зробити висновок, що час роботи алгоритму прямо пропорційний розміру заданого графа.

5. Вправи для розв’язування.

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

6. Підсумки уроку.

7. Домашнє завдання.

1. Вивчити конспект.
2. Виконати завдання.