Het Kruskal-algoritme - de constructie van het optimale skelet

In het begin van de 19e eeuw, de meetkundige van Berlijn, Jacob Steinerde taak om de drie dorpen met elkaar te verbinden, zodat hun lengte de kortste was. Vervolgens generaliseerde hij dit probleem: het is nodig om een ​​punt op het vlak te vinden, zodanig dat de afstand ervan tot n andere punten het kleinst was. In de 20e eeuw ging het werk over dit onderwerp gewoon door. Er werd besloten om verschillende punten te nemen en ze zo te verbinden dat de afstand tussen hen het kortst was. Dit is allemaal een speciaal geval van het probleem dat wordt bestudeerd.

Greedy algoritmen

Het Kruskal-algoritme verwijst naar 'hebzuchtige' algoritmen(ze worden ook gradiënt genoemd). De essentie van die - de grootste overwinning bij elke stap. Niet altijd geven "hebzuchtige" algoritmen de beste oplossing voor de taak. Er is een theorie die laat zien dat ze, wanneer toegepast op specifieke problemen, de optimale oplossing bieden. Dit is de theorie van matroïden. Het Kruskal-algoritme heeft betrekking op dergelijke problemen.

Het skelet van minimaal gewicht vinden

Het algoritme in kwestie construeert een optimumhet skelet van de grafiek. Het probleem is als volgt. Een niet-gerichte grafiek zonder meerdere randen en lussen wordt gegeven en op de set randen krijgt een gewichtsfunctie w die aan elke rand e een nummer toekent - het gewicht van de rand - w (e). Het gewicht van elke deelverzameling van de reeks randen wordt bepaald door de som van de gewichten van de randen. Het is vereist om het skelet van het kleinste gewicht te vinden.

beschrijving

Het Kruskal-algoritme werkt als volgt. Eerst worden alle randen van de originele grafiek gerangschikt in volgorde van toenemende gewichten. Aanvankelijk bevat het framework geen randen, maar bevat het alle hoekpunten van de grafiek. Na de volgende stap van het algoritme wordt een rand toegevoegd aan het reeds geconstrueerde deel van het raamwerk, dat een omspannend bos is. Het is niet willekeurig gekozen. Alle randen van de grafiek die niet tot het skelet behoren, kunnen rood en groen worden genoemd. De hoekpunten van elke rode rib zijn in een component van de verbondenheid van het bos dat wordt gebouwd, en de hoekpunten van de green zijn in verschillende componenten. Daarom, als u daar een rode rand toevoegt, verschijnt er een cyclus en als de groene er is - in de resulterende bosstap zal de verbindingscomponent minder één worden. Er kan dus geen rode rand aan de resulterende constructie worden toegevoegd, maar elke groene rand kan worden toegevoegd om het bos te krijgen. En een groene rib met een minimumgewicht is toegevoegd. Als resultaat wordt het skelet met het kleinste gewicht verkregen.

uitvoering

Geef het huidige bos F. aan Het splitst de reeks hoekpunten van de grafiek in verbonden domeinen (hun verbindingsvormen F, en ze snijden elkaar niet in paren). De rode randen hebben beide hoekpunten in één deel. Deel (x) is een functie die de naam retourneert van het gedeelte waartoe x hoort voor elke hoekpunt x. Unite (x, y) is een procedure die een nieuwe partitie opbouwt die bestaat uit de unie van de delen x en y en alle andere delen. Laat n het aantal randen van de grafiek zijn. Al deze concepten zijn opgenomen in het Kruskal-algoritme. uitvoering:

1. Rangschik alle randen van de grafiek van de 1e tot de nde oplopende gewichten. (ai, bi zijn de hoekpunten van de rand met index i).

2. voor i = 1 tot n doen.

3. x: = Deel (ai).

4. y: = Deel (bi).

5. Als x niet gelijk is aan y en verenigt (x, y), neemt u de rand op met het cijfer i in F.

juistheid

Laat T het skelet zijn van de originele grafiek die is geconstrueerd met behulp van het Kruskal-algoritme, en laat S zijn willekeurig skelet zijn. Het is noodzakelijk om te bewijzen dat w (T) w (S) niet overschrijdt.

Laat M de reeks randen van S, P de reeks randen zijnT. Indien S niet gelijk is aan T, dan is er een rand et karkas T, niet behorend tot S. S. et grenzen de cyclus, het heet C C verwijderen van een rand es, behorend S. We krijgen een nieuw frame, omdat randen en er zitten zoveel hoekpunten in. Zijn gewicht niet groter dan wi (S), aangezien w (et) niet langer w (n) in een stroom Kruskal algoritme. Deze bewerking (plaatsvervanger Ts ribben op ribben) worden herhaald zolang ontvangt T. Het gewicht van elke volgende ontvangen frame niet groter is dan de vorige gewicht, hetgeen betekent dat w (t) niet groter dan wi (S).

Ook volgt de correctheid van het Kruskal-algoritme uit de stelling van Rado-Edmonds over matroïden.

Voorbeelden van de toepassing van het Kruskal-algoritme

Gegeven een grafiek met hoekpunten a, b, c, d, e en randen (a,b), (a, e), (b, c), (b, e), (c, d), (c, e), (d, e). De gewichten van de randen worden weergegeven in de tabel en in de afbeelding. Aanvankelijk bevat de constructie van het bos F alle hoekpunten van de grafiek en bevat deze geen enkele rand. Algoritme Kruskal eerst toevoegen rib (a, e), aangezien het gewicht had de laagste en de hoekpunten a en e zijn in verschillende componenten hout verbinding F (rib (a, e) groen) en de ribbe (c, d), omdat dat althans deze rand gewicht van de grafiek randen, niet behorend tot F, en het is groen, dan om dezelfde redenen toekomen rand (a, b). Maar de rand (b, e) wordt aangenomen, hoewel hij en het minimumgewicht van de resterende randen, omdat het rood: de hoekpunten b en e behoren tot dezelfde component van het bos connectiviteit F, dat wil zeggen, als we toe te voegen aan F de rand (b, e), wordt gevormd cyclus. Vervolgens wordt de groene rand (b, c) toegevoegd, de rode rand (c, e) overgeslagen en dan d, e. Aldus worden de randen achtereenvolgens (a, e), (c, d), (a, b), (b, c). Hieruit bestaat het optimale skelet van de oorspronkelijke grafiek. Dit is hoe het algoritme werkt in dit geval Ik heb geverfd. Een voorbeeld laat dit zien.

De afbeelding toont een grafiek die bestaat uit twee connectiviteitscomponenten. Vetgedrukte lijnen tonen de randen van het optimale kader (groen), geconstrueerd met behulp van het Kruskal-algoritme.

De bovenste afbeelding toont de oorspronkelijke grafiek en de onderste - het skelet van het minimale gewicht, geconstrueerd met behulp van het betreffende algoritme.

De reeks toegevoegde randen: (1.6); (0,3), (2,6) of (2,6), (0,3) - doet er niet toe; (3,4); (0,1), (1,6) of (1,6), (0,1), is ook onverschillig (5,6).

Kruskal's algoritme vindt praktische toepassing, bijvoorbeeld om communicatiekussens, wegen in nieuwe buurten in de plaatsen van elk land en ook in andere gevallen te optimaliseren.