Algorytm Kernighana-Lina

Algorytm Kernighana-Lina to Heurystyczny algorytm o złożoności obliczeniowej $O(n^2logn)$ rozwiązywania problemu podziału grafu na 2 równe części. Może pracować na grafach o dodatnich jak i ujemnych wagach krawędzi.

Opis

Niech $G(V,E)$ będzie grafem, gdzie $V$ to zbiór jego wierzchołków, a $E$ zbiór krawędzi. Algorytm próbuje znaleźć podział $V$ na dwa rozłączne, jednakowo liczne podzbiory $A$ i $B$ tak, by sumaryczna waga krawędzi między wierzchołkami z podzbioru $A$ i $B$, oznaczona przez $T$, była jak najmniejsza. Niech $I_{a}$ będzie wewnętrznym kosztem a, czyli sumą kosztów wszystkich krawędzi między a i resztą wierzchołków z $A$, natomiast $E_{a}$ zewnętrznym kosztem a, czyli sumą kosztów krawędzi między a i wierzchołkami z $B$. Zdefiniujmy $D_{a}$ jako:

$D_{a} = E_{a} - I_{a}$

czyli różnicę między zewnętrznym i wewnętrznym kosztem a. W momencie wymiany a i b zysk wyraża się wyrażeniem:

$T_{new} - T_{old} = D_{a} + D_{b} - 2c_{a,b}$,

gdzie $c_{a,b}$ jest kosztem krawędzi między a i b.

Algorytm stara się znaleźć najkorzystniejszą sekwencję wymian wierzchołków między $A$ i $B$ przez maksymalizację funkcji celu określonej jako:

$T_{new} - T_{old}$

Należy pamiętać, że po wyborze optymalnych wierzchołków następuje ich zamiana, ale w kolejnej iteracji są one nie ruszane - rozpatruje się n/2 -1 wierzchołków w każdym z podzbiorów, i tak dalej, aż nie pozostanie więcej wierzchołków do rozpatrzenia.

Co więcej, gdy wszystkie zyski z zamian w danej iteracji będą ujemne (zamiana zwiększy sumę krawędzi łączących podgrafy), to algorytm działa dalej, gdyż być może kolejne zamiany okażą się lepsze.

Pseudokod

 1  function Kernighan-Lin(G(V,E)):
 2      determine a balanced initial partition of the nodes into sets A and B
 3      do
 2         A1 := A; B1 := B
 4         compute D values for all a in A1 and b in B1
 5         for (i := 1 to |V|/2)
 6          find a[i] from A1 and b[i] from B1, such that g[i] = D[a[i]] + D[b[i]] - 2*c[a][b] is maximal
 7          move a[i] to B1 and b[i] to A1
 8          remove a[i] and b[i] from further consideration in this pass
 9          update D values for the elements of A1 = A1 / a[i] and B1 = B1 / b[i]
 10        end for
 11        find k which maximizes g_max, the sum of g[1],...,g[k]
 12        if (g_max > 0) then
 13           Exchange a[1],a[2],...,a[k] with b[1],b[2],...,b[k]
 14     until (g_max <= 0)
 15  return G(V,E)

Zobacz też

• Brian Kernighan

Bibliografia

1. Kernighan, B. W.; Lin, Shen (1970). "An efficient heuristic procedure for partitioning graphs". Bell Systems Technical Journal 49: 291–307.

2. Ravikumār, Si. Pi; Ravikumar, C.P (1995). Parallel methods for VLSI layout design. Greenwood Publishing Group. pp. 73. ISBN 9780893918286. OCLC 2009-06-12