Algorytm Kernighana-Lina

Algorytm Kernighana-Lina

Rodzaj	problemu podziału grafu na 2 równe części
Struktura danych	graf ważony
Złożoność
Czasowa	$O(n^{2}\log n)$

Algorytm Kernighana-Lina – heurystyczny algorytm o złożoności obliczeniowej $O(n^{2}\log n)$ 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

• 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.