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	${\displaystyle O(n^{2}\log n)}$

Algorytm Kernighana-Lina – heurystyczny algorytm o złożoności obliczeniowej ${\displaystyle 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 ${\displaystyle G(V,E)}$ będzie grafem, gdzie ${\displaystyle V}$ to zbiór jego wierzchołków, a ${\displaystyle E}$ zbiór krawędzi. Algorytm próbuje znaleźć podział ${\displaystyle V}$ na dwa rozłączne, jednakowo liczne podzbiory ${\displaystyle A}$ i ${\displaystyle B}$ tak, by sumaryczna waga krawędzi między wierzchołkami z podzbioru ${\displaystyle A}$ i ${\displaystyle B,}$ oznaczona przez ${\displaystyle T,}$ była jak najmniejsza.

Niech ${\displaystyle I_{a}}$ będzie wewnętrznym kosztem ${\displaystyle a}$, czyli sumą kosztów wszystkich krawędzi między ${\displaystyle a}$ i resztą wierzchołków z ${\displaystyle A,}$ natomiast ${\displaystyle E_{a}}$ zewnętrznym kosztem ${\displaystyle a,}$ czyli sumą kosztów krawędzi między ${\displaystyle a}$ i wierzchołkami z ${\displaystyle B.}$

Zdefiniujmy ${\displaystyle D_{a}}$ jako:

${\displaystyle D_{a}=E_{a}-I_{a},}$

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

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

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

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

${\displaystyle 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ę ${\displaystyle 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.