Algorytm Kernighana-Lina

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

 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ż[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

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