Тема 4. Пошук в глибину

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

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

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

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

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

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

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

З вершини 4 ми побачимо вершини 1 і 3, але жодна з них не є новою. Далі шляху немає, тому повертаємось назад. Оскільки попередньою вершиною була вершина 3, тому повернемось до неї (Малюнок 5).

Подивимося чи є з вершини 3 інший шлях, відмінний від вершини 4? Це шлях через вершину 5. Вона є наступною новою вершиною, яку ми бачимо з вершини 3. Перейдемо до неї, записавши її у дерево пошуку, замінивши нею вершину 4 у послідовності та дописавши її у множину (Малюнок 6).

З вершини 5 бачимо вершини 2, 3, 7. Новою є  вершина 7, одночасно вона є шуканою. Тому дописуємо її в дерево пошуку, послідовність та множину (Малюнок 7).

Отже, у заданому графі вершина 7 є досяжною з вершини 1 і шлях до неї міститься у послідовності (Малюнок 7).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Наведемо фрагменти алгоритму пошуку в глибину у вигляді Pascal-програми:

Описуємо масив для послідовності вершин   var a:array[1..100] of byte;

Вводимо матрицю суміжності d розмірністю n*n.

top:=1; a[1]:=k;                                                                    {Ініціалізація роботи алгоритму.}

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

while (top > 0) and not flag do {Поки стек не порожній і не знайдено шукану}
                                                                                            {вершину,}

begin

i:=1;                                                        {починаємо пошук нової «видимої» вершини.}

While (і <= n) and not flag do             {Пошук нової «видимої» вершини з к-ї вершини.}

begin

if (d[a[top], i] = 1) and not (і in S)                    {Якщо існує нова «видима» вершина,}

then begin

         inc(top); a[top] := i;                                                  {то записуємо її у стек і}

         s:=s+[i];                                                                               {заносимо у множину.}

          if i = z then flag := true; {Якщо нова вершина є шуканою, то фіксуємо це.}

     end
else inc(і)                              {Інакше переходимо до нової «побаченої» вершини.}

end;

if not false then dec(top)                                     {Якщо відсутні нові «видимі» вершини,}

end;                                                                               {то повертаємося до попередньої.}

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

if flag then begin                                                                  {Якщо шлях знайдено, то}

           writeln('YES');                                           {виводимо інформацію про це і}

           while top <>0 do

               begin                                                          {виводимо послідовність}

                        write(a[top],' '); dec(top)                                     {елементів стеку.}

                   end

           end

   else write('NO');                      {Виведення інформації про відсутність шляху.}

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

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

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

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

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

Завдання

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

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

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

4.       Виконати завдання 2-3 для N = 100.