Алгоритъмът на Крускал - конструкцията на оптималния скелет

В началото на 19 век геометрията от Берлин, Якоб Щайнер, поставила задачата за свързване на трите села, така че тяхната дължина да е най-кратката. Впоследствие той обобщи този проблем: трябва да намери точка в равнината, така че разстоянието от нея до други точки да е най-малкото. През 20-и век работата по тази тема продължи. Решено е да се вземат няколко точки и да се свържат по такъв начин, че разстоянието между тях да е най-кратко. Това е специален случай на проучения проблем.

Алчници алчни

Алгоритъмът на Kruskal се отнася до "алчни" алгоритми (те също се наричат ​​градиентни алгоритми). Същността на тези - най-голямата победа на всяка стъпка. Не винаги алчните алгоритми дават най-доброто решение за задачата. Има теория, която показва, че когато се прилагат към конкретни проблеми, те осигуряват оптималното решение. Това е теорията на мароидите. Алгоритъмът на Крускал се отнася до такива проблеми.

Намиране на скелета с минимално тегло

Изглежданият алгоритъм конструира оптималния скелет на графиката. Проблемът за него е както следва. Представена е неопределена графика без множество ръбове и бримки и на нейната група от ръбове се дава функция w, която приписва на всеки ръб е число - теглото на ръба - w (e). Теглото на всяка подгрупа от множеството ръбове се определя от сумата от теглата на нейните ръбове. Необходимо е да се намери скелет с най-малко тегло.

описание

Алгоритъмът на Kruskal работи по този начин. Първо, всички ръбове на оригиналната графика са подредени в зависимост от нарастващите тегла. Първоначално рамката не съдържа никакви ръбове, но включва всички върхове на графиката. След следващата стъпка на алгоритъма един ръб се добавя към вече изградената част на рамката, която е обхващаща гора. Той не е избран произволно. Всички краища на графиката, които не принадлежат към скелета, могат да се наричат ​​червени и зелени. Върховете на всяко червено ребро са в един от компонентите на свързаността на гората, която се изгражда, а върховете на зелените са в различни компоненти. Ето защо, ако добавите червен ръб там, се появява цикъл, а ако зеленият - в последващата стъпка в гората, компонентът за свързване ще бъде по-малко с един. По този начин не може да се добави червен ръб към произтичащата конструкция, но може да се добави и всеки зелен ръб, за да се получи гората. И се добавя зелено ребро с минимално тегло. В резултат се получава скелет с най-малко тегло.

изпълнение

Ние обозначаваме текущата гора F. Разделя множеството върхове на графиката в свързани области (техните съюзни форми F и те не се пресичат по двойки). Червените ръбове имат и двата върха в една част. Част (x) е функция, която връща името на частта, към която принадлежи х за всеки връх х. Unite (x, y) е процедура, която изгражда нов дял, състоящ се от съединението на частите x и y и всички други части. Нека n е броят на краищата на графиката. Всички тези понятия са включени в алгоритъма на Крускал. Изпълнение:

1. Подредете всички ръбове на графиката от 1-во до нутови възходящи тежести. (ai, bi са върховете на ръба с индекс i).

2. за i = 1 до n.

3. x: = Част (ai).

4. y: = част (би).

5. Ако x не е равно на y, тогава Unite (x, y), включва края с числото i в F.

правилност

Нека T е скелетът на оригиналната графика, конструиран чрез алгоритъма на Kruskal и нека S бъде неговият произволен скелет. Трябва да докажем, че w (T) не надвишава w (S).

Нека М - множество перки S, Р - множество от ребра Т. Ако S не е равно на Т, тогава има конструкция ребро et T, които не принадлежат към S. S. et граничат цикъл, той се нарича С С изважда от всички крайни ES, принадлежащ S. Ще бъде получена нова рамка, защото в нея има също толкова краища и върхове. Неговото тегло не надвишава w (S), тъй като w (et) не е по-голямо от w (es) от алгоритъма на Kruskal. Тази операция (заместващи T S ребра ребра) ще се повтаря дотогава, докато получите T. Теглото на всяка следваща приетия пакет е не по-голямо от предишното тегло, което означава, че w (T) е не по-голяма от w (S).

Също така, правилността на алгоритъма на Крускал произтича от теоремата на Радо-Едмондс за матроидите.

Примери за приложението на алгоритъма на Kruskal

Dan графика с възли А, В, С, D, Е и ребра (А, В), (а, д), (В, С), (Ь, е), (С, D), (с, е) , (d, е). Теглото на ръбовете е показано в таблицата и на фигурата. Първоначално конструкцията на гората F съдържа всички върхове на графиката и не съдържа нито един ръб. Алгоритъм Kruskal първия добавят ребро (А, Е), тъй като теглото имаше най-ниската и върховете А и Е са в различни компоненти дървесина свързване F (ребро (а, д) зелен), след това реброто (С, D), защото че най-малко този ръб тегло на графиката ръбове, които не принадлежат към F, и е зелен, а след това по същите причини натрупват ръб (а, Ь). Но на ръба (б, д) се предава, въпреки че и минималното тегло на останалите краища, защото тя е в червено: върховете В и Е, принадлежат към един и същ компонент на горски свързаност F, което е, ако прибавим към F ръба (б, д), е формиран цикъл. След това се добавя зеленият ръб (b, c), червеният край (c, e) се пропуска и след това d, e. По този начин краищата (а, е), (с, d), (а, b), (b, с) се добавят последователно. От него се състои оптималният скелет на оригиналната графика. Ето как работи алгоритъмът Crascal в този случай. Един пример показва това.

Фигурата показва графика, състояща се от два компонента за свързване. Удебелените линии показват краищата на оптималната рамка (зелено), конструирани с алгоритъма на Kruskal.

Горната фигура показва оригиналната графика, а в долната - скелетът на минималното тегло, конструиран за него с помощта на разглеждания алгоритъм.

Последователността на добавените краища: (1,6) - (0,3), (2,6) или (2,6), (0,3) - няма значение (3,4) - (0,1) (1.6) или (1.6), (0.1) също е безразличен (5.6).

Алгоритъмът на Kruskal намират практическо приложение, например, за оптимизиране на комуникационните подложки, пътищата в новите квартали в местностите на всяка страна, както и в други случаи.