Algorytm Kernighana-Lina
Algorytm Kernighana-Lina to heurystyczna metoda o złożoności obliczeniowej O(n2 log n), która rozwiązuje problem podziału grafu na dwa równe części. Może działać na grafach z dodatnimi oraz ujemnymi wagami krawędzi.
Opis
Niech G(V, E) będzie grafem, gdzie V to zbiór wierzchołków, a E to zbiór krawędzi. Algorytm ma na celu znalezienie podziału V na dwa rozłączne, jednakowo liczne podzbiory A i B tak, aby łączna waga krawędzi łączących wierzchołki z podzbioru A i B, oznaczona jako T, była minimalna.
Niech Ia będzie wewnętrznym kosztem a, czyli sumą kosztów wszystkich krawędzi między a a pozostałymi wierzchołkami z A. Z kolei Ea będzie zewnętrznym kosztem a, czyli sumą kosztów krawędzi między a a wierzchołkami z B.
Zdefiniujmy Da jako:
Da = Ea – Ia,
czyli różnicę między zewnętrznym a wewnętrznym kosztem a. W momencie wymiany a i b, zysk wyraża się wzorem:
Tnew – Told = Da + Db – 2ca,b,
gdzie ca,b jest kosztem krawędzi między a i b.
Algorytm dąży do znalezienia optymalnej sekwencji wymian wierzchołków między A i B, maksymalizując funkcję celu określoną jako:
Tnew – Told.
Warto pamiętać, że po dokonaniu wyboru optymalnych wierzchołków następuje ich zamiana, ale w kolejnej iteracji nie są one brane pod uwagę – rozpatruje się n/2 – 1 wierzchołków w każdym z podzbiorów, aż nie pozostaną żadne do rozpatrzenia.
Dodatkowo, gdy wszystkie zyski z zamian w danej iteracji będą ujemne (co oznacza, że zamiana zwiększa sumę krawędzi łączących podgrafy), algorytm kontynuuje działanie, ponieważ przyszłe zamiany mogą przynieść lepsze wyniki.
Pseudokod
1. function Kernighan-Lin(G(V,E)):
2. określ zrównoważony początkowy podział węzłów na zbiory A i B
3. do
4. A1 := A; B1 := B
5. oblicz wartości D dla wszystkich a w A1 i b w B1
6. for (i := 1 to |V|/2)
7. znajdź a[i] z A1 i b[i] z B1, tak aby g[i] = D[a[i]] + D[b[i]] – 2*c[a][b] było maksymalne
8. przenieś a[i] do B1 i b[i] do A1
9. usuń a[i] i b[i] z dalszego rozpatrywania w tej iteracji
10. zaktualizuj wartości D dla elementów A1 = A1 \ a[i] i B1 = B1 \ b[i]
11. end for
12. znajdź k, które maksymalizuje g_max, sumę g[1],…,g[k]
13. if (g_max > 0) then
14. wymień a[1],a[2],…,a[k] z b[1],b[2],…,b[k]
15. until (g_max <= 0)
16. return G(V,E)
Zobacz też
Bibliografia
Kernighan, B.W.; Lin, Shen (1970). An efficient heuristic procedure for partitioning graphs. Bell Systems Technical Journal 49: 291–307.
Ravikumār, Si. Pi; Ravikumar, C.P (1995). Parallel methods for VLSI layout design. Greenwood Publishing Group. s. 73. ISBN 978-0-89391-828-6. OCLC 2009-06-12.
