Алгоритъм Kruskal му - изграждането на оптимална рамка

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

"Алчни" алгоритъм

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

Намирането на най-малко кланично тегло

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

описание

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

изпълнение

Да означим текущото гората F. Тя разделя множеството от върховете в областта на свързаност (техните синдикални форми F, и те са разединени). В двата края на червените върхове лежат в едно цяло парче. Част (х) - функция, която за всеки връх х връща част от името, той принадлежи х. Обедини (х, у) - процедура, която се основава на нов дял, състояща се от комбиниране на части от х и у и всички други части. Нека п - брой на ръбове. Всички тези понятия са включени в алгоритъма Kruskal му. Изпълнение:

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

2. за I = 1 до п направи.

3. х: = част (AI).

4. Y: = част (Bi).

5. Ако X не равно у след това обедини (х, у), да се включи с броя на ръба F аз.

правилност

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

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

Достоверността на алгоритъм Kruskal са следствие от теоремата на Радо-Едмъндс на matroids.

Примери за нанасяне Kruskal алгоритъм

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

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

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

Последователността на добавените ребрата (1.6); (0,3), (2,6) или (2,6), (0,3) - не е от значение; (3,4); (0,1), (1,6) или (1,6), (0,1), също така се грижи (5,6).

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