Lalgoritmo Kernighan–Lin è un algoritmo euristico per la soluzione del problema della partizione di un grafo con complessità computazionale .
Questo algoritmo, proposto nel 1970 da Shen Lin e Brian Kernighan, ha importanti applicazioni per la progettazione di circuiti digitali e VLSI.
Descrizione
Si consideri il grafo , dove denota l'insieme dei vertici ed l'insieme degli archi.
L'algoritmo mira a trovare una partizione di in due sottoinsiemi e di uguale cardinalità, tali che la somma del costo degli archi fra elementi di e sia minimizzato.
In particolare, se si denota con
il costo interno di (cioè la somma del costo degli archi fra e altri elementi che sono nello stesso sottoinsieme, sia esso o ) il costo esterno (cioè la somma del costo degli archi fra e tutti gli altri vertici che non appartengono al medesimo insieme di ) la differenza di costo
Allora si ha che se si scambiano due elementi e (uno appartenente ad , l'altro a ), si ha una riduzione di costo
dove con si denota il costo dell'arco fra e .
L'algoritmo cerca una sequenza ottimale di permutazioni di un elemento di e uno di tale da massimizzare. its one of the optimized algorithms.
Pseudocodice Vedi
1 function Kernighan-Lin(G(V,E)): 2 determina una partizione iniziale dei vertici in A e B 3 do 4 A1 := A; B1 := B 5 calcola D per tutti gli a in A1 e b in B1 6 for (i := 1 to |V|/2) 7 trova a[i] da A1 e b[i] da B1 tali che g[i] = D[a[i] ] + D[b[i] ] - 2*c[a[i] ][b[i] ] è massimale 8 sposta a[i] a B1 e b[i] ad A1 9 tralascia a[i] e b[i] da ulteriori considerazioni 10 aggiorna i valori di D per gli elementi di A1 = A1 /{a[i]} and B1 = B1 /{b[i]} 11 end for 12 trova k che massimizza g_max=g + ... +g[k] 13 if (g_max > 0) then 14 Scambia a,a,...,a[k] with b,b,...,b[k] 15 until (g_max <= 0) 16 return G(V,E)
Note
Kernighan-Lin