http://poradumo.pp.ua

Online Журнал-Світ порад.
Головна сторінка
» » Алгоритм Краскала – побудова оптимального каркаса

Алгоритм Краскала – побудова оптимального каркаса

На початку 19 століття геометр з Берліна Якоб Штейнер поставив завдання, як поєднати три села так, щоб їх довжина була найкоротшою. Згодом він узагальнив цю задачу: потрібно знайти на площині таку точку, щоб відстань від неї до n інших точок було найменшим. У 20 столітті продовжилася робота над цією темою. Було вирішено взяти кілька точок і з'єднати їх таким чином, щоб відстань між ними було коротким. Це все є приватним випадком досліджуваної проблеми.

"Жадібні" алгоритми

Алгоритм Краскала відноситься до "жадібних" алгоритмів (їх ще називають градієнтними). Суть таких – найбільший виграш на кожному кроці. Не завжди "жадібні" алгоритми дають найкраще рішення поставленої задачі. Існує теорія, що показує, що при їх застосуванні до певних завдань вони дають оптимальне рішення. Це теорія матроидов. Алгоритм Краскала відноситься до таких завдань.




Знаходження каркаса мінімального ваги

Розглянутий алгоритм будує оптимальний каркас графа. Задача про нього полягає в наступному. Дан неорієнтований граф без кратних ребер та петель, і на велику кількість його ребер задана вагова функція w, яка приписує кожному ребру e число – вага ребра – w(e). Вага кожної підмножини з множини ребер визначається сумою ваг його ребер. Потрібно знайти каркас самого малого ваги.

Опис

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




Реалізація

Позначимо поточний ліс F. Він розбиває множину вершин графа на області зв'язності (їх об'єднання утворює F, і вони попарно не перетинаються). У червоних ребер обидві вершини лежать в одній частині. Part(x) – функція, яка для кожної вершини x повертає ім'я частини, до якої належить x. Unite(x,y) – це процедура, яка будує нове розбиття, що складається з об'єднання частин x і y і всіх інших частин. Нехай n – число ребер графа. Всі ці поняття включені в алгоритм Краскала. Реалізація:

  • Впорядкувати всі ребра графа від 1-го до n-го за зростанням ваг. (ai, bi – вершини ребра з номером i).

  • for i = 1 to n do.

  • x := Part(ai).

  • y : = Part(bi).

  • If x не дорівнює y then Unite (x, y), включити в F ребро з номером i.

  • Коректність

    Нехай T – каркас вихідного графа, побудований за допомогою алгоритму Краскала, а S – його довільний каркас. Потрібно довести, що w(T) не перевершує w(S).

    Нехай M – множина ребер S, P – множина ребер T. Якщо S не дорівнює T, то знайдеться ребро et каркаса T, що не належить S. Приєднаємо et S. Утворюється цикл, назвемо його C. Видалимо з C будь-яке ребро es, належить S. Вийде новий каркас, тому що і ребер і вершин у ньому стільки ж. Його вага не перевищує w(S), так як w(et) не більше w(es) в силу алгоритму Краскала. Цю операцію (заміну ребер S на ребра T) будемо повторювати до тих пір, поки не отримаємо Т. Вага кожного наступного отриманого каркаса не більше ваги попереднього, звідки випливає, що w(T) не більше, ніж w(S).


    Також коректність алгоритму Краскала випливає з теореми Радо-Едмондс про матроидах.

    Приклади застосування алгоритму Краскала

    Алгоритм Краскала – побудова оптимального каркаса

    Дано граф з вершинами a, b, c, d, e і ребрами (a, b), (a, e), (b, c), (b, e), (c, d), (c, e), (d, e). Ваги ребер показані в таблиці та на рисунку. Спочатку будується ліс F містить всі вершини графа і не містить жодного ребра. Алгоритм Краскала спочатку додасть ребро (a, e), так як вага у нього найменший, і вершини a і e знаходяться в різних компонентах зв'язності лісу F (ребро (a, e) є зеленим), потім ребро (c, d), тому що у цього ребра найменший вагу ребер графа, що не належать F, і воно є зеленим, потім з тих же причин додається ребро (a, b). А ось ребро (b, e) пропускається, хоч у нього і найменшу вагу з решти ребер, тому що воно червоне: вершини b і e належать одній компоненті зв'язності лісу F, тобто якщо додати до F ребро (b, e), утворюється цикл. Потім додається зелене ребро (b, c), пропускається червоне ребро (c, e), а потім d, e. Таким чином, послідовно додаються ребра (a, e), (c, d), (a, b), (b, c). З нихер і складається оптимальний каркас вихідного графа. Так працює у даному випадку алгоритм Краскала. Приклад це показав.

    Алгоритм Краскала – побудова оптимального каркаса

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

    Алгоритм Краскала – побудова оптимального каркаса

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

    Послідовність доданих ребер: (16); (03), (26) або (26), (03) – не має значення; (34); (01), (16) або (16), (01), також байдуже (56).

    Алгоритм Краскала – побудова оптимального каркаса

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

    of your page -->

    Популярні поради

    загрузка...