Розв’язання.

ПОШУК

Алгори́тм пошуку́ в глибину́ (англ. Depth-first search, DFS) — алгоритм для обходу дерева, структури подібної до дерева, або графа. Робота алгоритма починається з кореня дерева (або іншої обраної вершини в графі) і здійснюється обхід в максимально можливу глибину до переходу на наступну вершину.

Рекурсивна версія алгоритму (псевдокод):

def dfs(v):

помітити v як відвідану

обійти-в-прямому-порядку(v)

для всіх ребер i інцидентних до v таких що i не відвідано

dfs(i)

обійти-в-зворотному-порядку(v)

Рис. 9. Порядок обходу вершин.

По́шук у ширину́ — алгоритм пошуку на графі.

Якщо задано граф G = (V, E) та початкову вершину s, алгоритм пошуку в ширину систематично обходить всі досяжні із s вершини. На першому кроці вершина s позначається, як пройдена, а в список додаються всі вершини, досяжні з s без відвідування проміжних вершин. На кожному наступному кроці всі поточні вершини списку відмічаються, як пройдені, а новий список формується із вершин, котрі є ще не пройденими сусідами поточних вершин списку. Для реалізації списку вершин найчастіше використовується черга. Виконання алгоритму продовжується до досягнення шуканої вершини або до того часу, коли на певному кроці в список не включається жодна вершина. Другий випадок означає, що всі вершини, доступні з початкової, уже відмічені, як пройдені, а шлях до цільової вершини не знайдений.

Алгоритм має назву пошуку в ширину, оскільки «фронт» пошуку (між пройденими та непройденими вершинами) одноманітно розширюється вздовж всієї своєї ширини. Тобто, алгоритм проходить всі вершини на відстані k перед тим як пройти вершини на відстані k+1.

Рис. 10. Порядок обходу вершин.

Одним із застосувань пошуку в ширину є алгоритм Лі або хвильовий алгоритм.

Задача.Дано кліткове поле. Частина клітинок занята перешкодами. Необхідно попасти з деякої клітинки в другу задану шляхом послідовного переміщення по клітинках. Рухатись можна тільки на одну клітинку вгору, вправо, вниз або вліво.

Позначимо перешкоди 1, а клітинки по яких можна ходити 0. Кліткове поле буде являти собою прямокутний масив. Розширимо заданий масив двома стовпцями і двома рядками (по периметру) і заповнимо додаткові рядки і стовпці одиницями, щоб краї поля ототожнити з перешкодами. Поставимо в початкову клітинку число 2. Занесемо координати початкової точки у створену чергу. У всі вільні клітинки навколо початкової заповнимо числом 3. Координати цих клітинок занесемо в хвіст черги. Всі вільні клітинки біля трійок заповнимо числом 4, заносячи відповідні координати в хвіст черги і так далі поки хвиля чисел не досягне кінцевої клітинки, або не закінчиться черга. Нехай координати початкової клітинки 9, 3, а кінцевої 2, 10.

Кількість кроків 16-2=14. Шлях знаходять рухаючись з кінцевої точки до початкової в сторону зменшення чисел.

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

Кістякове дерево також називають каркасним деревом, покриваючим деревом, кістяком або каркасом графа.

Властивості.

Будь-яке каркасне дерево у графі з n вершинами містить рівно n — 1 ребро. Кількість кістякових дерев у повному графі з n вершинами подається формулою Келі:

Каркасне дерево може бути побудовано майже будь-яким алгоритмом обходу графа, наприклад пошуком у глибину або у ширину. Воно складається з усіх пар ребер (u, v), таких, що алгоритм, переглядаючи вершину u виявляє в її списку суміжності нову, невиявлену раніше вершину v. Кістякове дерево, побудоване обходом графа починаючи з вершини s за алгоритмом Дейкстри, має властивість, що найкоротший шлях у графі з вершини s до будь-якої іншої вершини — це шлях з s до цієї вершини в побудованому дереві.

Якщо кожному ребру графа присвоєно вагу, то пошук оптимального каркасного дерева, яке мінімізує суму ваги його ребер здійснюють численні алгоритми пошуку мінімального каркасного дерева.
Задача про пошук кістяка, в якому ступінь кожної вершини не перевищує деякої наперед заданої константи k, є NP-повною.

Мінімальне кістякове дерево (чи мінімальне покриваюче дерево) в зв'язаному, зваженому, неорієнтованому графові - це кістякове дерево цього графа, що має мінімальну можливу вагу, де під вагою дерева розуміється сума вагів ребер, що входять в нього.

Завдання про знаходження мінімального кістякового дерева часто зустрічається в подібній постановці: припустимо, є n міст, які необхідно з'єднати дорогами, так, щоб можна було добратися з будь-якого міста в будь-яке інше (безпосередньо або через інші міста). Дозволяється будувати дороги між заданими парами міст і відома вартість будівництва кожної такої дороги. Вимагається вирішити, які саме дороги треба будувати, щоб мінімізувати загальну вартість будівництва.

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

Існує декілька алгоритмів для знаходження мінімального кістякового дерева. Деякі найбільш відомі з них: Алгоритм Прима; Алгоритм Краскала (чи алгоритм Крускала); Алгоритм Борувки.

Алгоритм Крускала(чи алгоритм Краскала) - алгоритм побудови мінімального остовного дерева зваженого зв'язного неорієнтованого графа. Алгоритм уперше описав Джозеф Крускал в 1956 році.

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

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Синтаксичний аналіз арифметичних виразів	\|	Приклад

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.009 сек.