Algorytm kwitnienia - Blossom algorithm

Algorytm kwiat jest algorytm w teorii grafów do konstruowania maksymalne skojarzeń na wykresach. Algorytm został opracowany przez Jacka Edmondsa w 1961 r. I opublikowany w 1965 r. Biorąc pod uwagę ogólny wykres G = ( V , E ), algorytm znajduje pasujące M takie, że każdy wierzchołek w V występuje z co najwyżej jedną krawędzią w M i | M | jest zmaksymalizowana. Dopasowanie jest konstruowane przez iteracyjne ulepszanie początkowego pustego dopasowania wzdłuż rozszerzających się ścieżek na wykresie. W przeciwieństwie do dopasowywania dwustronnego , kluczowym nowym pomysłem jest to, że cykl o nieparzystej długości na wykresie (kwiat) jest skracany do pojedynczego wierzchołka, a przeszukiwanie jest kontynuowane iteracyjnie na wykresie skurczonym.

Algorytm działa w czasie , gdzie jest liczbą krawędzi grafu i liczbą jego wierzchołków . Lepszy czas wykonywania tego samego zadania można uzyskać dzięki znacznie bardziej złożonemu algorytmowi Micali i Vazirani. ${\ Displaystyle O (| E || V | ^ {2})}$${\ displaystyle | E |}$${\ displaystyle | V |}$${\ Displaystyle O (| E || V | ^ {1/2})}$

Głównym powodem, dla którego algorytm kwitnienia jest ważny, jest to, że dał pierwszy dowód na to, że dopasowanie maksymalnego rozmiaru można było znaleźć przy użyciu wielomianu czasu obliczeń. Innym powodem jest to, że doprowadziło to do liniowego programowania wielościennego opisu dopasowującego polytopu , dając algorytm dopasowania minimalnej wagi . Jak rozwinął Alexander Schrijver , dalsze znaczenie wyniku wynika z faktu, że był to pierwszy polytop, którego dowód integralności „nie wynika po prostu tylko z całkowitej unimodularności , a jego opis był przełomem w kombinatoryce wielościennej ”.

Rozszerzające się ścieżki

Biorąc pod uwagę G = ( V , E ) i pasujące M z G , wierzchołek v jest odsłonięty, jeśli żadna krawędź M nie przypada na v . Ścieżka w G jest ścieżką naprzemienną , jeśli jej krawędzie na przemian nie znajdują się w M i M (lub w M, a nie w M ). Rozszerzająca się ścieżka P to naprzemienna ścieżka, która zaczyna się i kończy na dwóch różnych odsłoniętych wierzchołkach. Zauważ, że liczba niedopasowanych krawędzi na ścieżce rozszerzającej jest o jeden większa niż liczba dopasowanych krawędzi, a zatem całkowita liczba krawędzi na ścieżce rozszerzającej jest nieparzysta. Dopasowanie powiększenie wzdłuż ścieżki rozszerzanie P jest operacja wymiany M nową dopasowania . ${\ Displaystyle M_ {1} = M \ oplus P = (M \ setminus P) \ filiżanka (P \ setminus M)}$

Przez lematu Berge użytkownika , dopasowując M jest maksymalny wtedy i tylko wtedy, gdy nie ma M -augmenting ścieżki w G . Dlatego dopasowanie jest maksymalne lub można je wzmocnić. W związku z tym, zaczynając od początkowego dopasowania, możemy obliczyć maksymalne dopasowanie, rozszerzając bieżące dopasowanie o ścieżki rozszerzające, o ile możemy je znaleźć, i powrócić, gdy nie pozostały żadne ścieżki rozszerzające. Możemy sformalizować algorytm w następujący sposób:

   INPUT:  Graph G, initial matching M on G
   OUTPUT: maximum matching M* on G
A1 function find_maximum_matching(G, M) : M*
A2     P ← find_augmenting_path(G, M)
A3     if P is non-empty then
A4         return find_maximum_matching(G, augment M along P)
A5     else
A6         return M
A7     end if
A8 end function

Nadal musimy opisać, jak efektywnie można znaleźć ścieżki ulepszające. Procedura znajdująca je wykorzystuje kwiaty i skurcze.

Kwitnie i skurcze

Biorąc pod uwagę G = ( V , E ) i pasujące M z G , kwiat B jest cyklem w G składającym się z 2k + 1 krawędzi, z których dokładnie k należy do M , i gdzie jeden z wierzchołków v cyklu ( podstawa ) jest taka, że ​​istnieje przemienna ścieżka o parzystej długości ( rdzeń ) od v do odsłoniętego wierzchołka w .

Znajdowanie kwiatów:

• Przejdź przez wykres, zaczynając od odsłoniętego wierzchołka.
• Zaczynając od tego wierzchołka, oznacz go jako zewnętrzny wierzchołek „ o ” .
• Zamień etykietowanie między wierzchołkami będącymi wewnętrznymi „ i ” i zewnętrznymi „ o ”, tak aby żadne dwa sąsiednie wierzchołki nie miały takiej samej etykiety.
• Jeśli skończymy z dwoma sąsiednimi wierzchołkami oznaczonymi jako zewnętrzne „ o ”, to mamy cykl o nieparzystej długości, a więc kwiat.

Określić umownej wykres G „ w postaci wykresu uzyskanego z G przez zarażenia każdą krawędź B i określenie umownej dopasowanie M” jako dopasowywanie G” odpowiadającym M .

G „ ma M” -augmenting ścieżkę wtedy i tylko wtedy, gdy G ma M -augmenting ścieżki, a każde M „ -augmenting ścieżki P” w G” może być podniesiona do M -augmenting ścieżkę G przez odkręcenie skurcz przez B tak, że segment P” (jeśli występuje) przechodzącą przez przeciwko _B jest zastąpiona przez odpowiednią przesuwającego segmentu B . Bardziej szczegółowo:

• jeśli P ' przechodzi przez odcinek u → v _B → w w G' , to ten odcinek jest zastępowany odcinkiem u → (u '→ ... → w') → w w G , gdzie wierzchołki kwiatu u ' i w ' i strona B , (u' → ... → w ') , idąca od u' do w ', są wybierane w celu zapewnienia, że ​​nowa ścieżka nadal się zmienia ( u' jest odsłonięta względem , ).${\ displaystyle M \ czapka B}$${\ displaystyle \ {w ', w \} \ in E \ setminus M}$

• jeśli P ' ma punkt końcowy v _B , to odcinek ścieżki u → v _B w G' jest zastępowany odcinkiem u → (u '→ ... → v') w G , gdzie wierzchołki kwiatu u ' i v' oraz strona B , (u '→ ... → v') , przechodząca od u ' do v', jest wybierana w celu zapewnienia, że ​​ścieżka jest naprzemienna ( v ' jest odsłonięta ).${\ displaystyle \ {u ', u \} \ in E \ setminus M}$

W ten sposób można skurczyć kwiaty i przeprowadzić wyszukiwanie na ściągniętych wykresach. Ta redukcja leży u podstaw algorytmu Edmondsa.

Znalezienie ścieżki wzmacniającej

Poszukiwanie ścieżki augmentacji wykorzystuje strukturę pomocniczą danych, składający się z lasów F którego drzewa jednostka odpowiada określonych części wykresu G . W rzeczywistości las F jest tym samym, który zostałby użyty do znalezienia maksymalnych dopasowań na wykresach dwudzielnych (bez potrzeby kurczenia się kwiatów). W każdej iteracji algorytm albo (1) znajduje ścieżkę rozszerzającą, (2) znajduje kwiat i powtarza się na odpowiadającym mu zwężonym wykresie, albo (3) stwierdza, że ​​nie ma ścieżek rozszerzających. Struktura pomocnicza jest budowana według procedury przyrostowej omówionej poniżej.

Procedura konstrukcji bierze pod uwagę wierzchołki v i krawędzie e w G i odpowiednio aktualizuje F przyrostowo . Jeśli V jest w drzewie T lasu, możemy pozwolić korzeń (v) oznaczymy pierwiastek T . Jeśli zarówno U i V są w tej samej drzewa T na F , damy odległość (U, V) oznacza długość ścieżki od unikalnego u do v w T .

    INPUT:  Graph G, matching M on G
    OUTPUT: augmenting path P in G or empty path if none found
B01 function find_augmenting_path(G, M) : P
B02    F ← empty forest
B03    unmark all vertices and edges in G, mark all edges of M
B05    for each exposed vertex v do
B06        create a singleton tree { v } and add the tree to F
B07    end for
B08    while there is an unmarked vertex v in F with distance(v, root(v)) even do
B09        while there exists an unmarked edge e = { v, w } do
B10            if w is not in F then
                   // w is matched, so add e and w's matched edge to F
B11                x ← vertex matched to w in M
B12                add edges { v, w } and { w, x } to the tree of v
B13            else
B14                if distance(w, root(w)) is odd then
                       // Do nothing.
B15                else
B16                    if root(v) ≠ root(w) then
                           // Report an augmenting path in F ${\displaystyle \cup }$ { e }.
B17                        P ← path (root(v) → ... → v) → (w → ... → root(w))
B18                        return P
B19                    else
                           // Contract a blossom in G and look for the path in the contracted graph.
B20                        B ← blossom formed by e and edges on the path v → w in T
B21                        G’, M’ ← contract G and M by B
B22                        P’ ← find_augmenting_path(G’, M’)
B23                        P ← lift P’ to G
B24                        return P
B25                    end if
B26                end if
B27            end if
B28            mark edge e
B29        end while
B30        mark vertex v
B31    end while
B32    return empty path
B33 end function

Przykłady

Poniższe cztery rysunki ilustrują wykonanie algorytmu. Linie przerywane wskazują krawędzie, których obecnie nie ma w lesie. Najpierw algorytm przetwarza krawędź poza lasem, która powoduje ekspansję bieżącego lasu (linie B10 - B12).

Następnie wykrywa kwiat i kurczy wykres (linie B20 - B21).

Na koniec lokalizuje rosnącą ścieżkę P ′ na skurczonym wykresie (linia B22) i podnosi ją do oryginalnego wykresu (linia B23). Zwróć uwagę, że zdolność algorytmu do ściągania kwiatów jest tutaj kluczowa; algorytm nie może znaleźć P w oryginalnym grafie bezpośrednio, ponieważ tylko poza lasem krawędzie między wierzchołkami w równych odległościach od korzeni są uwzględniane w linii B17 algorytmu.

Analiza

Las F zbudowany przez funkcję find_augmenting_path () jest lasem naprzemiennym.

• drzewo T w G jest drzewem naprzemiennym względem M , jeśli
  • T zawiera dokładnie jeden odsłonięty wierzchołek r zwany korzeniem drzewa
  • każdy wierzchołek w nieparzystej odległości od korzenia ma dokładnie dwie przypadkowe krawędzie w T , i
  • wszystkie ścieżki od R do liści T mają nawet długości, ich krawędzie nie są nieparzyste w M , a ich krawędzie są nawet w M .
• las F w G jest lasem naprzemiennym względem M , jeśli
  • jego połączone komponenty to naprzemienne drzewa, a
  • każdy narażony wierzchołek w G jest korzeniem drzewa zmiennego F .

Każda iteracja pętli rozpoczynająca się w linii B09 albo dodaje do drzewa T w F (linia B10), albo znajduje ścieżkę rozszerzającą (linia B17) lub znajduje kwiat (linia B20). Łatwo zauważyć, że czas pracy jest . ${\ Displaystyle O (| E || V | ^ {2})}$

Dopasowanie dwustronne

Kiedy G jest dwudzielne , w G nie ma cykli nieparzystych . W takim przypadku kwiaty nigdy nie zostaną znalezione i można po prostu usunąć linie B20 - B24 algorytmu. W ten sposób algorytm sprowadza się do standardowego algorytmu konstruowania dopasowań maksymalnej mocy w grafach dwudzielnych, w których wielokrotnie szukamy ścieżki rozszerzającej za pomocą prostego przejścia grafu: tak jest na przykład w przypadku algorytmu Forda-Fulkersona .

Dopasowanie ważone

Problem dopasowania można uogólnić, przypisując wagi krawędziom w G i prosząc o zestaw M, który daje dopasowanie maksymalnej (minimalnej) masy całkowitej: jest to problem z dopasowaniem maksymalnej wagi . Ten problem można rozwiązać za pomocą algorytmu kombinatorycznego, który wykorzystuje nieważony algorytm Edmondsa jako podprogram. Kolmogorov zapewnia wydajną implementację tego w C ++.

Bibliografia