Algorytm Kernighana-Lina

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Algorytm Kernighana-Lina
Rodzaj problemu podziału grafu na 2 równe części
Struktura danych graf ważony
Złożoność
Czasowa O(n2logn)
Niniejszy artykuł jest częścią cyklu teoria grafów.




Najważniejsze pojęcia
graf
drzewo
podgraf
cykl
klika
stopień wierzchołka
stopień grafu
dopełnienie grafu
obwód grafu
pokrycie wierzchołkowe
liczba chromatyczna
indeks chromatyczny
izomorfizm grafów
homeomorfizm grafów


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


Algorytmy grafowe
A*
Bellmana-Forda
Dijkstry
Fleury'ego
Floyda-Warshalla
Johnsona
Kruskala
Prima
przeszukiwanie grafu
wszerz
w głąb
najbliższego sąsiada


Zagadnienia przedstawiane jako problemy grafowe
problem komiwojażera
problem chińskiego listonosza
problem marszrutyzacji
problem kojarzenia małżeństw


Inne zagadnienia
kod Graya
diagram Hassego
kod Prüfera


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]

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]

 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]

Bibliografia[edytuj]

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