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

У пачатку 19 стагоддзя геаметрычны з Берліна Якаб Штэйнер паставіў задачу, як злучыць тры вёскі так, каб іх працягласць была самай кароткай. Пасля ён абагульніў гэтую задачу: патрабуецца знайсці на плоскасці такі пункт, каб адлегласць ад яе да n іншых кропак было найменшай. У 20 стагоддзі працягнулася праца над гэтай тэмай. Было вырашана ўзяць некалькі кропак і злучыць іх такім чынам, каб адлегласць паміж імі было самым кароткім. Гэта ўсё з'яўляецца прыватным выпадкам якая вывучаецца праблемы.

"Прагныя" алгарытмы

Алгарытм Краскала ставіцца да "прагным" алгарытмах (іх яшчэ называюць Градыентнае). Сутнасць такіх - самы вялікі выйгрыш на кожным кроку. Не заўсёды "прагныя" алгарытмы даюць найлепшае рашэнне пастаўленай задачы. Існуе тэорыя, якая паказвае, што пры іх ужыванні да пэўных задачам яны даюць аптымальнае рашэнне. Гэта тэорыя матроидов. Алгарытм Краскала ставіцца да такіх задачам.

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

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

апісанне

Алгарытм Краскала працуе так. Спачатку ўсе рэбры зыходнага графа размяшчаюцца ў парадку ўзрастання вагаў. Першапачаткова каркас не ўтрымлівае ні аднаго рэбры, але ўключае ўсе вяршыні графа. Пасля чарговага кроку алгарытму да ўжо пабудаванай часткі каркаса, якая з'яўляецца остовным лесам, дадаецца адно рабро. Яно выбіраецца не адвольна. Ўсе рэбры графа, якія не належаць каркаса, можна назваць чырвонымі і зялёнымі. Вяршыні кожнага чырвонага рэбры знаходзяцца ў адной кампаненце складнасці будуецца лесу, а вяршыні зялёнага - у розных. Таму калі дадаць туды чырвонае рабро, з'яўляецца цыкл, а калі зялёнае - у атрыманым пасля гэтага кроку лесе кампанент складнасці будзе менш на адну. Такім чынам, да атрыманага пабудове нельга дадаць ні адно чырвонае рабро, але любое зялёнае рабро дадаць можна, каб атрымаць лес. І дадаецца зялёнае рабро з мінімальным вагой. У выніку атрымліваецца каркас найменшай вагі.

рэалізацыя

Абазначым бягучы лес F. Ён разбівае мноства вяршыняў графа на вобласці складнасці (іх аб'яднанне ўтварае F, і яны парамі не перасякаюцца). У чырвоных рэбраў абедзве вяршыні ляжаць у адной частцы. Part (x) - функцыя, якая для кожнай вяршыні x вяртае імя часткі, да якой належыць x. Unite (x, y) - гэта працэдура, якая будуе новае разбіццё, якое складаецца з аб'яднання частак x і y і ўсіх астатніх частак. Хай n - лік рэбраў графа. Усе гэтыя паняцці ўключаны ў алгарытм Краскала. рэалізацыя:

1. Упарадкаваць ўсе рэбры графа ад 1-га да n-га па ўзрастанні вагаў. (Ai, bi - вяршыні рэбры з нумарам i).

2. for i = 1 to n do.

3. x: = Part (ai).

4. y: = Part (bi).

5. 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), таму што ў гэтага рэбры найменшы вага з рэбраў графа, якiя не належаць 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). З нихер і складаецца аптымальны каркас зыходнага графа. Так працуе ў дадзеным выпадку алгарытм Краскала. Прыклад гэта паказаў.

На малюнку паказаны граф, які складаецца з двух кампанент складнасці. Тлустымі лініямі паказаны рэбры аптымальнага каркаса (зялёныя), пабудаванага з дапамогай алгарытму Краскала.

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

Паслядоўнасць дададзеных рэбраў: (1,6); (0,3), (2,6) або (2,6), (0,3) - значэння не мае; (3,4); (0,1), (1,6) або (1,6), (0,1), таксама абыякава (5,6).

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