Урок Пошук у ширину та глибину


НазваУрок Пошук у ширину та глибину
Дата конвертації06.02.2013
Розмір445 b.
ТипУрок


Профільна інформатика

11 клас. АТП

Тема 2: «Основи теорії графів», 10 годин

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

Урок 6. Пошук у ширину та глибину

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



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

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

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

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

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

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

Почнемо пошук шуканої вершини 7 із заданої вершини 1 і зафіксуємо для себе цю інформацію, будуючи дерево пошуку, в якому на першому кроці нашого пошукового алгоритму є лише вершина 1 та послідовність вершин, які переглядаються.

Встановимо покажчики перегляду вершин у послідовності так: верхній вказуватиме на номер вершини, з якої ми дивимося, а нижній – на номер останньої “видимої” вершини. Відповідно на першому кроці такою вершиною є єдина вершина 1.

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

Вершину з номером 1 знову побачимо, коли перейдемо до перегляду вершин 2, 3 та 4. Щоб не зациклюватися і не крутитися на тому самому місці, варто запам'ятовувати номери вершин, у яких ми вже побували, для того, щоб виключити їх надалі з перегляду. Як реалізувати такий захист? Є два способи: перший – проглядати послідовність переглянутих вершин, другий – використати множину для їх фіксації.

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

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

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

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

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

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

Чи завершили ми наш пошук? Ні, ми не дісталися вершини 7.

Тому переходимо до наступної “побаченої” вершини 3 (“побачена” та ще й “переглянута”).

Згідно із зображенням графа і відповідної йому таблиці суміжності з вершини 3 ми бачимо вершини 1, 2, 4, 5. Але вони не є новими, тому ми їх не фіксуємо у дереві пошуку.

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

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

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

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

Тому алгоритм можна вважати завершеним, а відповідь на поставлене на початку запитання буде такою: “У заданому графі вершина 7 є досяжною з вершини 1.

Алгоритм пошуку в ширину

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

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

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

Алгоритм пошуку в ширину (словесна форма)

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

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

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

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

  • Для переходу до перегляду наступної “побаченої” вершини збільшити значення індексу “голови” черги на 1 (i:=i+1 або i++)



Алгоритм пошуку в ширину (словесна форма)

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

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

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

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

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

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

Висновок



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



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

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

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

Розглянемо той самий граф і його таблицю суміжності. Будемо знову шукати шлях від вершини 1 до вершини 7. Під час пошуку будемо так само будувати дерево пошуку.

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

Перший крок нашого алгоритму повністю збігається з першим кроком алгоритму пошуку в ширину

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

Перейшовши тепер у вершину 2, згідно з таблицею суміжності першою новою “видимою” вершиною є вершина 3, оскільки вершину 1 ми вже відвідали. Додамо цю нову вершину до дерева пошуку і перейдемо у послідовності до неї.

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

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

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

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

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

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

Застосуємо нашу стратегію до останньої “переглянутої” вершини 5. З неї ми бачимо вершини 2, 3, 7. Але серед них вершина 7 є новою і одночасно шуканою. Саме тому дописуємо її у дерево пошуку та вважатимемо пошук завершеним

Висновки

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

1, 2, 3, 5, 7.

Висновки

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

В іншій ситуації як дізнатися, що шлях відсутній? Згадаємо, як ми діяли у випадку, коли потрапляли у тупик. Ми повертались до попередньої “переглянутої” вершини і намагалися знайти іншу нову, ще не “побачену” вершину.

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

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

Алгоритм пошуку в глибину

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

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

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

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

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

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

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

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

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

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

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



Схожі:

Урок Пошук у ширину та глибину iconТема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину
Теорія графів — розділ математики, що дає змогу формалізувати взаємозв'язки між різноманітними видами інформації, організувати абстрактне...
Урок Пошук у ширину та глибину iconТема 2: «Основи теорії графів»
Тема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину
Урок Пошук у ширину та глибину iconНестандартні уроки у початковій школі кар,єрнівська загальньоосвітня школа
Уроки-діскусії ( урок-діалог, урок-диспут, урок запитань І відповідей, урок-засідання, урок-круглий стіл, урок-конгрес, урок-конференція,...
Урок Пошук у ширину та глибину iconУ 1951 році англійське дослідницьке судно “Челленджер-2” виявило у Тихому океані у Маріанському жолобі на південь від острова Гуам глибину 10860 м.
Тихому океані у Маріанському жолобі на південь від острова Гуам глибину 10860 м. Через шість років радянська експедиція на кораблі...
Урок Пошук у ширину та глибину iconЗакон України "Про реабілітацію інвалідів" Системна робота: Для організаторів: Пошук партнерів Пошук коштів Пошук спеціалістів Для педагогів, керівників творчих колективів
Держави-учасниці вживають всіх належних заходів для того, щоб надавати людям з інвалідністю можливість розвивати та використовувати...
Урок Пошук у ширину та глибину iconПошук і збирання Пошук і збирання
Комп’ютерна мережа це система зв’язку між двома чи більшою кількістю комп’ютерів
Урок Пошук у ширину та глибину iconІнтерактивна гра “Наукова подорож”. В океанах риби знаходяться на глибині сотні метрів. Як потрапляє кисень на таку глибину?
В океанах риби знаходяться на глибині сотні метрів. Як потрапляє кисень на таку глибину?
Урок Пошук у ширину та глибину iconЕвристичний пошук Евристичний пошук Інтуїтивно “метод проб та помилок”, систематизований перебір варіантів можливих дій
Якщо підходить в залежності від постановки задачі або прийняти його як остаточний, або розвинути далі
Урок Пошук у ширину та глибину iconУрок Коло. Круг. Урок Коло. Круг. Урок Дотична до кола, її властивості. Урок 3 Коло, вписане в трикутник. Урок 5 Коло, описане навколо трикутника
Навчитись будувати, знаходити елементи кола за його властивостями, розв'язувати задачі
Урок Пошук у ширину та глибину iconУрок Політичне життя в Україні в 1656-1657 рр. Урок Політичне життя в Україні в 1656-1657 рр. Урок Гетьманщина в роки правління гетьмана І. Виговського
Урок Політичний устрій Лівобережної Гетьманщини та Слобідської України в ІІ половині XVII століття

Додайте кнопку на своєму сайті:
dok.znaimo.com.ua


База даних захищена авторським правом ©dok.znaimo.com.ua 2013
звернутися до адміністрації
dok.znaimo.com.ua
Головна сторінка