• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

ПОШУК

Алгори́тм пошуку́ в глибину́ (англ. 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 році.

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

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

1. Міжнаціональні відносини і причини виникнення міжнаціональних конфліктів, шляхи їх розв’язання. Міжконфесійні стосунки та їх вплив на життя в полікультурному суспільстві
2. Поняття біосфери та ноосфери. Поняття екології. Основні завдання соціальної екології. Сучасні екологічні проблеми, причини їх виникнення та розв’язання.
3. Розв’язання.
4. Розв’язання.
5. Розв’язання.
6. Розв’язання.
7. Розв’язання.
8. Розв’язання.
9. Розв’язання.
10. Розв’язання.
11. Розв’язання.

Переглядів: 1843