Тема 3. Пошук в ширину

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

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

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

Для пояснення цього методу розглянемо граф та відповідну йому матрицю суміжності.

  

Потрібно визначити існування у даному графі шляху від вершини 1 до вершини 7.

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

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

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

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

 

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

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

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

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

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

Ми розглянули перший випадок пошуку вершини в графі, коли шукана вершина 7 є досяжною із заданої вершини 1. Шлях від вершини 1 до вершини 7 присутній у черзі, але його не видно без додаткової інформації. Щоб знайти цей шлях потрібно запам'ятовувати також і номери вершин, з яких ми побачили кожну наступну вершину. Тобто, на 0-кроці є вершина 1 (з якої починаємо пошук), на 1-ому кроці - вершини 2,3,4, на 2-ому кроці - вершини 5,6, на 3-ому та 4-ому кроках немає нових вершин, і на 7-ому кроці - знайдена вершина 7.

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

Опишемо алгоритм пошуку в ширину в словесній формі.

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

2.      Почати перегляд вершин заданого графа з вершини k, записавши її в чергу: і := k. Одночасно ця вершина є останньою «побаченою» вершиною: j := k.

3.      Зафіксувати всі нові вершини, які можна побачити з вершини і, в порядку зростання їх номерів, записуючи їх у чергу та збільшуючи при цьому на кожному кроці індекс «хвоста» черги j на 1 (j:=j+1).

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

5.      Для переходу до перегляду наступної «побаченої» вершини збільшити значення індексу «голови» черги і (і := і + 1).

6.      Якщо значення індексу «голови» черги і збіжиться зі значенням індексу його «хвоста» j, то перейти до п.10.

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

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

9.      Перейти до п. 11.

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

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

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

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

var a: array[1..1OO] of record

                    top, prev: byte;

                  end;

Початкові значення параметрів «черги» будуть такими:

    head := 1; tail := 2; a[1].top := k; a[i].prev := 0;

а фрагмент програми, що поповнює «чергу» новими «видими­ми» вершинами, такий:

     if (d[afhead].top, і] = 1) and not (і in s) then      begin

          a[tail].top := i;

          a[tail].prev := head;

          inc(tail);

          s := s + [i]; if і = z then flag := true;     end;

Тоді фрагмент коду для реалізації алгоритму матиме вигляд:

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

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

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

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

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

   While (i <= n) and not flag do           {Вести пошук, доки не досягнуто кінця рядка}
   begin                                                                     {або не знайдено шуканої вершини.}

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

         begin

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

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

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

          end;

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

end;

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

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

 end;             

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

                              {Інформація про те, що}
 else write('NO');                                                        {не знайдено шукану вершину.}

Щоб вивести знайдений шлях від заданої вершини до шуканої можна використати такий фрагмент:

if flag then

  begin

      write('YES');

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

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

           tail:=a[tail].prev;  {Перехід до вершини, з якої було видно поточну вершину шляху.}

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

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

   end

 else write('NO');

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

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

Завдання

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

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

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

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