Algorytm Kernighana-Lina

Algorytm Kernighana-Lina to Heurystyczny algorytm o złożoności obliczeniowej O(n2logn) 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.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 Ia będzie wewnętrznym kosztem a, czyli sumą kosztów wszystkich krawędzi między a i resztą wierzchołków z A, natomiast Ea zewnętrznym kosztem a, czyli sumą kosztów krawędzi między a i wierzchołkami z B. Zdefiniujmy Da jako:czyli różnicę między zewnętrznym i wewnętrznym kosztem a. W momencie wymiany a i b zysk wyraża się wyrażeniem:gdzie ca,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: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 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